Opened 13 years ago

Closed 12 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:


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 13 years ago.
Proposed patch (529.2 KB ) - added by mrx 13 years ago.
Sample cell to show the issue
patch1 (2.8 KB ) - added by mrx 13 years ago.
Second patch with ring swap for polygons

Download all attachments as: .zip

Change History (10)

by mrx, 13 years ago

Attachment: patch added

Proposed patch

comment:1 by warmerdam, 13 years ago

Status: newassigned

Patch applied in trunk (r19790).

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

comment:2 by rburhum, 13 years ago

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 by warmerdam, 13 years ago

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 by mrx, 13 years ago

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.

by mrx, 13 years ago

Attachment: added

Sample cell to show the issue

by mrx, 13 years ago

Attachment: patch1 added

Second patch with ring swap for polygons

comment:5 by mrx, 13 years ago

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 by mrx, 13 years ago

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 by Even Rouault, 12 years ago

Resolution: fixed
Status: assignedclosed

r23323 /trunk/ (autotest/ogr/ 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.