Bug introduced in 10.0 and persisting through 12.1
RegionMember
is new in 10.0
A commenter notes that the issue is with Graphics`PolygonUtils`PolygonTriangulate[polygon]
RegionMember
(new in V10) appears to have a bug. For some polygons it finds points that are clearly outside to be "members" of the region. This depends on the shape of the polygon in a way that is hard to pin down. Here is one example.
polygonPoints = {{0, 200},{100, 200},{100, 300},{200, 300},{200,
400},{250, 400},{250, 0},{200, 0},{200, 100},{0, 100}};
polygon = Polygon[polygonPoints];
polyQ = RegionMember[polygon]
testPoints = Table[{300 Random[], 450 Random[]}, {10000}];
Next let's see which test points RegionMember
finds to be inside the test polygon (blue points) and how it compares to actual polygon (gray region).
ListPlot[{testPoints, Select[testPoints, polyQ],polygonPoints},
PlotStyle -> {Red, Blue, {PointSize -> Large, Green}}, Prolog -> {Gray, polygon}]
Changing the polygon reveals a little bit about how the bug affects results in this particular case. The mistaken area appears to be below a line that connects two vertices; moving one of the vertices and redoing the test confirms this.
polygonPointsB = ReplacePart[polygonPoints, 1 -> {0, 150}];
polygonB = Polygon[polygonPointsB]
polyBQ = RegionMember[polygonB]
ListPlot[{testPoints, Select[testPoints, polyBQ], polygonPointsB},
PlotStyle -> {Red, Blue, {PointSize -> Large, Green}}, Prolog -> {Gray, polygonB},
Epilog -> {Green, Thick, Line[polygonPointsB[[{1, 4}]]]}]
Other observations based on a small number of cases (using V10.3):
- The mistaken region was always inside the convex hull of the actual polygon
- Problem goes away when using real numbers to define the polygon
polygonPoints = N@polygonPoints
works well. $\endgroup$polyQ // InputForm
reveals a difference between the exact and machine precision versions. For the latter it uses a MeshRegion, but for the former it contains an implicit member function which is presumably not quite correct. $\endgroup$Graphics`PolygonUtils`PolygonTriangulate[polygon]
. $\endgroup$