Incorrect result from bg::intersection()
- Dominant language
- C++
- Stars
- 517
- Forks
- 232
- PR merge metrics
- No merged PRs in 30d
Description
I see there are few reports against this function already, I hope I am not repeating the issue.
I have an oval, which I am trying to split into 4 pieces using the 4 quadrants from the center. The result is that my lower left quadrant is incorrect (same as the overlapping box), upper right is incorrect (empty), but upper left and lower right are correct.
This is the input oval:

And this is the final result:

I am using boost 1.82 with BOOST_GEOMETRY_NO_ROBUSTNESS.
Any suggestions?
Here is my code:
```
auto wkt = "POLYGON ((4.67226015 3.73961913997, 4.67226015 3.73961913998, 4.67226015 3.73961913999, 4.67226015 3.73961914, 4.67226015 3.73961914001, 4.67226015 3.73961914003, 4.67226015001 3.73961914004, 4.67226015001 3.73961914005, 4.67593090393 3.76279536818, 4.67593090393 3.76279536819, 4.67593090394 3.7627953682, 4.67593090394 3.76279536822, 4.67593090394 3.76279536823, 4.67593090394 3.76279536824, 4.67593090396 3.76279536827, 4.68658384675 3.78370294571, 4.68658384676 3.78370294572, 4.68658384677 3.78370294574, 4.68658384677 3.78370294575, 4.68658384678 3.78370294576, 4.68658384679 3.78370294577, 4.68658384681 3.78370294579, 4.70317619421 3.80029529319, 4.70317619422 3.8002952932, 4.70317619423 3.80029529321, 4.70317619424 3.80029529322, 4.70317619425 3.80029529323, 4.70317619426 3.80029529323, 4.70317619429 3.80029529325, 4.72408377174 3.81094823605, 4.72408377175 3.81094823605, 4.72408377177 3.81094823606, 4.72408377178 3.81094823606, 4.72408377179 3.81094823606, 4.7240837718 3.81094823606, 4.7240837718 3.81094823607, 4.72408377181 3.81094823607, 4.72408377182 3.81094823607, 4.74725999995 3.81461899, 4.74725999996 3.81461899, 4.74725999998 3.81461899, 4.74725999999 3.81461899, 4.74726 3.81461899, 4.74726000002 3.81461899, 4.74726000003 3.81461899, 4.74726000004 3.81461899, 5.34706575996 3.81461899, 5.34706575997 3.81461899, 5.34706575998 3.81461899, 5.34706576 3.81461899, 5.34706576002 3.81461899, 5.34706576004 3.81461899, 5.37024198818 3.81094823607, 5.37024198819 3.81094823607, 5.3702419882 3.81094823607, 5.3702419882 3.81094823606, 5.37024198821 3.81094823606, 5.37024198822 3.81094823606, 5.37024198823 3.81094823606, 5.37024198824 3.81094823606, 5.37024198825 3.81094823605, 5.37024198826 3.81094823605, 5.37024198827 3.81094823604, 5.39114956571 3.80029529325, 5.39114956572 3.80029529325, 5.39114956572 3.80029529324, 5.39114956573 3.80029529324, 5.39114956574 3.80029529323, 5.39114956575 3.80029529323, 5.39114956575 3.80029529322, 5.39114956576 3.80029529322, 5.39114956577 3.80029529321, 5.39114956578 3.80029529321, 5.39114956579 3.8002952932, 5.39114956579 3.80029529319, 5.4077419132 3.78370294579, 5.40774191321 3.78370294577, 5.40774191322 3.78370294577, 5.40774191322 3.78370294576, 5.40774191323 3.78370294575, 5.40774191325 3.78370294571, 5.41839485604 3.76279536827, 5.41839485604 3.76279536826, 5.41839485605 3.76279536826, 5.41839485605 3.76279536825, 5.41839485606 3.76279536823, 5.41839485606 3.76279536822, 5.41839485606 3.76279536821, 5.41839485607 3.7627953682, 5.41839485607 3.76279536819, 5.41839485607 3.76279536818, 5.42206560999 3.73961914005, 5.42206560999 3.73961914004, 5.42206561 3.73961914003, 5.42206561 3.73961914002, 5.42206561 3.73961914001, 5.42206561 3.73961914, 5.42206561 3.73961913999, 5.42206561 3.73961913997, 5.42206560999 3.73961913996, 5.42206560999 3.73961913995, 5.41839485607 3.71644291182, 5.41839485607 3.71644291181, 5.41839485607 3.7164429118, 5.41839485606 3.7164429118, 5.41839485606 3.71644291178, 5.41839485606 3.71644291177, 5.41839485606 3.71644291176, 5.41839485606 3.71644291175, 5.41839485604 3.71644291173, 5.40774191325 3.69553533429, 5.40774191324 3.69553533428, 5.40774191324 3.69553533427, 5.40774191323 3.69553533426, 5.40774191323 3.69553533425, 5.40774191322 3.69553533425, 5.40774191322 3.69553533424, 5.40774191321 3.69553533423, 5.4077419132 3.69553533422, 5.40774191319 3.69553533421, 5.39114956577 3.67894298679, 5.39114956576 3.67894298678, 5.39114956575 3.67894298677, 5.39114956571 3.67894298675, 5.37024198827 3.66829004396, 5.37024198826 3.66829004395, 5.37024198825 3.66829004395, 5.37024198824 3.66829004394, 5.37024198823 3.66829004394, 5.37024198822 3.66829004394, 5.37024198821 3.66829004394, 5.3702419882 3.66829004393, 5.37024198819 3.66829004393, 5.37024198818 3.66829004393, 5.34706576005 3.66461929, 5.34706576004 3.66461929, 5.34706576002 3.66461929, 5.34706576001 3.66461929, 5.34706576 3.66461929, 5.34706575998 3.66461929, 5.34706575997 3.66461929, 5.34706575996 3.66461929, 4.74726000004 3.66461929, 4.74726000003 3.66461929, 4.74726000002 3.66461929, 4.74726 3.66461929, 4.74725999998 3.66461929, 4.74725999996 3.66461929, 4.72408377182 3.66829004393, 4.72408377181 3.66829004393, 4.7240837718 3.66829004393, 4.72408377179 3.66829004394, 4.72408377178 3.66829004394, 4.72408377177 3.66829004394, 4.72408377175 3.66829004395, 4.72408377174 3.66829004395, 4.72408377173 3.66829004396, 4.70317619429 3.67894298675, 4.70317619428 3.67894298676, 4.70317619425 3.67894298677, 4.70317619424 3.67894298678, 4.70317619421 3.67894298681, 4.68658384681 3.69553533421, 4.6865838468 3.69553533422, 4.68658384679 3.69553533423, 4.68658384679 3.69553533424, 4.68658384678 3.69553533424, 4.68658384678 3.69553533425, 4.68658384677 3.69553533426, 4.68658384676 3.69553533427, 4.68658384675 3.69553533429, 4.67593090396 3.71644291173, 4.67593090396 3.71644291174, 4.67593090394 3.71644291176, 4.67593090394 3.71644291177, 4.67593090394 3.71644291178, 4.67593090394 3.7164429118, 4.67593090393 3.7164429118, 4.67593090393 3.71644291181, 4.67593090393 3.71644291182, 4.67226015001 3.73961913995, 4.67226015001 3.73961913996, 4.67226015 3.73961913997))";
#include
#include
namespace bg = boost::geometry;
typedef double coord_type;
typedef bg::model::point point_type2d;
typedef bg::model::box box_type2d;
typedef bg::model::polygon polygon_type2d;
int main(int argc, const char **argv) {
polygon_type2d poly;
std::vector out;
box_type2d bbox;
bg::read_wkt(wkt, poly);
bg::correct(poly);
// find enclosing box
bg::envelope(poly, bbox);
// fix center of enclosing box
auto cx = (bbox.max_corner().get<0>() + bbox.min_corner().get<0>()) / 2;
auto cy = (bbox.max_corner().get<1>() + bbox.min_corner().get<1>()) / 2;
// intersect with (llx, lly) (cx, cy)
bg::intersection(
poly, box_type2d(
{bbox.min_corner().get<0>(), bbox.min_corner().get<1>()},
{cx, cy}),
out);
if(!out.empty()) // result is incorrect
std::cout << bg::wkt(out[0]) <()},
{bbox.max_corner().get<0>(), cy}
), out);
if (!out.empty()) //result is OK
std::cout << bg::wkt(out[0]) << std::endl;
else
std::cout << "EMPTY\n";
out.clear();
// intersect with (llx, cy) (cx, ury)
bg::intersection(poly, box_type2d(
{bbox.min_corner().get<0>(), cy},
{cx, bbox.max_corner().get<1>()}
), out);
if (!out.empty()) // result is OK
std::cout << bg::wkt(out[0]) << std::endl;
else
std::cout << "EMPTY\n";
out.clear();
// intersect with (cx, cy) (urx, ury)
bg::intersection(poly, box_type2d(
{cx, cy},
{bbox.max_corner().get<0>(), bbox.max_corner().get<1>()}
), out);
if (!out.empty()) // result is incorrect, it is empty
std::cout << bg::wkt(out[0]) << std::endl;
else
std::cout << "EMPTY\n";
return 0;
}
```
Contributor guide
Assessment
This issue has not been assessed yet.