difference() produces invalid (self-intersecting) result for valid polygon-with-hole input
- 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:**
**Picture of output:**
### 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
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