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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Are you sure this is the right place to ask such a question ? $\endgroup$ Commented Nov 9, 2015 at 11:54

3 Answers 3

Reset to default
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

Improve this answer
$\endgroup$
1
  • 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$ Commented Nov 9, 2015 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How would you handle the "inside the other"-case? $\endgroup$ Commented Nov 9, 2015 at 12:25
  • $\begingroup$ @eldo should be good now. $\endgroup$ Commented Nov 9, 2015 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.)

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.