boostorg / boostorg/geometry

Incorrect result from bg::intersection()

Open
#1,174 8 comments 0 reactions 1 assignee Claimed by @barendgehrels View on GitHub
bug
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:
![image](https://github.com/boostorg/geometry/assets/12432089/cd9fb7dd-4fa5-4d71-9d10-2187344bc2aa)

And this is the final result:
![image](https://github.com/boostorg/geometry/assets/12432089/fca21f10-1f05-4d7f-a5e9-11ddc6b8e04f)

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.