boostorg / boostorg/boost

Bug in polygon intersection?

Open
#731 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
HTML
Stars
8.6k
Forks
1.9k
Avg merge
39m
Merged PRs (30d)
2

Description

A, B <- simple polygons
There appears to be a problem in computing $A \cap B$, although I am not sure which specific cases trigger it.
The example below reproduces the problem:

// boost polygon utilities
#include

// boost aliases
namespace bg = boost::geometry;
namespace bgm = bg::model;
using boost_point_t = bgm::point;
using boost_polygon_t = bgm::polygon;

int main()
{
boost_polygon_t p1{{{76.37593982020243, 53.62855965544195},
{76.56629943847656, 53.71099853515625},
{76.97709655761719, 54},
{77.41490173339844, 54.58509826660156},
{77, 55},
{76.99999312109907, 55.00000687887207},
{76.99866406552184, 55.00133592887243},
{76.09896357657894, 55.90103264257367},
{76.32990264892578, 54},
{76.37593982020243, 53.62855965544195}}};
bg::correct(p1);

boost_polygon_t p2{{{77.41490173339844, 54.58509826660156},
{77, 55},
{76.09089660644531, 55.90909957885742},
{76, 56},
{76.32990264892578, 54},
{76.372802734375, 53.62720108032227},
{76.56629943847656, 53.71099853515625},
{76.97709655761719, 54},
{77.41490173339844, 54.58509826660156}}};
bg::correct(p2);

std::vector intersection{};
bg::intersection(p2, p1, intersection);

// intersection should be non empty, with one connected component
assert(intersection.empty()==false);
assert(static_cast(intersection.size())==1);

std::cout << std::endl << std::endl << "Intersection: " << std::endl;
for(auto& it:intersection[0].outer())
std::cout << bg::get<0>(it) << " " << bg::get<1>(it) << std::endl;
}

Output (incorrect):
76.3759 53.6286
76.5663 53.711
76.9771 54
77.4149 54.5851
77 55
77 55
76.0909 55.9091
76 56
76.3299 54
76.3728 53.6272
76.5663 53.711
76.9771 54
77.4149 54.5851
77 55
76.9997 55.0003
76.9987 55.0013
76.099 55.901
76.3299 54
76.3759 53.6286

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.