28
$\begingroup$

Bug introduced in 10.0 and persisting through 12.0
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}]

A polygon and the points deemed to be inside it by RegionMember

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}]]]}]

A polygon and the points deemed to be inside it by RegionMember

Other observations based on a small number of cases (using V10.3):

  1. The mistaken region was always inside the convex hull of the actual polygon
  2. Problem goes away when using real numbers to define the polygon
$\endgroup$
  • $\begingroup$ With polygonPoints = N@polygonPoints works well. $\endgroup$ – Kuba Dec 19 '15 at 16:04
  • $\begingroup$ 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$ – Simon Woods Dec 19 '15 at 17:46
  • 16
    $\begingroup$ The incorrect result in the exact case is coming from an internal triangulation routine, Graphics`PolygonUtils`PolygonTriangulate[polygon]. $\endgroup$ – ilian Dec 19 '15 at 18:12
  • $\begingroup$ @ilian What a horrible bug. Has this issue been reported to WRI? $\endgroup$ – Ali Hashmi Jul 10 at 3:02
  • $\begingroup$ @AliHashmi Ok I just reported it. $\endgroup$ – M.R. Sep 8 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.