boostorg / boostorg/geometry

Small integer multipolygon (sym_)difference failure case post traversal rewrite

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

Description

Here is a very small failure case for both difference and sym_difference that first fails on commit 805ff654e869030c4ba70f37fad6c3825f59c077, i.e. the traversal rewrite.

```cpp
#include

namespace bg = boost::geometry;

using point = bg::model::d2::point_xy;
using polygon = bg::model::polygon;
using multi_polygon = bg::model::multi_polygon;

int main() {
const auto geo1 = bg::from_wkt("MULTIPOLYGON(((8 8,8 6,8 4,6 4,6 2,6 0,0 0,0 6,2 6,2 8,8 8),(2 4,2 2,4 2,4 4,2 4),(6 6,4 6,4 4,6 4,6 6)))");
const auto geo2 = bg::from_wkt("MULTIPOLYGON(((6 6,6 4,4 4,4 6,6 6)),((6 6,6 8,8 8,8 6,6 6)),((4 6,2 6,2 8,4 8,4 6)),((4 4,4 2,2 2,2 4,4 4)),((4 2,6 2,6 0,4 0,4 2)),((2 6,2 4,0 4,0 6,2 6)),((2 2,2 0,0 0,0 2,2 2)),((6 2,6 4,8 4,8 2,6 2)))");
multi_polygon diff, symdiff;
bg::difference(geo1, geo2, diff);
bg::sym_difference(geo1, geo2, symdiff);

std::cout << "Diff:\t\t" << bg::to_wkt(diff) << '\n';
std::cout << "Symdiff:\t" << bg::to_wkt(symdiff) << '\n';
return 0;
}
```
Prints
```sql
Diff: MULTIPOLYGON(((8 6,8 4,6 4,6 6,8 6)),((2 2,4 2,4 0,2 0,2 2)),((2 4,2 2,0 2,0 4,2 4)),((6 6,4 6,4 8,6 8,6 6)))
Symdiff: MULTIPOLYGON(((8 2,6 2,6 4,4 4,4 6,4 8,6 8,6 6,8 6,8 2)),((4 0,2 0,2 2,0 2,0 4,4 4,4 0)))
```
should print
```sql
Diff: MULTIPOLYGON(((8 6,8 4,6 4,6 6,8 6)),((4 0,2 0,2 2,4 2,4 0)),((0 4,2 4,2 2,0 2,0 4)),((6 8,6 6,4 6,4 8,6 8)),((6 4,6 2,4 2,4 4,6 4)),((2 6,4 6,4 4,2 4,2 6)))
Symdiff: MULTIPOLYGON(((8 2,4 2,4 0,2 0,2 2,0 2,0 4,2 4,2 6,4 6,4 8,6 8,6 6,8 6,8 2)))
```

Contributor guide

Open the contributing guide

Research direction

Start by compiling and running the minimal C++ reproducer against the traversal rewrite at commit 805ff654e869030c4ba70f37fad6c3825f59c077, focusing on bg::difference and bg::sym_difference for the supplied integer multipolygons. Trace the traversal behavior that drops components, then verify both operations produce the expected WKT output shown in the issue.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
computer-graphics
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.