Wrong OGR2OGR conversion

[vitali@…]

Wrong conversion to shapefile.

OGR2OGR utility converts vector data into shapefile in a wrong way. Here is a description of the problem.

I have a shapefile, for example with a polygon and two holes (see attached figure.jpg , holes are numbered as hole 1 and hole 2).

Ordering is CW for exterior and CCW for interiors, see the shpdump for initial file:

Shapefile Type: Polygon   # of Shapes: 1

File Bounds: (       0.000,       0.000,0,0)
         to  (       5.000,       5.000,0,0)

Shape:0 (Polygon)  nVertices=15, nParts=3
  Bounds:(       0.000,       0.000, 0, 0)
      to (       5.000,       5.000, 0, 0)
     (       0.000,       0.000, 0, 0) Ring 
     (       0.000,       5.000, 0, 0)  
     (       5.000,       5.000, 0, 0)  
     (       5.000,       0.000, 0, 0)  
     (       0.000,       0.000, 0, 0)  
   + (       3.000,       2.000, 0, 0) Ring 
     (       2.000,       2.000, 0, 0)  
     (       2.000,       1.000, 0, 0)  
     (       3.000,       1.000, 0, 0)  
     (       3.000,       2.000, 0, 0)  
   + (       3.000,       2.000, 0, 0) Ring 
     (       4.000,       2.000, 0, 0)  
     (       4.000,       3.000, 0, 0)  
     (       3.000,       3.000, 0, 0)  
     (       3.000,       2.000, 0, 0)  

Now lets convert this file from SHP to SHP (Initially I got that bug after converting from TAB to SHP, but it doesn’t matter, bug is present when converting from SHP to SHP).

After convertation shpdump gives the next result:

Shapefile Type: Polygon   # of Shapes: 1

File Bounds: (       0.000,       0.000,0,0)
         to  (       5.000,       5.000,0,0)

Shape:0 (Polygon)  nVertices=15, nParts=3
  Bounds:(       0.000,       0.000, 0, 0)
      to (       5.000,       5.000, 0, 0)
     (       0.000,       0.000, 0, 0) Ring 
     (       0.000,       5.000, 0, 0)  
     (       5.000,       5.000, 0, 0)  
     (       5.000,       0.000, 0, 0)  
     (       0.000,       0.000, 0, 0)  
   + (       3.000,       2.000, 0, 0) Ring 
     (       2.000,       2.000, 0, 0)  
     (       2.000,       1.000, 0, 0)  
     (       3.000,       1.000, 0, 0)  
     (       3.000,       2.000, 0, 0)  
   + (       3.000,       2.000, 0, 0) Ring 
     (       3.000,       3.000, 0, 0)  
     (       4.000,       3.000, 0, 0)  
     (       4.000,       2.000, 0, 0)  
     (       3.000,       2.000, 0, 0)  

As you see the hole 2 becomes a usual polygon because of CW coordinate sequence ordering after conversion, but in initial file it was a hole with CCW ordering!!!

So, my deduction is the bug appears during OGR2OGR conversion when in initial data two holes touch each other in one polygon or multipolygon....

This wrong behaviour is quite critical for java shapefile library for example. It considers this wrong ring as a polygon in multipolygon, not as a hole in polygon.

See the test_data.zip package attached:

• touched_holes.shp – initial valid file
• touched_holes_OGR.shp - after OGR2OGR conversion with wrong geometries

---

Vitali Diatchkov Oy Arbonaut LTD Finland

[warmerdam]

Mateusz,

There is quite a block of code in the the Shapefile OGR driver for analysing the rings in a shapefile polygon to determine which are inner or outer rings. I think this logic is failing in the quoted situation.

I think we have lost the external url in the bugzilla to trac conversion, but you can dig it out of the bugzilla database which should still be online.

[mloskot]

I suppose this issue may be related to the Ticket #1217 in some way.

[mloskot]

I contacted Vitali directly asking for files that he mentioned in the report but are missing.

[mloskot]

Package with test data

[mloskot]

Picture presenting polygon with holes

[warmerdam]

SHPRewindObject() from gdal/ogr/ogrsf_frmts/shape/shpopen.c has been "upstreamed" to the home Shapelib package.

[mloskot]

2 shapefiles with test polygons including 1 outer and 5 connected inner rings

[mloskot]

Drawing presents polygons used in 5 holes test

[mloskot]

5 holes test translation output shapefiles, generated using patched OGR.

[mloskot]

Original touched_holes.shp and translation result after fixed OGR

[mloskot]

Drawing presents test of 2 diamonds connected but not in start point of both rings

[mloskot]

Drawing presents test of 2 diamonds connected in start point of rings

[mloskot]

The problem with incorrectly determined inner/outer rings was in SHPRewindObject() from shpopen.c. It's now fixed (r11689).

The SHPRewindObject() function tries to determine spatial relation between every polygon and distinguish outer ring and inner rings. Next, it checks if all inner rings are counter-clockwise (according to the  Shapefile specification ).

The problem was that ring-to-ring test was executed in isolation from other rings and test results, but the final result was collected during all subsequent tests. A ring is tested using  point-in-polygon procedure (based on crossing number algorithm), where test point is first a vertex of tested ring. If point is in another ring, then the tested ring is assumed to be inner to that another ring.

In result, if there are: A - outer and B, C - inner rings and B and C are connected in some vertex, the tests results are (F - false, T - true):

• A inner of B -> F
• A inner of C -> F

F and F -> F - A is confirmed as outer ring

• B inner of A -> T
• B inner of B -> T or F - here random result depends on if test point is a common point or not (the main source of problem), assuming we test common vertex -> T

T and T -> F - even number of T results gives F, because this test is based on ray crossing number algorithm of point-in-polygon test. Here, FALSE is incorrect, because B is an inner ring in the bigger picture of 3 rings of Shapefile.

• C inner of A -> T
• C inner of B -> again, result is random but let's assume it's F here

T and F -> T - because of odd number of T results.

Finally, ring B as being incorrectly detected as not an inner ring, converted from counter-clockwise to clockwise, what breaks the correct structure of Shapefile object.

According to these pretty big number of tests I run, the buggy behavior of OGR was caused by testing common vertex of two rings for point-in-polygon. In order to avoid testing common vertex, I changed the algorithm to not to test vertex but middle point of first segment of tested ring.

So, (from the test above), testing if B is inside C, middle point of 1st segment of B is taken and tested if inside C. This solution ensure us that two real inner rings having common vertex, won't be incorrectly determined as inner and outer. The specification ensures that one ring do not adhere in segment to another ring.

[mloskot]

Dirty drawing presents rings tests explained in my long comment.

[mloskot]

The fix for this bug also applies to the Ticket #1415. As I tested, that issue has been fixed as well.

[mloskot]

2 touching diamonds inside outer ring