Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
Perhaps there is some triangulation involved along the way? –  Yves Klett Sep 17 '13 at 4:24
add comment

1 Answer

up vote 3 down vote accepted

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]
share|improve this answer
    
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? –  Avi Sep 17 '13 at 8:27
1  
@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. –  Simon Woods Sep 17 '13 at 8:48
1  
That's a good point, I'm just curious now what holes with higher winding numbers look like. –  Avi Sep 17 '13 at 8:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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