Point-in-Polygon: a "plumbline" algorithm
|
The problem of point location is to find in which polygon a reference point lies. A typical application of this problem is an interactive map: if I click on the map, how can the software tell me if I clicked in Pennsylvania or Ohio?
The plumbline algorithm is based on a very simple idea. From the reference point (for example, where I click on the map), drop a vertical line. This is called a plumbline, since vertical lines in the construction industry were once made by attaching a heavy lead weight, called a plumb or plumb-bob, to a string. The weight pulled the string to a vertical alignment, and the carpenter could then mark the vertical line. In the plumbline algorithm, we count the number of times the plumbline intersects sides of a polygon. Obviously, if the plumbline does not intersect any sides of the polygon, the reference point is not in the polygon. Equally obvious: if the plumbline intersects just one side of the polygon, then the reference point is inside the polygon. Generally: if the plumbline intersects an odd number of sides of the polygon, then the reference point is inside the polygon. The efficiency algorithm depends on the number of sides of all polygons which could contain the reference point. In some cases, one can quickly decide if the polygon intersects a side or not: if both ends of the side lie to the left or right of the plumbline, then there can be no intersections. There is one movie available, based on a map of Worcester County, Maryland, USA. Click on the Download button at the right to obtain both versions of this movie in a zipped file. |