Planar Point Location

Kirkpatrick's Algorithm

Kirkpatrick (1983) proposed a method for planar point location now known as the triangle refinement method. Given a finite planar sudivision the algorithm creates a corresponding triangular subdivision in which each region is bounded by three line segments (or in simple terms is a triangle)! A polygonal subdivision may be transformed into a triangular subdivision by triangulating each polygon and finally placing a single bounding triangle around the entire region. Note that each triangular region in this new subdivision can be linked to its parent polygon so that a point query which finds a triangle in the triangular subdivision can be used to select the parent polygon.

Given such a triangular subdivision, S a subdivision hierarchy is a sequence of such triangulations creating subdivisions S₁, S₂, S₃, ..., S_h(n) where S₁=S and each region R of S_i+1 is linked to each region R' of S_i where R' intersects R. h(n) is the hieght of the subdivision hierarchy.

Fig. 1: A vertex (in red) is selected and its adjacent regions (labelled a through e) are deleted at the S_i level resulting in a new polygonal region (shaded). On the right we see the new triangulation for this polygon at the S_i+1 level. New regions in the S_i+1 level are then linked to regions in the S_i level if they intersect. Thus for example region G would be linked to all regions while region J would be linked to e and f.

The subdivision hierarchy is generated in the following manner. At the lowest level, S₁ a set of non-adjacent vertices with degree = 6 are selected. The vertex is deleted resulting in a new polygonal region which replaces the triangles but a degree lower (by 1) than the original region. This new polygonal region is then re-triangulated forming a new set of triangles at the S₂ level, which are linked to each of the intersecting deleted triangles from the S₁ level. This proceedure is duplicated for all degree 6 vertices at S₁ level to generate the S₂ level. Then the process is repeated, selecting a new set of degree 6 vertices at the S₂ level and repeating the deletion/retriangulation to form the S₃ level. The process is repeated until we arrive at the S_h level, which is a the single triangle representing the search region.

Fig. 2: The search structure for a hierarchical subdivision. The lowest levels corresponding to shaded portions of the S₁ and S₂ levels in Fig. 1 shaded in grey. The S_h level (Z) and the S_h-1 levels are also shown.

With the subdivision hierarchy completed we can now perform queries. The query process operates by starting at the S_h level and working down to the S₁ level as follows:

1. Search in the S_h level to determine which triangular region, R, the query point q falls in.

2. Search at the S_h-1 level in all triangular regions linked to R to determine which of these regions q falls in. This region now becomes R and we repeat step 2 at the next lower level until we arrive at S₁ at which point we have our result, since the triangular regions in S₁ keep a reference to their parent polygon in the original subdivision.

For an excellent discussion of Kirkpatrick's Algorithm see Derek Bradley's project on the topic.