determine if a given point is inside the polygon

问题:

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.

回答1:

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.

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

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.

回答2:

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/

回答3:

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.