boostorg / boostorg/polygon

Infinite loop

Open
#49 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
70
Forks
75
PR merge metrics
No merged PRs in 30d

Description

A call to `construct_voronoi` blocks forever in the following code:
```cpp
int main() {
using poly_segment = boost::polygon::segment_data;
std::vector segments;

std::ifstream file("bad_voronoi.segments.txt");
while (!file.fail()) {
double x1, y1, x2, y2;
file >> x1 >> y1 >> x2 >> y2;
segments.push_back({{x1, y1}, {x2, y2}});
}

// // Doesn't help:
// std::vector split_segments;
// boost::polygon::intersect_segments(split_segments, segments.begin(), segments.end());
// segments = std::move(split_segments);

boost::polygon::voronoi_diagram vd;
boost::polygon::construct_voronoi(segments.begin(), segments.end(), &vd);
}
```
[bad_voronoi.segments.txt](https://github.com/boostorg/polygon/files/5036881/bad_voronoi.segments.txt)

I've tracked the issue down to the `_build()` method in `voronoi_diagram.hpp`, specifically in the loop that remove degenerate vertices:
```cpp
do {
e->vertex0(v);
e = e->rot_next();
} while (e != v->incident_edge());
```

An odd property: removing *any* segment from `bad_voronoi.segments.txt` will unbreak the infinite loop. You need all 1912 segments to trigger the fault.

![bad_voronoi](https://user-images.githubusercontent.com/3943815/89563472-56f09c00-d7d0-11ea-9754-a0879c76d00b.png)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.