`contains_point` cannot handle nested exterior rings.

[ljwolf]

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.

[ljwolf]

Alternatively, this is not really commonly used in the library, so I'm open to non-head-on approaches to resolving this.

[ljwolf]

And, I'm not sure exactly if that polygon is considered valid via OGC? so, if it's invalid, it's okay that the result is "wrong", but I would want to warn the user that the result is nonsense.

[ljwolf]

It's a valid OGC polygon, but maybe not simple features.

Regardless, I'll be working on this.