Polygon with 4 nested rings not broken up properly

[rengelkemeir@…]

I have a shapefile which has a set of 4 nested rings.

This polygon displays as a donut inside a donut in ArcMap, but as a disk inside a donut in my app.

The geometry says this feature has 2 parts. The first part is a polygon with 2 inner rings and the 2nd part is a polygon with just an exterior ring.

I would have expected each part to have one inner ring.

[rengelkemeir@…]

tar of shapefile exhibiting problem

[warmerdam]

I have confirmed the incorrect handling of this geometry.  I'm not sure 
when I'll get to fixing the problem though.  I didn't write the ring
classifying code in the OGR shapefile driver, and it might be quite hard
to fix up. 

[warmerdam]

Mateusz, 

Could you look into this when you get a chance.  It is the inner/outer ring
classification logic in the OGR Shapefile driver that is wonky.  This was
written by Radim so I am not too sure how it works.  

It might make sense to factor it out of the shapefile driver in a form that
could be used in other places at the same time it is fixed. 

I would call this issue medium priority.

[Mateusz Łoskot]

Bug 1217 tests

[Mateusz Łoskot]

Last days I analysed the problem and consulted with Frank.
Unfortunately, the Bug 1217 has not been fixed.
Here I'd like to present my (and Frank's) thoughts and notes I gathered about this issue.

The general conclusion is the SHPReadOGRObject function in the shape2ogr.cpp file does not run tests required to correctly classify inner/outer rings in multipart polygons.

Second issue is that the SHPReadOGRObject function classifies polygon rings according to coordinates orientation (CW - outer or CCW - inner). This assumption is incorrect when dealing with "dirty" shapefiles.
Example, the Stacks.shp file attached to this report by Richard *may*be* seen as  such dirty file.
Rings orientation is as follows:
1 - clockwise (biggest outer)
2 - counter-clockwise (biggest inner)
3 - counter-clockwise (smallest inner)
4 - clockwise (smallest outer)

Here, current classification algorithm assigns the ring 3 as an inner ring of the biggest outer ring 1, instead of classifying it as an inner of outer 4.
Also, in the Stacks example above, we can not be sure if ring 4 is outer or inner, similarly we can not be sure about ring 3, without checking geometric relation between those rings.

Next conclusion is that current algorithm depends on how inner rings are ordered in a shapefile.

The solution is to add heavy gemetric checks and also, if needed, sort inner/outer rings accordint the extent.

Here is Frank's idea discussed on the #gdal channel:

1. My hope was that outer rings (rings not contained in any other ring) would be seen as outer rings. 
2. Anything within an outer ring, but not inside any other ring would be an inner ring.
3. Any ring completely inside an inner ring, but with no other unclassified ring around it would be an outer ring, and so forth.
4. Sort of a winding number approach to inner/outer assignment. But that approach assumes a full polygon-in-polygon test for all polygons against each other.

The step 4 requires potentially heavy calculations.
The question is if OGR should expose users on low performance tests :-)

I also considered sorting rings against area and/or spatial extent.
Then the classification should run from  smallest to biggest ring in the collection to avoid situation that the outer ring of middle/smaller polygon will be assigned as the inner ring of the biggest polygon (biggest outer ring).
This situation may occure when rings have incorrect orientation, in example outer ring is CCW.

If anything above needs more clarification, please give me a note and I'll try to explain it better.

[rengelkemeir@…]

I think the handling of nested polygons should be geared towards proper files.
I actually have 2 shapefiles, one which contains the 4 level polygon and some other polygons for hole testing.  The 2nd shapefile was extracted from the first using ogr2ogr and became 'dirty' there.
I used shpdump to examine both files.  FOr the polygon in question the original file (created in ArcMap) had the order of the 3rd and 4 rings reversed:
1 - clockwise (biggest outer)
2 - counter-clockwise (biggest inner)
3 - clockwise (smallest outer)
4 - counter-clockwise (smallest inner)
However the results are the same.