3
$\begingroup$

I'm working on an algorithm which should check if two polygons, described by their vertex coordinates, are: one inside the other, are intersecting or are separated

image below describe this three cases: example

i'm thinking about how to do it but i'm not having any idea. Any suggestion?

$\endgroup$

closed as off-topic by MarcoB, user9660, dr.blochwave, C. E., bill s Nov 10 '15 at 2:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "The question is out of scope for this site. The answer to this question requires either advice from Wolfram support or the services of a professional consultant." – MarcoB, Community, dr.blochwave, C. E., bill s
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Are you sure this is the right place to ask such a question ? $\endgroup$ – Sektor Nov 9 '15 at 11:54
5
$\begingroup$
R1 = Polygon[{{1, 0}, {1, 1}, {0, 0}}];
R2 = Polygon[{{0, 1}, {1/3, 1/2}, {0, 1/2}}];

Graphics[{R1, Red, R2}, Frame -> True]

enter image description here

Catenate @ Map[RegionMember[R1, #] &, List @@ R2] // MemberQ[#, True] &

False

R3 = Polygon[{{0, 1}, {3/4, 1/2}, {0, 1/2}}];

Graphics[{R1, Red, R3}, Frame -> True]

enter image description here

Catenate @ Map[RegionMember[R1, #] &, List @@ R3] // MemberQ[#, True] &

True

"Inside the other"

Catenate @ Map[RegionMember[R1, #] &, List @@ R1] // FreeQ[#, False] &

True

$\endgroup$
  • $\begingroup$ many thanks, should help $\endgroup$ – TuoCuggino Nov 9 '15 at 12:20
  • 2
    $\begingroup$ This is no general solution, your code fails for all cases where the first polygon doesn't have any of it's veritces inside the second polygon. Swapping R1 and R3 results in a wrong answer. Some cases can't be solved e.g. R1 = {{-1, 0}, {0, 1}, {1, 3}, {1, 0}}; R2 = {{-1, -0.5}, {2, 3}, {4, 2}}; $\endgroup$ – paw Nov 9 '15 at 18:18
6
$\begingroup$

Using RegionIntersection and Area:

PolygonIntersectingQ[poly1_, poly2_] := Module[{m1, m2, area},
   {m1, m2} = MeshRegion[#, Polygon[Range@Length@#]] & /@ {poly1, poly2};
   area = Area@RegionIntersection[m1, m2];
   Switch[area,
    0, False,
    Area@m1, poly1,
    Area@m2, poly2,
    _, True]];

poly1 = {{-1, 0}, {0, 1}, {1, 3}, {1, 0}};
poly2 = {{-1, -0.5}, {2, 3}, {4, 2}};
PolygonIntersectingQ[poly1, poly2]

True

The function returns True if the polygons are intersecting, False if they are not intersecting and the inner polygon if one polygon is enclosed in the other.

$\endgroup$
  • $\begingroup$ How would you handle the "inside the other"-case? $\endgroup$ – eldo Nov 9 '15 at 12:25
  • $\begingroup$ @eldo should be good now. $\endgroup$ – paw Nov 9 '15 at 12:37
3
$\begingroup$

using this: https://mathematica.stackexchange.com/a/51425/2079

segsegintersectionQ[lines_] := Module[{
   md = Subtract @@ (Plus @@ # & /@ lines), 
   sub = Subtract @@ # & /@ lines, det}, det = -Det[sub];
  TrueQ[And @@ (Abs[#] <= 1 & /@ #)] &@(Det[{#[[1]], md}]/
       det & /@ ({#, Reverse@#} &@sub))]; 

and this: https://mathematica.stackexchange.com/a/9408/2079

testpoint[poly_, pt_] := 
 Round[(Total@
       Mod[(# - RotateRight[#]) &@(ArcTan @@ (pt - #) & /@ poly), 
        2 Pi, -Pi]/2/Pi)] != 0

Which[  Or @@ Flatten@Outer[segsegintersectionQ[{##}] & ,
 Partition[Append[poly1, First@poly1], 2, 1],
 Partition[Append[poly2, First@poly2], 2, 1], 1] ,
                                True ,
  testpoint[poly1, poly2[[1]]], True,
  testpoint[poly2, poly1[[1]]], True]

I haven't tested but I suspect this will be faster than the Region approaches.

(You could use Or instead of Which if you don't need to separately treat the inside cases.)

$\endgroup$

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