16
$\begingroup$

When trying to determine if two polygon objects overlap, I think the intuitive way to do this would be to use the RegionIntersection function to find the overlapping region, and Area to find the area of the overlap.

This works with two separated polygons,

{p1, p2} = {Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
   Polygon[1 + {{1, 0}, {2, 0}, {2, 1}, {1, 1}}]};
Graphics[{Red, p1, Blue, p2}]
RegionIntersection[p1, p2]
Area@%

enter image description here

(* EmptyRegion[2] *)
(* 0 *)

as well as for two polygons that share an edge,

{p1, p2} = {Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
   Polygon[{{1, 0}, {2, 0}, {2, 1}, {1, 1}}]};
Graphics[{Red, p1, Blue, p2}]
RegionIntersection[p1, p2]
Area@%

enter image description here

(* Line[{{1, 0}, {1, 1}}] *)
(* 0 *)

However, it doesn't work on these two simple triangles that clearly share an edge,

{p1, p2} = {Polygon[{{0., 0.354}, {-0.354, 0.}, {-0.707, 0.707}}], 
   Polygon[{{-0.707, -0.707}, {-0.354, 0.}, {-0.707, 0.707}}]};
Graphics[{Red, p1, Blue, p2}]
RegionIntersection[p1, p2]
Area@%

(* Polygon[{{-0.707, 0.707}, {-0.707, 0.707}, {-0.707, 0.707}}] *)

During evaluation of In[86]:= Area::nmet: Unable to compute the area of region Polygon[{{-0.707,0.707},{-0.707,0.707},{-0.707,0.707}}]. >>

(* Area[
 Polygon[{{-0.707, 0.707}, {-0.707, 0.707}, {-0.707, 0.707}}]] *)

First off, this is clearly the wrong answer for the intersection, as the polygons share the line segment {-0.354, 0.}, {-0.707, 0.707}, so the intersection should be a Line.

One workaround is to apply Rationalize to the Polygons before finding the intersection,

RegionIntersection[Rationalize@p1, Rationalize@p2]
Area@%
(* Line[{{-(707/1000), 707/1000}, {-(177/500), 0}}] *)
(* 0 *)

Another workaround is to reverse the coordinates for the second triangle,

RegionIntersection[p1, MapAt[Reverse, p2, {1}]]
Area@%
(* Line[{{-0.707, 0.707}, {-0.354, 0}}] *)
(* 0 *)

But I'm looking for a fool-proof, preferably fast way to do this.

So I ask you, is this a bug? And if so, what is the best way to determine if two polygons overlap?

I have this, hackish, method right now, but it is much slower than RegionIntersection, which is already pretty slow when there are hundreds of polygons to consider.

intersectQ[p1_, p2_] := 
 Chop[Area[RegionUnion[p1, p2]] - Total[Area /@ {p1, p2}]] =!= 0
intersectQ[p1, p2]
(* False *)

Edit

Here is another odd example of RegionIntersection bugging out in a related, but different, way. Here we have two triangles that intersect at a single point,

{p1, p2} = {Polygon[{{0.322, 0.363}, {0.116, 0.472}, {0.465, 
     0.885}}],
  Polygon[{{-0.116, 0.472}, {0.116, 0.472}, {0., 1.}}]};
Graphics[{Red, p1, Blue, p2}]
RegionIntersection[p1, p2]
Area@%
RegionIntersection[Rationalize@p1, Rationalize@p2]
Area@%

enter image description here

During evaluation of In[22]:= Part::partw: Part {2,3} of {{0.116,0.472},{0.116,0.472}} does not exist. >>

During evaluation of In[22]:= Set::partw: Part 3 of {{0.116,0.472},{0.116,0.472}} does not exist. >>

During evaluation of In[22]:= Part::partw: Part 3 of {{0.116,0.472},{0.116,0.472}} does not exist. >>

During evaluation of In[22]:= Set::partw: Part 3 of {{0.116,0.472},{0.116,0.472}} does not exist. >>

(* RegionIntersection[
 Polygon[{{-0.116, 0.472}, {0.116, 0.472}, {0., 1.}}], 
 Polygon[{{0.322, 0.363}, {0.116, 0.472}, {0.465, 0.885}}]] *)
(* 0 *)
(* Point[{29/250, 59/125}] *)
(* 0 *)
$\endgroup$
  • $\begingroup$ What version are you using? While I also get the degenerate polygon from using RegionIntersection on the triangles, Area@% does give 0., using 10.4. $\endgroup$ – Martin Ender Apr 11 '16 at 12:56
  • $\begingroup$ @MartinBüttner, well that is indeed odd. I'm using version 10.4 for linux $\endgroup$ – Jason B. Apr 11 '16 at 12:58
  • $\begingroup$ I'm on Windows 10. $\endgroup$ – Martin Ender Apr 11 '16 at 12:59
  • 1
    $\begingroup$ Linux always getting the shaft :-( $\endgroup$ – Jason B. Apr 11 '16 at 13:00
  • 5
    $\begingroup$ Sadly regions functionality involving set operations, in especially tormenting ways with Polygons and MeshRegions is so buggy, that it's hard not to run into bugs with free-form input. Problems vary from odd representation and inability to compute values to incorrect results and outright repeatable kernel crashes. Practically every time I try to do polygon intersections or similar operations, I end up writing a new bug report and have to abandon my approach at problem using this functionality. I really wish these problems will eventually go away... $\endgroup$ – kirma Apr 11 '16 at 16:38
3
$\begingroup$

For the examples given in the OP, this is fixed as of version 11.0

{p1, p2} = {Polygon[{{0., 0.354}, {-0.354, 0.}, {-0.707, 0.707}}], 
   Polygon[{{-0.707, -0.707}, {-0.354, 0.}, {-0.707, 0.707}}]};
Graphics[{Red, p1, Blue, p2}]
RegionIntersection[p1, p2]
Area@%

enter image description here

{p1, p2} = {Polygon[{{0.322, 0.363}, {0.116, 0.472}, {0.465, 0.885}}],
    Polygon[{{-0.116, 0.472}, {0.116, 0.472}, {0., 1.}}]};
Graphics[{Red, p1, Blue, p2}]
RegionIntersection[p1, p2]
Area@%

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.