MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: area of intersection of 2 triangles

  • To: mathgroup at smc.vnet.net
  • Subject: [mg27994] Re: area of intersection of 2 triangles
  • From: Tomas Garza <tgarza01 at prodigy.net.mx>
  • Date: Wed, 28 Mar 2001 02:40:23 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Apparently there was no interest in this problem (other than Paul Lutus,
who only sketched a possible way to approach it). Actually, it is possible to
answer the question using a few functions from Tom Wickham-Jones' ExtendGraphics
package (I recommend buying his book Mathematica Graphics, but the package is available from MathSource).
The idea is simple: first, find the intersections of each of the three lines
in one of the triangles with each of the lines in the other one (use the 
function IntersectionPoint in the above package). These, plus the six triangle
vertices, give 15 points (except in degenerate cases). Second, find how many
and which of these 15 points belong to both triangles (use the function
PointInTriangle). Then the ConvexHull (again, a function in the package)
of this set determines the intersection polygon. Finally, use a result
recently discussed in this group ([mg27733] Re: [mg27712] How to calculate the
 area of a polygon?) to obtain the area of the intersection. 
If the group moderator allows it, a program to do this is as follows
(I'm not a very good programmer, but it works). The program starts with a couple 
of random triangles, but they may of course be substituted by actual given 
triangles.

In[1]:==
{a1, a2, a3, b1, b2, b3} ==
  Table[Random[Real, {0, 9}], {6}, {2}]; {t1,
    t2} == {{a1, a2, a3}, {b1, b2, b3}}; tris ==
  Show[Graphics[{Thickness[0.01], Hue[0.9], Line[{a1, a2, a3, a1}]}],
    Graphics[{Thickness[0.01], Hue[0.7], Line[{b1, b2, b3, b1}]}],
    PlotRange -> {{0, 10}, {0, 10}}, GridLines -> Automatic,
    DisplayFunction -> Identity];
lns1 == Line /@ KSubsets[t1, 2];
lns2 == ToImplicit /@ Line /@ KSubsets[t2, 2];
crossLines == Partition[Flatten[Outer[List, lns1, lns2]], 2];
pts == Select[
      Table[IntersectionPoint[crossLines[[j, 1]], crossLines[[j, 2]]], {j, 
1,
          Length[crossLines]}], # !== {\[Infinity], \[Infinity]} &];
inters == Show[Graphics[{PointSize[0.025], Point /@ pts}],
      DisplayFunction -> Identity];
grIntersections ==
    Show[tris, inters, PlotRange -> {{0, 10}, {0, 10}},
      GridLines -> Automatic, DisplayFunction -> Identity];
trint == Join[Select[t1, PointInTriangle[#, Polygon[t2]] ==== True &],
      Select[t2, PointInTriangle[#, Polygon[t1]] ==== True &],
      Complement[pts,
        Select[pts, (PointInTriangle[#, Polygon[t1]] &&
                  PointInTriangle[#, Polygon[t2]]) ==== False &]]];
hull == If[trint !== {}, ConvexHull[trint], {}];
If[hull ==== {}, (Print["The intersection is empty"];
      Show[tris, DisplayFunction -> $DisplayFunction]),
    convPoints == Part[trint, hull] /. {a_, b__} :> {a, b, a};
    interPoly == Line[convPoints];
arePol[n_] :==
      arePol[n - 1] +
        Area[Polygon[{convPoints[[1]], Last[Take[convPoints, n - 1]],
              convPoints[[n]]}]];
arePol[3] ==
      Area[Polygon[{convPoints[[1]], convPoints[[2]], convPoints[[3]]}]];
Print["The area of the intersection of the two triangles is ",
      arePol[Length[convPoints]]];
    Show[grIntersections, Graphics[{Thickness[0.015], Hue[0.8], interPoly}],
      DisplayFunction -> $DisplayFunction]];

This is certainly a very low complexity algorithm; there is just a lot of
paperwork to deal with.

Tomas Garza
Mexico City


  • Prev by Date: Re: Problem with Mathematica fonts in pdfLaTeX
  • Next by Date: NDSolve
  • Previous by thread: Re: area of intersection of 2 triangles
  • Next by thread: Corrupted notebooks