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