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.