确定给定点是否在多边形内部
给定一个凸多边形作为 n 个顶点的逆时针列表，给出 O(lgn) 算法来确定给定点是否在多边形内部。假设基本操作需要 O(1)。
我认为一个方向是：如果一个点在凸多边形内部，那么该点与所有顶点或边之间有什么特殊关系？另外，我猜这里的技巧是凸多边形，它使得算法为 lgn。
Given a convex polygon as a counter-clockwise list of n vertices, give O(lgn) algorithm to determine if a given point is inside the polygon. Assume the basic operations take O(1).
I am think a direction that: if a point is inside a convex polygon, what is the special relationship among the points and all the vertecies or edges? Also, I am guessing the trick here is the convex polygon which makes the algorithm lgn.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
据我所知，此问题的唯一解决方案需要
O(n)多边形预处理时间。然后，针对预处理多边形的每个查询点都会在 O(lg n) 时间内处理。只需在多边形内取一个点
P（我们称之为“极点”），并为每个顶点绘制一条从P退出并穿过该顶点的射线。将其视为原点位于 P 的极坐标系，整个极平面被这些射线细分为多个扇区。现在，给定您的查询点，您只需将其转换为原点位于极点P的极坐标。然后只需执行二分查找即可确定包含查询点的特定扇区。扇区内的最终内部/外部检查（点与边缘测试）是一个简单的O(1)操作。每个查询的处理时间为二分搜索所需的O(lg n)时间。这种方法实际上适用于更大类别的多边形，而不仅仅是凸多边形。它涵盖了所谓的星形多边形，即具有一个点的多边形，从该点可以“看到”或“观察”多边形的整个内部。
O(n)预处理时间来自于需要提前确定极点的位置。PS 我开始思考更一般的情况。如果你的多边形是凸的，你可以简单地使用它的任何顶点作为极点。这样您就可以立即获得
O(lg n)算法，无需进行预处理。The only solution for this problem I know of requires
O(n)polygon preprocessing time. Afterwards each query point against a preprocessed polygon is handled inO(lg n)time.Just take a point
Pinside the polygon (let's call it "pole") and for each vertex draw a ray exiting fromPand passing through the vertex. Consider this to be a polar coordinate system with origin atP, with the entire polar plane subdivided into sectors by these rays. Now, given your query point, you just need to convert it to polar coordinates with origin at our poleP. Then just perform binary search to determine the specific sector that contains the query point. The final inside/outside check within the sector (point vs. edge side test) is a trivialO(1)operation. Each query is handled inO(lg n)time needed for binary search.This approach will actually work with a larger class of polygons than just convex ones. It covers the class of so called star-shaped polygons, i.e. polygons that have a point from which the whole interior of the polygon can be "seen" or "observed".
The
O(n)preprocessing time comes from the need to determine the location of the pole in advance.P.S. I got to carried away thinking about more general case. If your polygon is convex, you can simply use any of its vertices as the pole. That way you get a
O(lg n)algorithm right away, no preprocessing required.您可能需要检查此链接，其中包含如何确定点是否位于复杂多边形内部的详细信息，包括示例 (c) 代码。
http://alienryderflex.com/polygon/
you might want to check this link with detailed info how to determine whether a point is inside a complex polygon, including sample (c) code.
http://alienryderflex.com/polygon/
点位于多边形内的条件是该点应位于所有线段的同一侧。您应该检查相关点与构成多边形的每条线段的距离的符号 - 如果所有符号都相同，则该点位于多边形内部。谷歌搜索应该会给你很多算法。
The condition for a point to be inside a polygon is that the point should be on same side of all line segments. You should check for the sign of the distance of the point in question with each line segments that make up the polygon - if all are same sign the point is inside the polygon. A google search should give you many algorithms.