确定给定点是否在多边形内部

Question

确定给定点是否在多边形内部

computational-geometry

7

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

我想到了一个方向：如果一个点在一个凸多边形内部，那么这些点和所有的顶点或边之间有何特殊关系？此外，我猜想这里的技巧是凸多边形，这使得算法复杂度为lgn。

- SecureFish

这里有一个提示：想象从该点无限延伸一条线，朝着多边形外部绘制，在内部则可以向任何方向绘制。这条线会相交多少次？我相信这可以回答你的问题。 - Jesus Ramos

@Jesus Ramos：该算法适用于任何多边形（而不仅仅是凸多边形），并且它的时间复杂度是O(n)。在这种情况下，整个重点是利用多边形是凸的事实提出O(lg n)算法。 - AnT stands with Russia

@Jesus，我有什么遗漏吗？据我所知，你的建议是O(n)而不是O(log(n))。 - Bart Kiers

1

请访问以下链接：http://erich.realtimerendering.com/ptinpoly/ - Bart Kiers

@Bart Andrey的回答就是我想要的提示，我通常不喜欢直接给出这类问题的答案，我希望让人们多思考一下。 - Jesus Ramos

3个回答

1

你可能想要查看这个链接，其中包含详细信息，如何确定一个点是否在一个复杂的多边形内，包括示例（c）代码。

http://alienryderflex.com/polygon/

- Marnix v. R.

0

一个点在多边形内的条件是该点应该在所有线段的同一侧。您应该检查问题点与构成多边形的每条线段之间的距离的符号 - 如果所有符号相同，则该点在多边形内。通过谷歌搜索可以找到许多算法。

- d-live

但那是一个O(n)算法，而不是一个O(log(n))算法。 - Bart Kiers

由于其复杂度为 O(n)，它不符合要求。 - AnT stands with Russia

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AnT stands with Russia · Accepted Answer

我所了解的此问题的唯一解决方案需要 O(n) 多边形的预处理时间。之后，每个查询点都可以在预处理多边形中处理，并且处理时间为 O(lg n)。

只需取多边形内部的一个点 P（称之为“极点”），对于每个顶点从 P 出发并经过该顶点绘制射线。将其视为极坐标系，其原点位于 P，通过这些射线将整个极面划分为扇区。现在，给定查询点，您只需要将其转换为以我们的极点 P 为原点的极坐标系即可。然后进行二进制搜索，以确定包含查询点的特定扇区。扇区内的最终内/外检查（点与边的位置测试）是一个微不足道的操作，时间复杂度为 O(1)。每次查询都需要用于二进制搜索的 O(lg n) 时间来处理。

实际上，此方法适用于比凸多边形更大的多边形类。它涵盖了被称为“星状”的多边形类，即具有可以从中“看到”或“观察到”整个多边形内部的点的多边形。

需要进行 O(n) 预处理的原因是需要提前确定极点的位置。

附言：如果您的多边形是凸多边形，您可以直接将其任何一个顶点用作极点。那么您就可以立即获得 O(lg n) 算法，无需预处理。