Walking in a Triangulation - VoroWiki: "Given the Delaunay triangulation (DT) of a set S of n points and a query point p, the point location problem consists of determining inside which triangle of lies p.
This is a necessary operation for the incremental constructing of a DT, for deleting a vertex from it, and also for different spatial analysis operations.
The method described here is called walking in a triangulation, and does not need any pre-processing or any additional data structures.
The adjacency relationships between the simplices in a DT are used to perform the point location. The algorithm was described in the earliest papers about the construction of the DT in two dimensions (Gold et al., 1977)[1]; Green and Sibson, 1978[2]): in a DT, starting from a triangle τ, we move to one of the neighbours of τ (τ has 3 neighbours; we choose one neighbour such that the query point p and τ are on each side of the triangle shared by τ and its neighbour) until there is no such neighbour, then the triangle containing p is τ. The algorithm is illustrated on the right."
