给定一组多边形和一系列点,找到哪些多边形是点

Question

这是一个类似于这里的问题,但我认为如果我能用更一般的术语重新编写它会有所帮助.

我有一组多边形,这些多边形可以互相接触,重叠并可以呈现任何形状.我的问题是,给出一个点列表,如何设计一个有效的算法,找出哪些多边形是点？

点的位置的一个有趣的限制是,如果这有帮助,所有点都位于多边形的边缘.

我知道r-trees 可以提供帮助,但鉴于我正在做一系列的点,是否有更高效的算法而不是逐个计算每个点？

Answer 1

我认为你遇到的是关于问题的直觉（这是一种准模拟感知）与必然为 O(n) 的计算方法。

给定一个平面、一个简并多边形（一条线）以及该平面上的任意一组点，这些点是否与该线相交或落在该线的“上方”或“下方”？即使对于这种退化情况，我也无法想到小于 O(n) 的方法。

要么必须检查每个点与直线的关系，要么必须将这些点划分为某种树状结构，这至少需要 O(n) 次操作，但很可能更多。

如果我更擅长计算几何，我可能可以权威地说你刚刚重述了克利的测量问题，但事实上我只需要提出建议。