Identify a certain triangle

[holmhaavard]

Hello, If I have a large number of triangles and want to find which triangle encapsulates a certain point. What is the best method to do that ?

eg. I triangulated a domain :x:0-1, y:0-1 and want to find which triangle that enclose the point 0.1, 0.1. Are there routines sin delaunator to do that efficiently ?

[abellgithub]

No. There are fast point-in-triangle algorithms. You can look here:

https://github.com/PDAL/PDAL/blob/master/filters/HAGFilter.cpp

Though filtering by box containment before doing any multiply/divide would probably be advisable.

[lauraxinzhang]

@holmhaavard I'm a bit late to the game, but the way that triangles are stored in this particular implementation of the Delauney actually makes it very easy to "walk on a triangulation". This is because you can very easily find the neighbor triangle that shares a particular edge with. You get an average constant time access with it.

You can find a lot of resources on this with a quick google search. But here's the basic algorithm:

• You want to locate point P in the triangulation.
• Start from any triangle t, find point P0 that's in t. (centroid, for example)
• connect P and P0. Find the edge e in t that P-P0 intersects with
• Walk to the other triangle that shares e with t
• repeat.

To OP: thanks for this great library! It's very easily workable and made my life a lot easier.