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@%
(* 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@%
(* 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@%
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 *)
RegionIntersection
on the triangles,Area@%
does give0.
, using 10.4. $\endgroup$Polygon
s andMeshRegion
s 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$