boost::geometry::intersection on two triangles creates self-intersecting polygon

[snubdodecahedron@…]

The code below creates two triangles sharing one vertex, intersects them, and then tests the result for self intersections. The test fails on 1.49.0.

#include <iostream> #include <deque>

#include <boost/geometry.hpp> #include <boost/geometry/geometries/point_xy.hpp> #include <boost/geometry/geometries/polygon.hpp> #include <boost/geometry/io/wkt/wkt.hpp> #include <boost/geometry/multi/geometries/register/multi_polygon.hpp>

typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double>,false> polygon; BOOST_GEOMETRY_REGISTER_MULTI_POLYGON(std::deque<polygon>);

int main() {

polygon green, blue; std::deque<polygon> output;

boost::geometry::read_wkt(

"POLYGON((0.94458145927637815475 0.76153991837054491043 , 0.37399105052463710308 0.59515245421789586544 , " "0.031151068862527608871 0.95449111564084887505 , 0.94458145927637815475 0.76153991837054491043))", green);

boost::geometry::read_wkt(

"POLYGON((0.94458145927637815475 0.76153991837054491043 , 0.90063317718199253914 0.7487243450636832387 , " "0.57996011668279578988 0.83856179693083876536 , 0.94458145927637815475 0.76153991837054491043))", blue);

boost::geometry::intersection(blue, green, output);

std::cout<<"testing output"<<std::endl;

boost::geometry::detail::overlay::has_self_intersections(output);

std::cout<<"valid output"<<std::endl;

return 0;

}

[Barend Gehrels]

Thanks for your report.

This has been solved in the meantime one or two weeks ago, in Boost.Trunk. Polygons with less then 3 points or an area of 0.0 are filtered out. This solves this issue.

[snubdodecahedron@…]

I updated to the trunk a few hours ago. I am hitting the same problem but this time on a different set of input polygons. Thanks for your time.

Craig

#include <cstdio>
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/ring.hpp>
#include <boost/geometry/io/wkt/wkt.hpp>
#include <boost/geometry/multi/geometries/multi_polygon.hpp>

typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;
typedef boost::geometry::model::multi_polygon<polygon> multi_polygon;

int main()
{
    polygon green, blue;
    multi_polygon output;

    boost::geometry::read_wkt(
        "POLYGON((0.63872330997599124913 0.25963790394761232516 , 0.51901482278481125832 0.36860892060212790966 , 0.24443514109589159489 0.62663296470418572426 , 0.41175117865081167778 0.47178476291601745274 , 0.63872330997599124913 0.25963790394761232516))", green);

    boost::geometry::read_wkt(
        "POLYGON((0.52364358028948876367 0.36823021165656988352 , 0.7762673462275415659 0.13443113025277850237 , 0.59446187055393329146 0.29992923303868185281 , 0.52364358028948876367 0.36823021165656988352))", blue);
    boost::geometry::correct(green);
    boost::geometry::correct(blue);
    boost::geometry::detail::overlay::has_self_intersections(green);
    boost::geometry::detail::overlay::has_self_intersections(blue);

    printf("A\n");
    boost::geometry::intersection(green,blue,output);
    printf("B\n");
    boost::geometry::detail::overlay::has_self_intersections(output);
    printf("C\n");

    return 0;
}