boostorg / boostorg/geometry

difference() produces invalid (self-intersecting) result for valid polygon-with-hole input

Open
#1,490 1 comment 1 reaction 0 assignees View on GitHub
Dominant language
C++
Stars
517
Forks
232
PR merge metrics
No merged PRs in 30d

Description

### Version of Boost

`1.91.0`

### Actual and Expected Behavior

**Actual:** `boost::geometry::difference()` on two valid `multi_polygon` operands (a polygon with a hole, minus another polygon) returns a result that fails `boost::geometry::is_valid()` — it contains a self-intersection introduced at the point where the hole's ring touches the subtracted polygon's boundary.

I discovered this by seeing that a point, that is in `A \ B`, is reported as also being within `B`, which violates the basic definition of set difference.

**Expected:** `boost::geometry::difference()` should return a valid geometry (satisfying `is_valid()`) for valid input operands.

**Minimal complete program:** attached [testing.cpp](https://github.com/user-attachments/files/31964256/testing.cpp)
```
#include
#include
#include

namespace bg = boost::geometry;

using int_point_t = bg::model::point;
using int_poly_t = bg::model::polygon;
using int_multi_poly_t = bg::model::multi_polygon;

int main()
{
int_multi_poly_t poly_A;
boost::geometry::read_wkt("MULTIPOLYGON(((0 0,20 0,20 20,0 20,0 0),(5 15,14 14,9 6,5 15)))", poly_A);

int_multi_poly_t poly_B;
boost::geometry::read_wkt("MULTIPOLYGON(((5 15,5 5,15 5,15 15,5 15)))", poly_B);

bg::correct(poly_A);
bg::correct(poly_B);

assert(bg::is_valid(poly_A));
assert(bg::is_valid(poly_B));

int_multi_poly_t result;
boost::geometry::difference(poly_A, poly_B, result);

std::cout << boost::geometry::to_wkt(result) << std::endl;
if (std::string message; !bg::is_valid(result, message))
std::cerr << "Invalid geometry: " << message << std::endl;

}
```
Output when run:
> MULTIPOLYGON(((0 0,0 20,20 20,20 0,0 0),(5 15,9 6,14 14,5 15),(5 15,5 5,15 5,15 15,5 15)))
> Invalid geometry: Geometry has invalid self-intersections. A self-intersection point was found at (5, 15); method: t; operations: u/i; segment IDs {source, multi, ring, segment}: {0, 0, 0, 2}/{0, 0, 1, 3}

**Pictures of input:**
Image Image

**Picture of output:**
Image

### Steps necessary to reproduce the problem

1. Build the attached `testing.cpp` against Boost 1.91.0.
2. Run it.
3. Observe that `bg::is_valid(result, message)` reports `false` with a self-intersection at the point where polygon A's hole ring touches polygon B's boundary.

Both input polygons (`poly_A`, `poly_B`) are individually valid (confirmed via `is_valid()` before the `difference()` call in the program), so the invalidity is introduced by `difference()` itself.

### All relevant compiler information

- Compiler: GCC 14 (`g++-14.3.0`)
- Standard: C++23 (`-std=gnu++23`)
- OS: Linux

Contributor guide

Open the contributing guide

Research direction

Start with the attached testing.cpp and reproduce the case against Boost 1.91.0, focusing on bg::difference() where polygon A's hole touches polygon B's boundary. Use bg::is_valid() and the reported self-intersection at (5, 15) to trace the result; done means difference() returns a valid geometry that excludes B.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
computer-graphics
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
70/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.