Wrong results with overlapping polygons

[Paolo Giangrandi <paolo@…>]

Many algorithms from boost::geometry (difference, intersection, union_, disjoint, sym_difference, intersects, possibly more) give wrong results with some pairs of polygons.

I could find many pairs of polygons (could only find pairs of polygons sharing part of an edge since I'm working with this kind of polygons) that are wrongly treated as if they weren't intersecting by all the aforementioned algorithms.

Here some examples:

POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371 ))
POLYGON(( 1.000000000000000 0.384374707937241, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.384374737739563 ))

POLYGON(( 0.000000000000000 0.373437941074371, 1.000000000000000 0.373437792062759, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000 ))
POLYGON(( -2.592187881469727 -0.626561701297760, -2.592187643051147 0.373438000679016, 7.907812595367432 0.373437851667404, 7.907812595367432 -0.626561224460602 ))

POLYGON(( 1.000000000000000 2.531045913696289, 1.000000000000000 3.000000000000000, 2.000000000000000 3.000000000000000, 2.000000000000000 2.531045913696289 ))
POLYGON(( 5.204249382019043 3.531043529510498, 5.204247951507568 2.531045675277710, -5.295750617980957 2.531046152114868, -5.295751094818115 3.531045913696289 ))

I'm working on Linux x86-64 (ArchLinux), and could reproduce this bug both with G++ 4.7.2 and clang 3.2.

I'm using the following types to store points and polygons:

typedef boost::geometry::model::d2::point_xy<float> point;
typedef boost::geometry::model::polygon<point, true, false> polygon;

The attached source file (C++11) can be used to reproduce this bug.

I believe this bug could be related to ​https://svn.boost.org/trac/boost/ticket/8183 .

[Paolo Giangrandi <paolo@…>]

A C++11 source file that reproduces this bug. It can be compiled with `g++ --std=c++11 -o geom geom.cp'

[Barend Gehrels]

Thanks for the report. I can reproduce it and I'm currently busy with a fix.

[Barend Gehrels]

(In [86579]) [geometry] fixed ticket 8310, disjoint did give the wrong results. Fixed using point_on_surface. Added unit test. Also tests for overlay algorithms because they might suffer from the same problem