6
$\begingroup$

Playing around with some of the answers in the question How to check if a 2D point is in a polygon? I noticed that:

Graphics`Mesh`InPolygonQ[poly,pt]

Displays different behavior than the procedure that explicitly uses winding numbers (where a non-zero winding number implies polygon inclusion), for example the function in rm -rf♦'s answer to the aforementioned question:

inPolyQ[poly_, pt_] := Graphics`Mesh`PointWindingNumber[poly, pt] =!= 0

We can see this in the case where we define a self-intersecting polygon that has a "hole" in it:

PointWindingNumberInPolygonQ[poly_, pt_] := Graphics`Mesh`PointWindingNumber[poly, pt] =!= 0;

numRandPoints = 10^4;

testPolygon = {{65.4`, 439.5`}, {233.4`, 524.5`}, {364.40000000000003`, 433.5`}, {382.40000000000003`, 377.5`}, {354.40000000000003`, 293.5`}, {258.40000000000003`, 239.5`}, {94.4`, 207.5`}, {40.400000000000006`, 271.5`}, {18.400000000000002`, 356.5`}, {149.4`, 383.5`}, {187.4`, 330.5`}, {199.4`, 258.5`}, {136.4`, 130.5`}};

boundingBoxCoordinates = {{Min[testPolygon[[All, 1]]], Min[testPolygon[[All, 2]]]}, {Min[testPolygon[[All, 1]]], Max[testPolygon[[All, 2]]]}, {Max[testPolygon[[All, 1]]], Max[testPolygon[[All, 2]]]}, {Max[testPolygon[[All, 1]]], Min[testPolygon[[All, 2]]]}};

randomPoints = Table[{RandomReal[{Min[boundingBoxCoordinates[[All, 1]]], Max[boundingBoxCoordinates[[All, 1]]]}], RandomReal[{Min[boundingBoxCoordinates[[All, 2]]], Max[boundingBoxCoordinates[[All, 2]]]}]}, {k, 1, numRandPoints}];


windingNumPointsInPolygon = {};
inPolygonQPointsInPolygon = {};

For[i = 1, i <= Length[randomPoints], i++,

  If[PointWindingNumberInPolygonQ[testPolygon, randomPoints[[i]]] == True,
    windingNumPointsInPolygon = Append[windingNumPointsInPolygon, randomPoints[[i]]];
  ];

 If[Graphics`Mesh`InPolygonQ[testPolygon, randomPoints[[i]]] == True,
    inPolygonQPointsInPolygon = Append[inPolygonQPointsInPolygon, randomPoints[[i]]];
 ];

];


Graphics[Polygon[testPolygon]]
ListPlot[windingNumPointsInPolygon]
ListPlot[inPolygonQPointsInPolygon]

Notice how - 

inPolyQ[poly_, pt_] := Graphics`Mesh`PointWindingNumber[poly, pt] =!= 0

Counts points inside the polygon "hole" as being inside the hole, while - 

Graphics`Mesh`InPolygonQ[poly,pt]

Counts points inside the polygon "hole" as being outside the polygon, consistent with the shading for -

Graphics[Polygon[testPolygon]]

How can we characterize the behavior/algorithm of InPolygonQ? While I can understand how the winding number test method works, the trouble is that inPolygonQ is an undocumented function that doesn't give me any hints as to what it is doing.

|improve this question
$\endgroup$
  • $\begingroup$ Perhaps there is some triangulation involved along the way? $\endgroup$ – Yves Klett Sep 17 '13 at 4:24
4
$\begingroup$

The winding number is 0 outside the polygon, -1 in the non-self-intersecting region and -2 in the hole. So to exclude points inside the hole you would just test for the winding number being odd, rather than not equal to zero:

inPolyQ[poly_, pt_] := OddQ @  Graphics`Mesh`PointWindingNumber[poly, pt]
|improve this answer
$\endgroup$
  • $\begingroup$ Is it strictly true that the winding number will always be even if we're inside a hole? When will the winding number be even and greater than -2? $\endgroup$ – Avi Sep 17 '13 at 8:27
  • 1
    $\begingroup$ @Avi, I think the winding number must always increase or decrease by 1 when you cross the polygon boundary, so holes will always have an even winding number. $\endgroup$ – Simon Woods Sep 17 '13 at 8:48
  • 1
    $\begingroup$ That's a good point, I'm just curious now what holes with higher winding numbers look like. $\endgroup$ – Avi Sep 17 '13 at 8:56

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.