computational-geometry - 确定给定点是否在多边形内

Question

给定一个凸多边形作为 n 个顶点的逆时针列表，给出 O(lgn) 算法来确定给定的点是否在多边形内。假设基本操作需要 O(1)。

我认为一个方向是:如果一个点在凸多边形内，那么这些点与所有顶点或边之间的特殊关系是什么？另外，我猜这里的技巧是使算法lgn的凸多边形。

Answer 1

我所知道的这个问题的唯一解决方案需要 O(n)多边形预处理时间。然后针对预处理多边形的每个查询点在 O(lg n) 中处理。时间。

就拿一点P在多边形内部(我们称之为“极点”)，并为每个顶点绘制一条从 P 退出的射线并通过顶点。将此视为原点位于 P 的极坐标系。 ，整个极平面被这些射线分割为扇区。现在，给定您的查询点，您只需要将其转换为以我们极点为原点的极坐标 P .然后只需执行二分查找来确定包含查询点的特定扇区。扇区内的最终内部/外部检查(点与边缘侧测试)是微不足道的 O(1)手术。每个查询都在 O(lg n) 中处理二分查找所需的时间。

这种方法实际上适用于更多类的多边形，而不仅仅是凸多边形。它涵盖了所谓的星形多边形类，即具有一个点的多边形，从这个点可以“看到”或“观察”多边形的整个内部。
O(n)预处理时间来自于需要提前确定极点的位置。

附言我不得不考虑更一般的情况。如果您的多边形是凸多边形，您可以简单地使用它的任何顶点作为极点。这样你就会得到一个 O(lg n)算法，不需要预处理。