Opened 10 years ago

Closed 8 years ago

#3610 closed enhancement (fixed)

New feature: Identify and properly set exterior ring of a polygon in OGRBuildPolygonFromEdges

Reported by: mrx Owned by: warmerdam
Priority: normal Milestone:
Component: Algorithms Version: unspecified
Severity: normal Keywords:
Cc:

Description

This patch identifies an exterior ring of a polygon in OGRBuildPolygonFromEdges. It compares envelope sizes and, if for any ring other than the current exterior (as assembled prior) the envelope size is strictly larger, it will swap that ring with the exterior. This works well with all real geometries. Though in theory there may be cases where interior ring and exterior ring have the same envelope (diamond in a circle), they are non-existant in geographic data (and in any case the result would be no worse than random assignment). This patch can be tested on NOAA ENC data, as an example see US5CA92M, feature RCID 1167.

In addition first line of this patch is a small optimization for cases where dfTolerance is set to 0.0 (as it is in S57Reader).

Attachments (3)

patch (2.0 KB) - added by mrx 10 years ago.
Proposed patch
US5CA92M.zip (529.2 KB) - added by mrx 10 years ago.
Sample cell to show the issue
patch1 (2.8 KB) - added by mrx 10 years ago.
Second patch with ring swap for polygons

Download all attachments as: .zip

Change History (10)

Changed 10 years ago by mrx

Attachment: patch added

Proposed patch

comment:1 Changed 10 years ago by warmerdam

Status: newassigned

Patch applied in trunk (r19790).

Can you provide more direct information on how I can fetch the indicated NOAA file?

comment:2 Changed 10 years ago by rburhum

Shouldn't the delete call be changed from

delete poPolygon;

to CPLFree(poPolygon) ?

Same for the memory allocation. Or am I missing something?

comment:3 Changed 10 years ago by warmerdam

no, poPolygon is an OGRPolygon object, and is created with new. It is a complex object with subobjects (ring geometries), and it is important that the real destructor be invoked to clean up the ring geometries.

It is a pity that the rings are all being cloned and the originals destroyed instead of just reassigning them to the new polygon but currently the OGRPolygon class has no mechanism to delete rings, or to seize ownership of them (the opposite of addRingDirectly()).

comment:4 Changed 10 years ago by mrx

Yep, it would be nice to be able to add rings directly. I am going to see if I can hack my copy of OGR to do that - if so, I'd be glad to offer a patch. As a shortcut, it may be possible to add a method to swap exterior ring with a given interior ring - while it may not be generally applicable, it would make this particular function a lot faster.

I am going to attache the test cell to this ticket, since I don't know if the current edition of this cell still manifests the issue - they may have rearranged the edges, I guess.

Changed 10 years ago by mrx

Attachment: US5CA92M.zip added

Sample cell to show the issue

Changed 10 years ago by mrx

Attachment: patch1 added

Second patch with ring swap for polygons

comment:5 Changed 10 years ago by mrx

I added another patch - if you don't mind the slightly hackish OGRPolygon::swapExteriorRing() - it would certainly cut down on wasted memory allocations.

comment:6 Changed 10 years ago by mrx

Just realized that it also might be possible to avoid creating a first polygon, instead storing all rings in an array - and then create polygon and add rings directly once the exterior ring was detected. This also would not require modifying polygon methods. Well, I am not going to "re-patch" this method unless you want me to :)

comment:7 Changed 8 years ago by Even Rouault

Resolution: fixed
Status: assignedclosed

r23323 /trunk/ (autotest/ogr/ogr_geom.py gdal/ogr/ograssemblepolygon.cpp): Avoid copying ring in OGRBuildPolygonFromEdges, and add testing of multi-ring polygon (#3610)

Note: See TracTickets for help on using tickets.