最大线性维度 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(log(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 log n) 时间内完成.[我喜欢格雷厄姆扫描(见动画)，但 增量 算法也很流行，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，再次移动 y，等等. 你可以证明整个事情只需要 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.

这里是 David Eppstein 的代码(计算几何研究员；另见他的 Python 算法和数据结构 以供将来参考).

Here is code by David Eppstein (computational geometry researcher; see also his Python Algorithms and Data Structures for future reference).

所有这些都不是很难编码(最多应该是一百行；在上面的 Python 代码中不到 50 行)，但是在你这样做之前——你应该首先考虑你是否真的需要它.如果，如你所说，你只有数千个点"，那么简单的 O(n^2) 算法(比较所有对)将在任何合理的编程语言中运行不到一秒钟.即使有 100 万积分，也不应该超过一个小时.:-)

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屋！