确定给定点是否在多边形内 [英] determine if a given point is inside the polygon

问题描述

给定一个凸多边形作为n个顶点的逆时针列表，请使用O（lgn）算法确定给定点是否在多边形内。假设基本运算取O（1）。

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).

我认为一个方向是：如果一个点在凸多边形内，则这些点之间的特殊关系是什么？所有的顶点或边缘？另外，我猜这里的窍门是使算法成为lgn的凸多边形。

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.

推荐答案

我知道的唯一解决此问题的方法需要 O（n）多边形预处理时间。然后，在 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 in O(lg n) time.

只需在多边形内取一个 P 点（我们称其为极点），并为每个顶点绘制一个光线从 P 离开并穿过顶点。认为这是一个原点为 P 的极坐标系统，整个极平面被这些射线细分为扇区。现在，给定您的查询点，您只需要将其转换为极坐标为原点为我们的极坐标 P 的极坐标。然后，只需执行二进制搜索即可确定包含查询点的特定扇区。该扇区内的最终内部/外部检查（点与边缘侧测试）是一个简单的 O（1）操作。每个查询的处理时间均小于 O（lg n）二进制搜索所需的时间。

Just take a point P inside the polygon (let's call it "pole") and for each vertex draw a ray exiting from P and passing through the vertex. Consider this to be a polar coordinate system with origin at P, 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 pole P. 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 trivial O(1) operation. Each query is handled in O(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".

O（n）预处理时间来自需要提前确定极点的位置。

The O(n) preprocessing time comes from the need to determine the location of the pole in advance.

PS 我不得不考虑更一般的情况。如果多边形是凸的，则可以简单地使用其任何顶点作为极点。这样，您就可以立即得到 O（lg n）算法，无需进行预处理。

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.

这篇关于确定给定点是否在多边形内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！