RE: [Algorithms] Tris intersection

[Robert D. <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