boostorg / boostorg/geometry

difference algorithm returning invalid geometry (regression over 1.75.0)

Open
#1,034 4 comments 0 reactions 1 assignee Claimed by @barendgehrels View on GitHub
bug
Dominant language
C++
Stars
517
Forks
232
PR merge metrics
No merged PRs in 30d

Description

This problem has been with us for a while. It did not occur in 1.55.0/1.59.0, then it did occur in 1.63.0/1.64.0/1.66.0, and **was fixed in 1.67.0**, see: https://svn.boost.org/trac10/ticket/12752

It then did not occur in 1.75.0, and **now occurred again in 1.79.0**.

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). I am using **boost 1.79.0**. Please consider the following example:

```C++
tc::geo::polygon polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((3232 2413,2136 2646,3232 2412,3232 2413)),((3232 2532,3232 2856,1031 2856,1031 1056,3232 1056,3232 2221,2136 2328,1032 1212,1032 1458,1032 1764,2136 2790,3232 2532)))", polygonA); // does not throw
_ASSERT( boost::geometry::is_valid(polygonA) ); // returns true

tc::geo::polygon polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((1032 2130,1032 1764,2052 2712,1032 2130)),((3234 2580,2558 2690,3234 2532,3234 2580)),((2558 2690,2136 2790,2052 2712,2136 2760,2558 2690)))", polygonB); // does not throw
_ASSERT( boost::geometry::is_valid(polygonB) ); // returns true

tc::geo::polygon polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((3232 2413,2136 2646,3232 2412,3232 2413)),((2567 2689,3232 2581,3232 2856,1031 2856,1031 1056,3232 1056,3232 2221,2136 2328,1032 1212,1032 1458,1032 1764,1032 2130,2052 2712,2136 2790,2567 2689),(1032 1764,2053 2713,2052 2712,1032 1764)))
boost::geometry::is_valid(polygonC); // returns false!
```

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

See also:
- https://github.com/boostorg/geometry/issues/602
- https://github.com/boostorg/geometry/issues/1035

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.