Lindley
August 18th, 2010, 11:35 AM
I need to compute the area of the region of intersection between two 2D triangles. (Well, actually, the total intersection between two sets of triangles, but let's start with just two.)
So far my research has pointed to a barycentric coordinate test as the fastest approach. This easily lets me test whether one tri is completely contained in the other, or has some of its vertices inside the other.
But there's a case which isn't covered by the simple point-in-triangle test: the six-point ("Jewish") star. Here, all six vertices are outside the other triangle, yet there's clearly lots of overlap.
I was wondering if anyone knows a simple, definitive rule for solving this problem. Otherwise, I'll just need to start figuring out conditions on barycentric coordinate signs and the like.
Incidentally, once I've found all points along the (convex) overlap region, I can use the area-of-convex-polygon formula to get the intersection area. Each of these points will either be a triangle vertex inside the other triangle, or an intersection of two triangle edges.
So far my research has pointed to a barycentric coordinate test as the fastest approach. This easily lets me test whether one tri is completely contained in the other, or has some of its vertices inside the other.
But there's a case which isn't covered by the simple point-in-triangle test: the six-point ("Jewish") star. Here, all six vertices are outside the other triangle, yet there's clearly lots of overlap.
I was wondering if anyone knows a simple, definitive rule for solving this problem. Otherwise, I'll just need to start figuring out conditions on barycentric coordinate signs and the like.
Incidentally, once I've found all points along the (convex) overlap region, I can use the area-of-convex-polygon formula to get the intersection area. Each of these points will either be a triangle vertex inside the other triangle, or an intersection of two triangle edges.