Point-in-Polygon: Trapezoidal Map algorithm
divide the polygon into trapezoids, and find the right trapezoid
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.
One movie is available; it comes from an actual map of Worcester County, Maryland. There is a version with pauses for questions, and one without those pauses. Remember the guidelines for use of these movies.
|
|
|
|
