7

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?

Community
  • 1
  • 1
dev_nut
  • 2,476
  • 4
  • 29
  • 49
  • 2
    are the triangles overlapping a lot or are they well separated? – Henry Mar 31 '17 at 17:29
  • Most of the time, they won't overlap, but they can overlap in some sense. So, an answer for when they don't overlap is also useful. – dev_nut Mar 31 '17 at 17:48
  • Could you give more context? What do you mean exactly: check if a point is in at least one triangle, is in all triangles, get the number of triangles it is in? Are the triangles small w.r.t the space you are working in? Do you need to do this for just one point or you have to then iterate for millions of points? – Adrien Apr 01 '17 at 16:00
  • Well, I will do it for millions of points, but that doesn't add anything to the question. As that will just multiply the complexity. I think it is clear, that I check a point in a million triangles. The size of the triangles are arbitrary, they can be big or small. – dev_nut Apr 01 '17 at 18:14
  • I now noticed that I answered this same question over at Computer Science Stack Exchange. Might be worth to check that page too [here](https://cs.stackexchange.com/questions/98568/similar-to-point-location) although my approach is very different. – Dozed12 Oct 25 '18 at 21:36

1 Answers1

5

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.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120