CODEWITHSUNDEEP
c++mathgeometryintersection
Mary Ellen Bench
Mary Ellen Bench

Reputation: 589

Triangle Triangle Overlap (But not edges)

I've found a nice algorithm to check tri/tri intersections, but I'd like it to fail if they only meet at a point along an edge or edge (no overlap). Basically want to overlap, and touch is not enough.

Anyone know how to adjust it?

http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/opttritri.txt

ex. should fail

float a1[3] = { 0, 0, 0 }; 
float a2[3] = { 2, 0, 0 }; 
float a3[3] = { 0, 1, 0 }; 
float b1[3] = { 0, 0, 0 }; 
float b2[3] = { 2, 0, 0 }; 
float b3[3] = { 0, -1, 0 }; 

bool inters = NoDivTriTriIsect(a1, a2, a3, b1, b2, b3);

Upvotes: 0

Views: 1839

Answers (1)

kamjagin
kamjagin

Reputation: 3654

A neat solution and an ad-hoc solution come to mind :). The ad-hoc one just adds additional tests to identify the edge-only-overlaps. The neat one directly computes the area of the overlap and says that the triangles intersect if area>0

The neater Area-of-overlap approach: Sutherland-Hodgman algorithm produce a polygon of the triangle-triangle overlap. And then just compute polygon area (How do I calculate the area of a 2d polygon?) (https://math.stackexchange.com/questions/154628/find-the-area-of-overlap-of-two-triangles)

If you prefer an ad-hoc solution via filtering cases: first find overlapping borders by parameterising the edges as lines and look for lines with the same parameters. Then check if a point just above and below the starting point of the shortest edge is in both triangles. (http://www.blackpawn.com/texts/pointinpoly/default.html). If both points are in only one of them, then they only overlap by an edge.

Upvotes: 1

Related Questions