最大线性尺寸的2D点集 [英] Greatest linear dimension 2d set of points
问题描述
鉴于2D像素位置的有序集合（相邻或相邻对角线）形成，没有重复一个完整的路径，如何确定它的边界是集像素的多边形的最大线性尺寸？ （其中GLD是在该组的任何一对的点的最大线性距离）
Given an ordered set of 2D pixel locations (adjacent or adjacent-diagonal) that form a complete path with no repeats, how do I determine the Greatest Linear Dimension of the polygon whose perimeter is that set of pixels? (where the GLD is the greatest linear distance of any pair of points in the set)
对于我而言，很明显为O（n ^ 2）的解决方案可能是速度不够快的千点的数字。是否有很好的启发，或者把时间复杂度接近O（N）或O（日志（N））？
For my purposes, the obvious O(n^2) solution is probably not fast enough for figures of thousands of points. Are there good heuristics or lookup methods that bring the time complexity nearer to O(n) or O(log(n))?
推荐答案
这是简单的方法是先找到点，这可以在O进行凸包（N日志N）在许多方面的时间。 [我喜欢 Graham扫描（见<一href="http://www.cs.princeton.edu/courses/archive/fall08/cos226/demo/ah/GrahamScan.html">animation),但增量算法也很受欢迎，因为是的others ，但也有一些需要的更多的时间]
An easy way is to first find the convex hull of the points, which can be done in O(n log n) time in many ways. [I like Graham scan (see animation), but the incremental algorithm is also popular, as are others, although some take more time.]
然后就可以通过启动任意两点（比如x和y）的凸包，Y顺时针方向移动找到最远的一对（直径），直到它最远的距离X，然后移动X，移动ÿ再等你能证明这整个事情只需要O（n）时间（摊销）。因此，它是为O（n log n）的+ O（N）=为O（n log n）的所有，并有可能O（NH）如果你使用礼品包装作为您的凸包的算法来代替。这种想法称为旋转，正如你所提到卡钳。
Then you can find the farthest pair (the diameter) by starting with any two points (say x and y) on the convex hull, moving y clockwise until it is furthest from x, then moving x, moving y again, etc. You can prove that this whole thing takes only O(n) time (amortized). So it's O(n log n)+O(n)=O(n log n) in all, and possibly O(nh) if you use gift-wrapping as your convex hull algorithm instead. This idea is called rotating calipers, as you mentioned.
下面是 code由David Eppstein的（计算几何研究;也见他的<一个HREF =http://www.ics.uci.edu/~eppstein/PADS/> Python的算法与数据结构中以供将来参考）。
Here is code by David Eppstein (computational geometry researcher; see also his Python Algorithms and Data Structures for future reference).
这一切是不是很辛苦，以code（应该是一百行顶多是低于50在Python code以上），但在此之前 - 你应该首先考虑是否你真的需要它。如果像你说的，你只有千点，那么平凡为O（n ^ 2）算法（也比较全对）将在不到一秒钟的任何合理的编程语言运行。即使有万点应该不会超过一个小时。 ： - ）
All this is not very hard to code (should be a hundred lines at most; is less than 50 in the Python code above), but before you do that -- you should first consider whether you really need it. If, as you say, you have only "thousands of points", then the trivial O(n^2) algorithm (that compares all pairs) will be run in less than a second in any reasonable programming language. Even with a million points it shouldn't take more than an hour. :-)
您应该选择的简单的算法，它的工作原理。
You should pick the simplest algorithm that works.
这篇关于最大线性尺寸的2D点集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
