Triangle-triangle intersection in 2D

[Lindley]

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.

[D_Drmmr]

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.

How about looking at the points where the sides of the different triangles intersect. If the triangles intersect, their sides must intersect as well, so this approach should always work. Not sure how it will work out performance wise, though.

[Zachm]

See this page on polygon intersection area (+code in C and java).

Regards,
Zachm

[egul]

Hi Lindley ,

I find your message while searcing the algorithm for fingding the intersection area of two triangles. There are lots of documantry about this but anyone of them dont help me and i am lost. Could you help me to find my way ?

If you interest i would be greatfull.

sincerely

[egul]

Is there anybody to help for this problem ? it is about my final project and dont have much time.I really need your help.

[Lindley]

Unfortunately I don't think I ever finished solving this problem; instead I modified my approach to take an entirely different tack.

[egul]

Thank you again for your interest. but as you see i am still verdant of matlab programing. maybe you can help me at least about how to compute the convex hull of this two triangle in the code.

clc
clear all




P(1, = [0.9 2.1];
P(2, = [2.8 5.2];
P(3, = [5.7 2.3];




Q(:, = ...
[2.7 1.1
5.6 4.1
8.0 1.8];




X = [P(:,1)
P(1,1)];

Y = [P(:,2)
P(1,2)];

line(X,Y)



A = [Q(:,1)
Q(1,1)];

B = [Q(:,2)
Q(1,2)];

line(A,B)

[Daniel_Wu]

Hello Lindley,

I am 1st PhD student, and recently I have worked on how to determine the intersection points of triangles. So could you please do me a favor? Thank you so much.