Opened 3 years ago

Last modified 3 months ago

#11674 assigned Bugs

difference algorithm returning invalid geometry

Reported by: vschoech@… Owned by: Barend Gehrels
Milestone: To Be Determined Component: geometry
Version: Boost 1.66.0 Severity: Problem
Keywords: difference, multi-polygon, polygon Cc:

Description

My "tc::geo::polygon" type is actually a multi-polygon, using a polygon type that is based on int, oriented counter-clockwise and open (not closed). Please consider the following example:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((529 3217,529 998,5337 998,5337 1834,5070 2000,5337 2072,5337 3475,529 3475,529 3312,1734 2054,2934 1670,3230 1690,2934 1400,1734 1784,529 3217),(4140 2582,5071 2001,4140 1754,3231 1691,4140 2582)))", polygonA); // does not throw
boost::geometry::is_valid(polygonA); // returns true

tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((528 3218,528 2498,1734 1406,2556 1522,1734 1784,528 3218)),((4610 2288,5340 1178,5340 1832,4609 2289,4140 3002,2934 1574,2555 1521,2934 1400,4140 2582,4610 2288)))", polygonB); // does not throw
boost::geometry::is_valid(polygonB); // returns true

tc::geo::polygon<int> polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((2553 1521,1734 1406,529 2498,529 998,5337 998,5337 1183,4839 1939,4140 1754,3231 1691,4140 2582,3230 1690,2934 1400,2555 1521,2556 1522,2553 1521)),((1734 1784,529 3217,529 3216,1734 1784)),((3020 1676,4140 3002,4609 2289,5071 2001,5337 2072,5337 3475,529 3475,529 3312,1734 2054,2934 1670,3020 1676)))
boost::geometry::is_valid(polygonC); // returns false!

The difference of two valid multi-polygons yields an invalid multi-polygon.

May be related to Ticket #10661.

Change History (4)

comment:1 Changed 3 years ago by Barend Gehrels

  • Still a problem in beta for 1.60
  • It generates spikes.
  • The sym_difference complains about invalid input
  • Added test case to unit test suite

comment:2 Changed 18 months ago by Barend Gehrels

Status: newassigned

So, alas still problematic

Last edited 18 months ago by Barend Gehrels (previous) (diff)

comment:3 Changed 9 months ago by Volker Schöch <vschoech@…>

Version: Boost 1.59.0Boost 1.66.0

Related problem #12753 still present in 1.66.0.

comment:4 Changed 3 months ago by Volker Schöch <vschoech@…>

Still reproducible in 1.67.0.

Note: See TracTickets for help on using tickets.