Multipolygon intersection incorrect for rectangles with rather specific collinear points
- Dominant language
- C++
- Stars
- 517
- Forks
- 232
- PR merge metrics
- No merged PRs in 30d
Description
The source files in the attached archive [bug.zip](https://github.com/boostorg/geometry/files/9179917/bug.zip) demonstrate an intersection bug that is present in version 1.79.0. Given two intersecting rectangles each with collinear points represented as two multi_polygons, for specific choices of those points, `boost::geometry::intersection` produces an incorrect result.
nonbug.cpp produces the following output where the second part of the output refers to a case with the y-coordinates of the points on the second rectangle being perturbed ever so slightly. As expected, the output is the same in both cases.
```
Valid (mpoly1): 1
Valid (mpoly2): 1
Valid (mpoly3): 1
Area: 0.09
Bounding box: ((-5.8, 5), (-5.5, 5.3))
Valid (mpoly1): 1
Valid (mpoly2): 1
Valid (mpoly3): 1
Area: 0.09
Bounding box: ((-5.8, 5), (-5.5, 5.3))
```
However, bug.cpp produces the following output where the first part indicates the bug. After perturbing the y-coordinates of the points on the second rectangle, the problem vanishes.
```
Valid (mpoly1): 1
Valid (mpoly2): 1
Valid (mpoly3): 1
Area: 0.24
Bounding box: ((-5.8, 5), (-5, 5.3))
Valid (mpoly1): 1
Valid (mpoly2): 1
Valid (mpoly3): 1
Area: 0.09
Bounding box: ((-5.8, 5), (-5.5, 5.3))
```
Note that the difference between both files is as follows.
```
--- nonbug.cpp 2022-07-21 13:00:55.168046300 +0200
+++ bug.cpp 2022-07-25 11:00:54.132520800 +0200
@@ -165,8 +165,8 @@ double r2[][2] = {
{-5.54, 5.3},
{-5.53, 5.3},
{-5.52, 5.3},
- {-5.51, 5.3},
- {-5.5, 5.3},
+ {-5.51, 5.299999999999998},
+ {-5.5, 5.299999999999998},
{-5.49, 5.3},
{-5.48, 5.3},
{-5.47, 5.3},
```
Contributor guide
Assessment
This issue has not been assessed yet.