Opened 4 years ago

Last modified 3 years ago

#10661 new Bugs

difference algorithm returning invalid geometry

Reported by: Volker Schöch <vschoech@…> Owned by: Barend Gehrels
Milestone: To Be Determined Component: geometry
Version: Boost 1.56.0 Severity: Regression
Keywords: difference, multi-polygon, polygon, self-intersection Cc:

Description

My "_TPolygon" 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:

_TPolygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((1701 985,3501 985,3501 2785,1701 2785,1701 985)))", polygonA); // does not throw
boost::geometry::is_valid(polygonA); // returns true

_TPolygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((1698 1860,1698 1122,2598 1392,3492 1842,3492 32706,2598 2340,1698 1860)))", polygonB); // does not throw
boost::geometry::is_valid(polygonB); // returns true

_TPolygon<int> polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((1701 1122,1701 985,3501 985,3501 2785,3492 1857,3492 1842,2598 1392,1701 1122)),((1701 1861,2598 2340,1669 2785,1701 2785,1701 1861)))
boost::geometry::is_valid(polygonC); // returns false!

_TPolygon<int> polygonD;
boost::geometry::read_wkt("MULTIPOLYGON(((1698 2772,1698 1860,2598 2340,3492 2412,3492 32743,1698 2772)))", polygonD); // does not throw
boost::geometry::is_valid(polygonD); // returns true

_TPolygon<int> polygonE;
boost::geometry::difference(polygonC, polygonD, polygonE); // throws "Boost.Geometry Overlay invalid input exception"!

This worked in boost 1.55.0. The result for polygonC was slightly different in 1.55.0, and there was a reasonable(?) result for polygonE:

polygonC: MULTIPOLYGON(((1701 1122,1701 985,3501 985,3501 2785,3492 2785,3492 1842,2598 1392,1701 1122)),((1701 1861,2598 2340,2611 2785,1701 2785,1701 1861)))
polygonE: MULTIPOLYGON(((3492 2412,3492 1842,2598 1392,1701 1122,1701 985,3501 985,3501 2785,3492 2785,3492 2412),(1701 1861,2598 2340,1701 1861)))

Change History (3)

comment:1 Changed 4 years ago by Volker Schöch <vschoech@…>

This may be related to

  • Ticket #9768 (difference of multi-polygon and box returns multi-polygon with redundant points)
  • Ticket #9942 (Result of difference of multi-polygons contains spike)

comment:2 Changed 4 years ago by Volker Schöch <vschoech@…>

May be related to #10803 (union algorithm returning invalid geometry).

comment:3 Changed 3 years ago by Barend Gehrels

  • Added test case in unit tests
  • For 1.60 this is still a problem
  • However, the first stage (the generated polygon C) is now valid
  • And (therefore) E=C-D does not generate an exception anymore, but that result is still invalid
Note: See TracTickets for help on using tickets.