next up previous contents index Search
Next: Source Code Up: 0.8 Geometric Algorithms Previous: 0.8.2 Closest Pair Problem

0.8.3 Determining Whether a Point is Inside a Polygon

The following algorithm was sent to me by Romano Giannetti who got it from the FAQ where it was originally written by Wm. Randolph Franklin. It works on convex or concave algorithms, simple and complex.

It works by the ray tracing method. Starting at the coordinates of the point in question draw a straight line in any direction. If the number of times it intersects the polygon border is odd the starting point is inside the polygon. If it is even the starting point is outside the polygon.

Another good polygon algorithm page is Darel Finley's. Check it out at

Scott Gasch