boostorg / boostorg/geometry

difference algorithm returning invalid geometry (regression over 1.75.0)

Open
#1,035 3 comments 0 reactions 0 assignees View on GitHub
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. I've seen it in 1.59.0/1.66.0, and it **was fixed in 1.67.0**, see: https://svn.boost.org/trac10/ticket/11676

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(((2974 352,2940 336,2907 334,2907 317,2974 317,2974 352)),((2940 354,2957 361,2907 361,2907 353,2940 354)))", polygonA); // does not throw
_ASSERT( boost::geometry::is_valid(polygonA) ); // returns true

tc::geo::polygon polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((576 330,576 312,777 348,576 330)),((2968 349,2940 342,2902 334,2940 336,2968 349)),((3612 516,3276 498,2968 349,3276 432,3612 444,3612 516)),((2902 334,2598 324,2262 438,1926 414,1590 384,1248 354,1590 372,1926 384,2262 402,2598 276,2902 334)),((1248 354,912 372,777 348,912 360,1248 354)))", 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(((2940 354,2957 361,2907 361,2907 353,2940 354)),((2974 351,2974 352,2967 348,2968 349,2974 351)),((2940 336,2907 334,2907 317,2974 317,2974 351,2968 349,2940 336)))
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/1034

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.