Point Location

  

 

Input description: A decomposition of the plane into polygonal regions and a query point q.

Problem description: Which region contains the query point q?

Discussion: Point location is a fundamental subproblem in computational geometry, usually needed as an ingredient to solve larger geometric problems. In a dispatch system to assign policemen to the scene of a crime, the city will be partitioned into different precincts or districts.   Given a map of regions and a query point (the crime scene), the system must identify which region contains the point. This is exactly the problem of planar point location, variations of which include:

• Is a given point inside or outside of polygon P? - The simplest version of point location involves only two regions, inside-P and outside-P, and asks which contains a given query point. For polygons with lots of narrow spirals, this can be surprisingly difficult to tell by inspection. The secret to doing it both by eye or machine is to draw a ray starting from the query point and ending beyond the furthest extent of the polygon. Count the number of times the polygon crosses through an edge. If this number is odd, we must be within the polygon. If it is even, we must be outside. The case of the line passing through a vertex instead of an edge is evident from context, since we are counting the number of times we pass through the boundary of the polygon. Testing each of the n edges for intersection against the query ray takes O(n) time. Faster algorithms for convex polygons are based on binary search and take time.    
• How many queries will have to be performed? - When we have a subdivision with multiple regions, it is always possible to repeat the inside-polygon test above on each region in the subdivision. However, this is wasteful if we will be performing many such point location queries on the same subdivision. Instead, we can construct a grid-like or tree-like data structure on top of our subdivision to get us near the correct region quickly. Such search structures are discussed in more detail below.
• How complicated are the regions of your subdivision? - More sophisticated inside-outside tests are required when the regions of your subdivision are arbitrary polygons. By triangulating all polygonal regions first, each inside-outside test reduces to testing whether a point is in a triangle. Such a test can be made particularly fast and simple, at the minor cost of recording the full-polygon name for each triangle. An added benefit is that the smaller your regions are, the better grid-like or tree-like superstructures are likely to perform. Some care should be taken when you triangulate to avoid long skinny triangles, as discussed in Section .   
• How regularly sized and spaced are your regions? - If all resulting triangles are about the same size and shape, the simplest point location method imposes a regularly-spaced grid of horizontal and vertical lines over the entire subdivision. For each of the rectangular regions, we maintain a list of all the regions that are at least partially contained within the rectangle. Performing a point location query in such a grid file involves a binary search or hash table lookup to identify which rectangle contains query point q and then searching each region in the resulting list to identify the right one.  

  Such grid files will perform very well, provided that each triangular region overlaps only a few rectangles (thus minimizing storage space) and each rectangle overlaps only a few triangles (thus minimizing search time). Whether it will perform well is a function of the regularity of your subdivision. Some flexibility can be achieved by spacing the horizontal lines irregularly, as a function of the regions of the subdivision. The slab method, discussed below, is a variation on this idea that guarantees worst-case efficient point location at the cost of quadratic space.  

• How many dimensions will you be working in? - In three or more dimensions, some flavor of kd-tree will almost certainly be the point-location method of choice. They are also likely to be the right answer for planar subdivisions too irregular for grid files.

  Kd-trees, described in Section , decompose the space into a hierarchy of rectangular boxes. At each node in the tree, the current box is split into a small number (typically 2 or 4 or , where d is the dimension) of smaller boxes. At the leaves of the tree, each box is labeled with the small number of regions that are at least partially contained in the box. The point location search starts at the root of the tree and keeps traversing down the child whose box contains the query point. When the search hits a leaf, we test each of the relevant regions against q to see which one of them contains the point. As with grid files, we hope that each leaf contains a small number of regions and that each region does not cut across too many leaf cells.

The simplest algorithm to guarantee worst-case access is the slab method, which draws horizontal lines through each vertex, thus creating n+1 ``slabs'' between the lines. Since the slabs are defined by horizontal lines, finding the slab containing a particular query point can be done using a binary search on the y-coordinate of q. Since there can be no vertices within any slab, looking for the region containing a point within a slab can be done by a second binary search on the edges that cross the slab. The catch is that a binary search tree must be maintained for each slab, for a worst-case of space if each region intersects each slab. A more space-efficient approach based on building a hierarchy of triangulations over the regions also achieves for search and is discussed in the notes below.  

Worst-case efficient computational geometry methods either require a lot of storage or are fairly complicated to implement. We identify implementations of worst-case methods below, which are worth at least experimenting with. However, we recommend kd-trees for most general point-location applications.

Implementations: LEDA (see Section ) provides excellent support for maintaining planar subdivisions in C++ and, in particular, supports point location in time.    

Arrange is a package for maintaining arrangements of polygons in either the plane or on the sphere. Polygons may be degenerate, and hence represent arrangements of lines. A randomized incremental construction algorithm is used, and efficient point location on the arrangement is supported. Polygons may be inserted but not deleted from the arrangement, and arrangements of several thousand vertices and edges can be constructed in a few seconds. Arrange is written in C by Michael Goldwasser and is available from http://theory.stanford.edu/people/wass/wass.html.    

A routine in C to test whether a point lies in a simple polygon has been provided by O'Rourke [O'R94], and a Pascal routine for the same problem by [MS91]. For information on both, see Section .  

Notes: The inside-outside test for convex polygons is described in [PS85], which has a very thorough treatment of deterministic planar point location data structures. Expositions on the inside-outside test for simple polygons include [Man89, PS85].

An experimental study of algorithms for planar point location is described in [EKA84]. The winner was a bucketing technique akin to the grid file.   

The elegant triangle refinement method of Kirkpatrick [Kir83] builds a hierarchy of triangulations above the actual planar subdivision such that each triangle on a given level intersects only a constant number of triangles on the following level. Since each triangulation is a fraction of the size of the subsequent one, the total space is obtained by summing up a geometric series and hence is linear. Further, the height of the hierarchy is , ensuring fast query times. An alternative algorithm realizing the same time bounds is [EGS86]. The slab method described above is due to [DL76] and is presented in [PS85].

More recently, there has been interest in dynamic data structures for point location, which support fast incremental updates of the planar subdivision (such as insertions and deletions of edges and vertices) as well as fast point location. Chiang and Tamassia's [CT92] survey is an appropriate place to begin.  

Related Problems: Kd-trees (see page ), Voronoi diagrams (see page ), nearest neighbor search (see page ).