Efficient checking of whether a point is inside a large number of triangles in 2D

Question

I have implemented an algorithm to check whether a point is inside a triangle in 2D by calling the 1st algorithm in this question: how to determine if a point is inside a 2d triangle.

This algorithm works, but I think if I preprocess the triangle and use a smart data structure, I can make this efficient. I'm using about 10 million triangles. I think one way of making this fast is to compute bounding rectangles for the triangles and do a point in rectangle check, but I feel even this case can be made faster by making use of some data structure to only check for rectangles that are closeby.

Does such a data structure and algorithm exist?

Answer 1

The classical approach from computational geometry is to triangulate and then do point location, but it's a lot easier to just use a k-d tree, putting triangles that intersect the partitioning line of an interior tree node in that node so that they can be checked on the way down to the leaves.

Constructing the k-d tree is a recursive process. Given a list of triangles and a coordinate to focus on (x or y, alternating with each layer), find a separating line that is vaguely in the middle, by sampling randomly, by taking a median, or by some combination or sampling and taking a median. Gather the triangles whose points are all strictly less than the separation coordinate and use them to construct the left subtree. Gather the triangles whose points are all strictly greater than the separation coordinate and use them to construct the right subtree. Store the remaining triangles (the ones that intersect the coordinate line) in the root.

To query, test whether the point belongs to any of the triangle in the root. Then, if the point is less than the separation coordinate, check the left subtree. If the point is greater, check the right.