道格拉斯-普克(Douglas-Peucker)折线简化算法的最坏时间复杂度为O(n²)。然而,要使一条线真正触发这种最坏情况,必须同时出现两件事情:
那么,是否存在一个简单的示例线路可以产生最坏情况(最好是触发每个递归步骤中偏差最大的点直接连接到线路端点的显而易见的最坏情况;但是任何其他示例也可以)?
- 阈值必须设置得非常低,以保留大部分顶点。
- 在每个递归步骤中,离当前端点连线的偏差最大的顶点必须靠近(按照其在线上的索引而不是欧几里德位置)其中一个端点。如果离线段的最大偏差点的索引足够靠近当前端点之间的中心,则算法应该会导致深度为log(n)的递归二进制细分,从而导致总时间复杂度为O(n log(n))。
那么,是否存在一个简单的示例线路可以产生最坏情况(最好是触发每个递归步骤中偏差最大的点直接连接到线路端点的显而易见的最坏情况;但是任何其他示例也可以)?
[0, 1, ..., 10]
和y位置[0, 10, -9, 8, ..., 0]
的点。当你画出来时,更容易看到它的效果 ;) - Vincent van der Weele