Point location
|
|
The point location problems and algorithms are a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographical information systems (GIS), motion planning, and CAD.
In its most general form, the problem is, given a point in the plane or in the space, to determine which area of interest the point belongs to. Each time you click a mouse to follow a web link, this problem is to be solved, namely, to determine which area of the computer screen is under the mouse pointer.
The simplest example is the point-in-polygon problem. In this case, there are three "areas of interest": polygon interior, polygon exterior and polygon boundary.
| Contents |
Point location in 2D
In two dimensions, the point location problem restricts itself to a plane. In general, given a planar subdivision, on which face is a point located? A linear search of each face using the point-in-polygon algorithm is possible, but usually not feasible for inputs of moderately reasonable size.
Simple point location algorithm
Suppose that S is a planar subdivision of R2 and p is a point located in S. To locate the face that contains p in O(log n) time, it is possible to divide S into "slabs" by projecting a line upwards and downwards from each vertex. These slabs are then ordered from left to right. The slab containing p can be found in logarithmic time by using a binary search.
Missing image
Planar_map.png
A planar subdivision S
Missing image
Planar_map_slabs.png
A planar subdivision divided into slabs
Missing image Planar_map_single_slab.png A single slab Notice that any given slab contains only line segments (with the degenerate case where a line segment is located on the edge of the slab). Each region inbetween two line segments has a one-to-one correspondence with a unique face on S, with the regions at the top and bottom corresponding to space outside of S. Because of this, it is possible to sort the line segments in each slab. Now the region containing p can be determined in O(logn) time. |
Space requirements
While this algorithm allows for point location in logarithmic time and is easy to implement, the space required to build the slabs and the regions contained within the slabs is at worst O(n2). While in most cases it is actually smaller than this, it is usually significantly larger than O(n). To solve this problem, other data structures and algorithms are used that have O(log n) point location and O(n) space requirements, such as trapezoidal decompositions.
References
- de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry, 2nd Edition. Berlin: Springer, 2000. ch. 6. ISBN 3540656200