RE: [Algorithms] Tris intersection
Brought to you by:
vexxed72
Menu
▾
▴
RE: [Algorithms] Tris intersection
|
From: Steve W. <Ste...@im...> - 2000-07-25 02:27:05
|
Oh...your right...checking to see if any of the line segments intersect would be a better test. R&R > From: Robert Dibley [mailto:RD...@ac...] > > This is not valid for all cases, since it is possible to have two > intersecting triangles where none of the vertices of either > triangle are in > the other one ... like this > > a > |\ > | \ > x---+--\------y > | | \ / > | | \ / > | | \/ > | | /\ > | | / \ > | | / \ > | | / \ > | | / \ > | |/ \ > | / \ > | /| \ > | / | \ > |/ b---------------c > z > > in which case no point will give you the same area when used > to make three > more triangles. > > The only guaranteed way I know is to test each edge to see if > the other > triangle is completely 'outside' it, which simply requires three > cross-products for each case, and you must test all six edges > to be certain > that you haven't missed one. I'm sure there must be an > easier way, but I've > never bothered to figure one out. > > Robert > > -----Original Message----- > From: Steve Wood [mailto:Ste...@im...] > Sent: 24 July 2000 03:59 > To: 'gda...@li...' > Subject: RE: [Algorithms] Tris intersection > > > I think the best way to find if the triangles intersect is to > take the 3 > vertexes from each triangle one at a time and use it to > divide the other > triangle up into three separate triangles (geometry now not > math). If the > sum of the area of the three triangles is equal to the area > of the whole > triangle then the triangles intersect (OK, put away your > thought compass and > do the math). You will need to do this 6 times, 3 times for each > triangle... Once you find a vertex where the areas are equal > then they > intersect and you won't have to do the rest of them. > > It's impossible to illustrate with ansii characters so in > your mind draw a > line from point p which represents one of the vertices from the other > triangle to each vertex a, b, and c to divide the triangle into 3 > triangles...add up the sum of the three triangles, apc, bpa, > cpb and compare > it to the area of abc. If They are equal then the point is > inside, or on > the triangle (be sure to allow some margin of error for > rounding). Sound > like a plan? > > a intersects a does not intersect > |\ |\ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | . \ | \ . > | p \ | \ p > | \ | \ > |___________\ |___________\ > c b c b > > > If it solves analytic geometry problems to relax after 10 > hours of straight > TFC and Q3A-CTF then it's, > Rockn-Roll > > > > -----Original Message----- > > From: Jeffrey C [mailto:pl...@as...] > > Sent: Sunday, July 23, 2000 5:54 PM > > To: gda...@li... > > Subject: [Algorithms] Tris intersection > > > > > > Hi, > > > > Anyone could tell me a quick way to know whether 2 triangle > > that lie on the same plane > > intersect each other? > > Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), > > here is some example that the > > triangles intersect each other. > > > > |\ /| > > | / B| > > | -\-- > > |___\ > > A > > > > /| > > / | > > / B| > > / | > > / |\ | > > /--| \- > > |A \ > > ---- > > > > > > > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
