Point-in-Polygon: a "trapezoidal map" 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 trapezoidal map algorithm makes use of the binary search algorithm, the fastest way to search for something in a sorted collection. The map is divided into trapezoids by drawing a vertical line through every vertex of every polygon in the map. The very thin slivers are sorted by their horizontal coordinate, and so it is fast to find in which sliver the reference point lies. But, each sliver is composed of a number of trapezoids, and so it is then possible to find in which trapezoid the reference point lies. If we are careful to remember to which polygon a trapezoid belongs, we will quickly discover in which polygon the reference point lies. The efficiency algorithm depends on the logarithm of sides of all polygons which could contain the reference point. 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. |