I hit this bug working on the WKT serialization/deserialization for the labelled array gsoc.
Take the following example with two polygons. The first multipolygon is a double-torus defined by a square ring between 1 and .75, and another square ring between .5 and .25. The other multipolygon is a single torus with an island, defined by a square between 1 and .75, and an inner square at .5.
Our contains_point
implementation bails when any hole contains the point, which is accurate for the double-torus, but incorrect for the single-torus-with-island:
>>> import pysal as ps
>>> double_torus = ps.cg.Polygon(parts= [[(-1, -1), (-1,1),(1,1),(1,-1)], #exterior square at 1
[(-.5,-.5), (-,5, .5),(.5,.5),(.5,-.5)]], #exterior square at .5
holes= [[(-.75, -.75),(-.75,.75),(.75,.75),(.75,-.75)], #hole square at .75
[(-.25,-.25),(-.25,.25),(.,25, .25),(.25,-.25)]]) #hole square at .25
>>> single_island_in_torus = ps.cg.Polygon(parts= [[(-1, -1), (-1,1),(1,1),(1,-1)], #exterior square at 1
[(-.5,-.5), (-,5, .5),(.5,.5),(.5,-.5)]], #exterior square at .5
holes= [[(-.75, -.75),(-.75,.75),(.75,.75),(.75,-.75)], #hole square at .75
]) #inner square is solid
>>> double_torus.contains_point((0,0)) #is hollow, so origin is not contained
False
>>> single_island_in_torus.contains_point((0,0)) #should contain origin, since the inner square is solid
False
Again, if any hole contains the point, the algorithm bails, meaning any concentric multi-polygon will have incorrect results for point-in-polygon searches.
In fact, I don't think we can do a correct point in polygon search on multipolygons without establishing a ring-hole nesting.
Like, take a point P related to a multipolygon M composed of 2 exterior rings, A,B and one hole, H. Let P be contained in B. Stating the rings in OGC style, if M := ((AH), B), then P in H is not sufficient to exclude P from M, since P in (B intersection H) implies P in M.
Also, no clear even-odd rule exists for rings with no topological sorting, since checking ring/hole membership of P in either M:= ((AH),B) or M:= (A, (BH)) is indeterminate; "P is contained in two exterior rings and one hole" is ambiguous about P and M, since we don't know whether H contains B.
Solution
Sort the rings of a polygon topologically and record them in OGC style. Then, conduct a level-set membership test, where a naive point-in-polygon ring test can be applied walking down the topological sorting. The "top" ring governs membership; if the "top" ring is a hole, the point is not inside. Otherwise, the point is inside.