[geos-devel] Bug in GEOS polygonizer

Mika Heiskanen mika.heiskanen at fmi.fi
Mon Mar 10 06:33:16 PDT 2014


On 03/07/2014 08:57 PM, Sandro Santilli wrote:
> You don't get the polygon twice, you get the _ring_ twice,
> once with the role of a shell (outer ring) and one with the
> role of an hole (inner ring).

[I'm including the above quote to make it clear for any new reader
  that is no bug in GEOS.]

> You may see if Martin Davis ever added that support to the JTS
> side of things. If so, it would be nice to port over.

Did not find any such code either in JTS nor in GEOS.

> In PostGIS you can find a function that does what you need,
> it's called "BuidArea". It was also recently improved:
> http://trac.osgeo.org/postgis/ticket/1806

I programmed a similar algorithm to remove unwanted duplicate
rings from the polygonizer output. The algorithm is a bit
different though.

The code first normalizes the list of polygons returned by the
Polygonizer. This makes sure the coordinates are in a specific
order, which makes finding matching rings easier. For each hole
a matching outer shell is then searched for by comparing the
first edge of the hole with the edge formed by the first and last
(different) coordinates of the shells. The remaining code is similar
to that in PostGIS: count the number of parent shells and remove
polygons with an odd number of parents. I'm not doing a final overlay
operation though, as I don't think my application needs it.

I can make the code available if there is any interest. The
code is about 100 lines, so making the code available as a web
link might be preferable over posting the code here. I wouldn't
mind sending the code in email either to anyone interested.
The code uses the GEOS C++ API.


Mika Heiskanen

More information about the geos-devel mailing list