Efficiently find Delaunay Triangulation face, which a given point lies on

Question

Given a Delaunay Triangulation of a point set, how should I index my triangulation to do quick point localization?

I'm currently looping over all the triangles. For each triangle, I'm checking if the given point is within triangle's bounding rectangle. If it is, I then check the triangle using geometry equations.

This is slow. Any ideas of how to make this search more efficient?

Answer 1

A solution is a hierarchical tree, I.e. dendogram or hierarchical cluster. For example use the euklidian distance:http://en.m.wikipedia.org/wiki/Hierarchical_clustering. Or you can use a metric tree.

Answer 2

A common approach to solve this point location problem is the efficient Trapezoidal Decomposition. It reduces the query time to O(Log(N)) per point, after O(N.Log(N)) preprocessing time, using O(N) space.

It could also be that the distribution of your query points allows alternative/simpler approaches.

Answer 3

Mission accomplished, that's the way I ended up doing it:

1) Check if the point lies within triangle bounding rectangle.

2) Assign the point as the start of a horizontal line, ending at max width.

3) Check intersections from the triangles found in (1) with the line from (2).

4) If triangle intersect, check how many times the horizontal line intersect with the triangle.

5) If intersects 1 time, means point in triangle. Else, not in triangle.

Reference:

Fast generation of points inside triangulated objects obtained by cross-sectional contours

Answer 4

Ranging from quick and practical to theoretically robust, here are three approaches you could use:

• Construct a regular grid where each cell contains a list of triangles that intersect it. Given a query point, in constant time determine the cell that contains it, then compare your query point against only those triangles that are in that cell's list.

• Construct a quadtree where each leaf cell contains the triangles that intersect it. Localizing the query point to a quadtree leaf takes logtime, but this can be more efficient in both speed and memory overall.

• Sweep a horizontal line down across all the triangles. Points in your point sets correspond to events. At each event, some triangles begin intersecting the sweepline, and other triangles stop intersecting the sweepline. You can use an immutable (aka persistent) sorted map data structure to efficiently represent this. map<double, sweepstate>, where the key is the y-intercept of the sweepline at an event and sweepstate is a sorted list of line segment pairs (corresponding to the left and right sides of triangles). Given a query point, you first use its y value to lookup a sweepstate, and then you do a single trapezoid containment test. (Two horizontal sweeplines and two line segments between them form a trapezoid.)