determine if a given point is inside the polygon

7
votes

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.

3
computational-geometry
here's a hint think of drawing an infinite line from that point towards the polygon if it's outside or in any direction if it's inside, how many intersections does the line have? I believe that will answer your question. – Jesus Ramos
@Jesus Ramos: That algorithm is applicable to any polygon (not just convex ones) and it is O(n). In this case the whole point is to come up with O(lg n) algorithm by using the fact that the polygon is convex. – AnT
@Jesus, am I missing something? AFAIK, your suggestion is O(n), not O(log(n)). – Bart Kiers
see: erich.realtimerendering.com/ptinpoly – Bart Kiers
@Bart Andrey's answer is the hint I was getting at, I usually don't like to give away the answer to these types of problems, I like to make people think a little bit. – Jesus Ramos

3 Answers

12
votes

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.

1
votes

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/

0
votes

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.