Opened 14 years ago

Closed 12 years ago

#976 closed defect (fixed)

Wrong OGR2OGR conversion

Reported by: vitali@… Owned by: Mateusz Łoskot
Priority: high Milestone: 1.4.2
Component: default Version: unspecified
Severity: major Keywords: hole polygon ring shapefile
Cc: warmerdam

Description (last modified by Mateusz Łoskot)

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

Attachments (10)

test_data.zip (4.2 KB) - added by Mateusz Łoskot 12 years ago.
Package with test data
figure.jpg (3.6 KB) - added by Mateusz Łoskot 12 years ago.
Picture presenting polygon with holes
5holes_test.zip (1.5 KB) - added by Mateusz Łoskot 12 years ago.
2 shapefiles with test polygons including 1 outer and 5 connected inner rings
5holes_test.jpg (211.0 KB) - added by Mateusz Łoskot 12 years ago.
Drawing presents polygons used in 5 holes test
5holes_test_results.zip (1.7 KB) - added by Mateusz Łoskot 12 years ago.
5 holes test translation output shapefiles, generated using patched OGR.
touched_holes_after_fix.zip (1.3 KB) - added by Mateusz Łoskot 12 years ago.
Original touched_holes.shp and translation result after fixed OGR
2diamonds.jpg (181.8 KB) - added by Mateusz Łoskot 12 years ago.
Drawing presents test of 2 diamonds connected but not in start point of both rings
2diamonds_in_common_vertex.jpg (169.0 KB) - added by Mateusz Łoskot 12 years ago.
Drawing presents test of 2 diamonds connected in start point of rings
rings_test.jpg (355.0 KB) - added by Mateusz Łoskot 12 years ago.
Dirty drawing presents rings tests explained in my long comment.
2diamonds_test.zip (1.3 KB) - added by Mateusz Łoskot 12 years ago.
2 touching diamonds inside outer ring

Download all attachments as: .zip

Change History (19)

comment:1 Changed 13 years ago by warmerdam

Cc: warmerdam added
Description: modified (diff)
Milestone: 1.4.2
Owner: changed from warmerdam to Mateusz Łoskot
Priority: highesthigh

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.

comment:2 Changed 13 years ago by Mateusz Łoskot

Keywords: hole polygon ring shapefile added

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

comment:3 Changed 13 years ago by Mateusz Łoskot

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

comment:4 Changed 13 years ago by Mateusz Łoskot

Status: newassigned

Changed 12 years ago by Mateusz Łoskot

Attachment: test_data.zip added

Package with test data

Changed 12 years ago by Mateusz Łoskot

Attachment: figure.jpg added

Picture presenting polygon with holes

comment:5 Changed 12 years ago by Mateusz Łoskot

Description: modified (diff)

comment:6 Changed 12 years ago by Mateusz Łoskot

Description: modified (diff)

comment:7 Changed 12 years ago by warmerdam

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

Changed 12 years ago by Mateusz Łoskot

Attachment: 5holes_test.zip added

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

Changed 12 years ago by Mateusz Łoskot

Attachment: 5holes_test.jpg added

Drawing presents polygons used in 5 holes test

Changed 12 years ago by Mateusz Łoskot

Attachment: 5holes_test_results.zip added

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

Changed 12 years ago by Mateusz Łoskot

Attachment: touched_holes_after_fix.zip added

Original touched_holes.shp and translation result after fixed OGR

Changed 12 years ago by Mateusz Łoskot

Attachment: 2diamonds.jpg added

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

Changed 12 years ago by Mateusz Łoskot

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

comment:8 Changed 12 years ago by Mateusz Łoskot

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.

Changed 12 years ago by Mateusz Łoskot

Attachment: rings_test.jpg added

Dirty drawing presents rings tests explained in my long comment.

comment:9 Changed 12 years ago by Mateusz Łoskot

Resolution: fixed
Status: assignedclosed

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

Changed 12 years ago by Mateusz Łoskot

Attachment: 2diamonds_test.zip added

2 touching diamonds inside outer ring

Note: See TracTickets for help on using tickets.