Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

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

Search the Archive

Re: Area of Intersection of two planar polygons

  • To: mathgroup at smc.vnet.net
  • Subject: [mg112249] Re: Area of Intersection of two planar polygons
  • From: Valeri Astanoff <astanoff at gmail.com>
  • Date: Mon, 6 Sep 2010 06:38:32 -0400 (EDT)
  • References: <i5su76$p8d$1@smc.vnet.net>

On 4 sep, 09:58, Thomas Melehan <tpmele... at gmail.com> wrote:
> Does anyone have an algorithm for the area of the intersection of two
> planar polygons?
>
> TIA
>
> Tom=

Good day,

This is my -slow- way to do it with NIntegrate :

In[1]:=
halfLineCutsSegment[{{x0_?NumericQ, y0_?NumericQ},
 {x1_?NumericQ, y1_?NumericQ}},
{{x2_?NumericQ, y2_?NumericQ},
 {x3_?NumericQ, y3_?NumericQ}}]:=
 (x3 (y0-y1)+x0 (y1-y3)+x1 (-y0+y3))*
 (x3 (y0-y2)+x0 (y2-y3)+x2 (-y0+y3))> 0 &&
 (x2 (y0-y1)+x0 (y1-y2)+x1 (-y0+y2))*
 (x3 (-y0+y2)+x2 (y0-y3)+x0 (-y2+y3))> 0;

insideQ[pt:{_?NumericQ, _?NumericQ},
pol:{{_?NumericQ, _?NumericQ}..}]:=
 Module[{p,rp,tp},
 p = If[First[pol]==Last[pol],Most[pol],pol];
 rp = RotateLeft[p];
 tp = Transpose[{p,rp}];
 And@@(OddQ /@ (Count[tp,seg_ /;
 halfLineCutsSegment[{pt,#},seg]]& /@ (Mean /@ tp)))];

In[4]:= poly1 = {{20, 20}, {0, 20}, {0, 0}, {20, 0}, {5, 10}, {20,
20}};

In[5]:= insideQ[{10, 1}, poly1]

Out[5]= True

In[6]:= insideQ[{10, 10}, poly1]

Out[6]= False

In[7]:= poly2 = {{5, 0}, {20, 0}, {20, 10}, {5, 10}, {5, 0}};

In[8]:= xx1 = poly1[[All, 1]];
xx2 = poly2[[All, 1]];
yy1 = poly1[[All, 2]];
yy2 = poly2[[All, 2]];
xmin = Max[Min@xx1, Min[xx2]];
xmax = Min[Max@xx1, Max[xx2]];
ymin = Max[Min@yy1, Min[yy2]];
ymax = Min[Max@yy1, Max[yy2]];

In[16]:= NIntegrate[Boole[insideQ[{x, y}, poly1] && insideQ[{x, y},
poly2]],
 {x, xmin, xmax}, {y, ymin, ymax}, PrecisionGoal -> 3] // Timing

Out[16]= {26.141, 75.0074}


The exact area is of course 75

--
V.Astanoff


  • Prev by Date: Re: Help with differential equation
  • Next by Date: Re: locating overlow/underflow
  • Previous by thread: Area of Intersection of two planar polygons
  • Next by thread: Please help