Point-In-Polygon Testing Part 1

One of the most basic geometric tests is if a point, p, is inside a polygon poly.

The most common method for this test is casting a ray from the point p either horizontally or vertically and checking how many times it intersects the polygon. If the number of intersections is odd then p is inside poly. If the number of intersections is even then p is outside poly. In the below illustration the horizontal ray cast from black point intersects the polygon 3 times. Thus the black point is inside the polygon.

There are a few corner cases that have to be carefully handled.

Case 1. The point p is on the boundary of the polygon. In this case the algorithm may return true or false because of floating point issues.

Case 2. The casted ray intersects a vertex of the polygon. In this case the naive implementation of the algorithm would return two intersections because of the top line segment and the bottom line segment. The way to fix this is to only count an intersection if (1) it’s not an end-point intersection or (2) it’s an end-point intersection and the end-point of the line segment lies below the casted ray.

Case 3. The casted ray overlaps a line segment, l. In this case the casted ray intersects an end-point of the overlapping line segment, l and the line segment does not lie below the casted ray. So do not count the line segment l intersection(s).

By implementing the special cases this point-in-polygon method should work extremely well. It’s a fast method since the only operations used are compares. The big-O is O(n) where n is the number of line segments for the polygon.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s