[geos-devel] Bug in GEOS polygonizer

[Mika Heiskanen]

Hi all,

I'm new to GEOS, and this is my first post to this list which I just
subscribed to.

I am quite confident I have found a bug in the GEOS polygonizer.

The problem:

- I have a set of edges which I first polygonize, and then
   call buildGeometry on to get a single multipolygon.

- The last two rings in the multipolygon output should not be
   there, they have already been listed as holes in earlier
   polygons.

Leads:

- The extra rings are listed last in the resulting multipolygon,
   implying they might be on some internal todo-list, but are
   perhaps not correctly removed when added as a hole to the
   multipolygon. This todo-list might be the last geometry
   collection to be added to the resulting multipolygon.

- The second coordinate of the rings is the first coordinate
   of the holes already added. This might imply some internal
   sorting/constructing has been done on the rings but perhaps
   not consistently.

I will try to debug this myself, but since I am completely
new to the code I would appreciate any hints on where to
look. For this purpose I have temporarily made this link available:

   http://beta.fmi.fi/bug.zip

The zip-file contains two files. One named EDGES, containing
about 2000 coordinate pairs forming the resulting polygons by a true
case of contouring temperature over Scandinavia, and
a second file named bug.cpp, a simple test program which uses the
GEOS C++ API and can be compiled in the GEOS source directory as
instructed by the first lines in bug.cpp:

// ./configure  CXXFLAGS="-g -O0" && make
// g++ -std=c++11 -Wno-deprecated-declarations -o bug bug.cpp 
src/.libs/libgeos.a

The test program prints a multipolygon WKT. The last two rings in
it have as their second coordinates:

    664682.9106474313884974 -3956251.4601273220032454
    824358.6671691739466041 -3900967.1810790780000389

The rings are embedded in "(( ))" meaning they are polygons in
a multipolygon. However, if you search backward in the output
the same coordinates appear first in holes embedded in "( )".

I will try to debug this on Monday, until then I'm pretty much
booked. Meanwhile any hints on where to look for the bug would be
appreciated.

This bug seems to occur fairly frequently. The test case covers
only one temperature interval in Scandinavia, the same problem
occurred in a couple of the ~20 temperature intervals I calculated.
The test data was the first one I tried.

Regards,

Mika Heiskanen / Finnish Meteorological Institute