Ticket #976 (closed defect: fixed)

Opened 3 years ago

Last modified 1 year ago

Wrong OGR2OGR conversion

Reported by: vitali@arbonaut.com Assigned to: mloskot
Priority: high Milestone: 1.4.2
Component: default Version: unspecified
Severity: major Keywords: hole polygon ring shapefile
Cc: warmerdam

Description (Last modified by mloskot)

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

test_data.zip (4.2 kB) - added by mloskot on 05/31/07 14:53:34.
Package with test data
figure.jpg (3.6 kB) - added by mloskot on 05/31/07 15:11:34.
Picture presenting polygon with holes
5holes_test.zip (1.5 kB) - added by mloskot on 06/21/07 16:08:30.
2 shapefiles with test polygons including 1 outer and 5 connected inner rings
5holes_test.jpg (211.0 kB) - added by mloskot on 06/21/07 16:09:07.
Drawing presents polygons used in 5 holes test
5holes_test_results.zip (1.7 kB) - added by mloskot on 06/21/07 16:14:13.
5 holes test translation output shapefiles, generated using patched OGR.
touched_holes_after_fix.zip (1.3 kB) - added by mloskot on 06/21/07 16:22:11.
Original touched_holes.shp and translation result after fixed OGR
2diamonds.jpg (181.8 kB) - added by mloskot on 06/21/07 16:26:27.
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 mloskot on 06/21/07 16:27:10.
Drawing presents test of 2 diamonds connected in start point of rings
rings_test.jpg (355.0 kB) - added by mloskot on 06/21/07 17:19:58.
Dirty drawing presents rings tests explained in my long comment.
2diamonds_test.zip (1.3 kB) - added by mloskot on 06/21/07 17:33:42.
2 touching diamonds inside outer ring

Change History

04/02/07 23:30:30 changed by warmerdam

  • priority changed from highest to high.
  • owner changed from warmerdam to mloskot.
  • description changed.
  • cc set to warmerdam.
  • milestone set to 1.4.2.

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.

04/07/07 08:35:39 changed by mloskot

  • keywords set to hole polygon ring shapefile.

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

04/25/07 14:42:49 changed by mloskot

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

04/25/07 14:42:54 changed by mloskot

  • status changed from new to assigned.

05/31/07 14:53:34 changed by mloskot

  • attachment test_data.zip added.

Package with test data

05/31/07 15:11:34 changed by mloskot

  • attachment figure.jpg added.

Picture presenting polygon with holes

05/31/07 15:15:17 changed by mloskot

  • description changed.

06/14/07 10:20:19 changed by mloskot

  • description changed.

06/21/07 11:58:58 changed by warmerdam

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

06/21/07 16:08:30 changed by mloskot

  • attachment 5holes_test.zip added.

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

06/21/07 16:09:07 changed by mloskot

  • attachment 5holes_test.jpg added.

Drawing presents polygons used in 5 holes test

06/21/07 16:14:13 changed by mloskot

  • attachment 5holes_test_results.zip added.

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

06/21/07 16:22:11 changed by mloskot

  • attachment touched_holes_after_fix.zip added.

Original touched_holes.shp and translation result after fixed OGR

06/21/07 16:26:27 changed by mloskot

  • attachment 2diamonds.jpg added.

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

06/21/07 16:27:10 changed by mloskot

  • attachment 2diamonds_in_common_vertex.jpg added.

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

06/21/07 17:19:04 changed by 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.

06/21/07 17:19:58 changed by mloskot

  • attachment rings_test.jpg added.

Dirty drawing presents rings tests explained in my long comment.

06/21/07 17:20:53 changed by mloskot

  • status changed from assigned to closed.
  • resolution set to fixed.

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

06/21/07 17:33:42 changed by mloskot

  • attachment 2diamonds_test.zip added.

2 touching diamonds inside outer ring