Jar*_*ike 11 algorithm graphics geometry
给定一组有序的2D像素位置(相邻或相邻对角线),形成一条没有重复的完整路径,如何确定多边形的最大线性尺寸,其周长是该像素集？(其中GLD是集合中任何一对点的最大线性距离)
就我的目的而言,明显的O(n ^ 2)解决方案对于数千个点的数字可能不够快.是否有良好的启发式或查找方法使时间复杂度更接近O(n)或O(log(n))？
Shr*_*saR 18
一种简单的方法是首先找到点的凸包,这可以在很多方面在O(n log n)时间内完成.[我喜欢格雷厄姆扫描(参见动画),但增量算法也很受欢迎,其他人也是如此,尽管有些花费更多时间.]
然后你可以通过在凸包上的任意两个点(比如x和y)开始找到最远的一对(直径),顺时针移动y直到它离x最远,然后移动x,再次移动y等等.你可以证明这整件事只需要O(n)时间(摊销).所以它总共是O(n log n)+ O(n)= O(n log n),如果你使用礼品包装作为你的凸包算法,它可能是O(nh).正如你所提到的,这个想法被称为旋转卡钳.
这是David Eppstein的代码(计算几何研究员;另见他的Python算法和数据结构以供将来参考).
所有这些都不是很难编码(最多应该是一百行;在上面的Python代码中小于50),但在你这样做之前 - 你应该首先考虑你是否真的需要它.如果,如你所说,你只有"数千个点",那么平凡的O(n ^ 2)算法(比较所有对)将在不到一秒的时间内以任何合理的编程语言运行.即使有一百万点,它也不应该超过一个小时.:-)
你应该选择最简单的算法.