Checking which triangles intersect a convex hull

Question

I have a bunch of 2D triangles (i.e., in R²), as well as a 2D convex hull (represented as a set of linear constraints), and I need to check which of those triangles intersect the convex hull. What algorithms are there for doing this?

At a later stage, I might also need to generalize the problem to higher dimensions than 2D (i.e., out of a set of simplexes in R^d, check which of those intersect a convex hull in R^d), so if you know of an algorithm that can handle the general case that would also be nice.

Answer 1

You can solve the 2D problem in two steps:

• construct the vertices of the convex hull;

• intersect the triangles and the hull, which are both convex polygons (https://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring17/Lectures/cg-convexintersection.pdf). The time for intersection will be O(N) for a hull of N vertices.

If you need to do this for many triangles, a possibility is to decompose the hull in two monotone chains along along an axis, say X, and find the overlap range of the hull and every triangle by dichotomic search. This will lower the time to O(Log N + K) where K is the average number of sides of the hull in X-overlap with the triangles.