Modify

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)))

Attachments (0)

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain Barend Gehrels.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.