# Behavior of GraphicsMeshInPolygonQ with self-intersecting polygons

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

GraphicsMeshInPolygonQ[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_] := GraphicsMeshPointWindingNumber[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_] := GraphicsMeshPointWindingNumber[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[GraphicsMeshInPolygonQ[testPolygon, randomPoints[[i]]] == True,
inPolygonQPointsInPolygon = Append[inPolygonQPointsInPolygon, randomPoints[[i]]];
];

];

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


Notice how -

inPolyQ[poly_, pt_] := GraphicsMeshPointWindingNumber[poly, pt] =!= 0


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

GraphicsMeshInPolygonQ[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.

-
Perhaps there is some triangulation involved along the way? – Yves Klett Sep 17 '13 at 4:24

inPolyQ[poly_, pt_] := OddQ @  GraphicsMeshPointWindingNumber[poly, pt]