boostorg / boostorg/polygon

Non-empty polygon incorrectly considered as empty

Open
#91 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

Hiya,

I've found an issue where some geometry that isn't empty is considered to be by boost polygon. Originally the geometry was part of a much more complex polygon, and small part of that polygon disappeared during a boolean operation which broke some of our code later down the line. I traced the issue and I've simplified it down to a single triangle:

```
std::vector> points{
{391663, 158218},
{339476, 267629},
{350305, 244924},
{391663, 158218}
};

boost::polygon::polygon_with_holes_data polygon(points.begin(), points.end());

boost::polygon::polygon_set_data polygon_set;
polygon_set.insert(polygon);

std::cout << "Area (polygon data): " << boost::polygon::area(polygon) << "\n"; // Prints 47058
std::cout << "Area (polygon set): " << boost::polygon::area(polygon_set) << "\n"; // Prints 0
std::cout << "Empty: " << boost::polygon::empty(polygon_set) << "\n"; // Prints true
std::cout << "Orient: " << boost::polygon::orientation(boost::polygon::segment_data(points[0], points[1]), points[2]) << "\n"; // Print 1 (point is left of segment)
```

I believe this polygon to not be empty, however after being loaded into a polygon_set_data, the geometry disappears (shown by the area calculation), and for the same reason I assume, empty() returns true.

I've included a call to orientation() in the sample code, which returns that the 3rd point is indeed to the left of the segment formed by the first two points, so the polygon is indeed correctly an anti-clockwise polygon, and also so that it's clear the points are not colinear.

It is worth noting that if I move points[2] up by 2 units in the y axis, it causes the polygon to have the opposite winding. So it really is a very very thin polygon.

Also worth noting that if I move points[2] down by 2 units in the y axis, the polygon doesn't disappear any more, the orientation() result is the same(as expected), and the above functions then return the correct results.

Just wanted to add that at my work we have put probably billions of complex polygons through boost polygon, and this is the first serious issue we've encountered. It's a great library so kudos! :-)

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.