CODEWITHSUNDEEP
c++boostconvex-hullset-intersectionboost-geometry
Xoph
Xoph

Reputation: 479

Taking intersections of convex hulls in boost::geometry

After several attempts using floating point numbers that resulted in wild exceptions because of rounding issues, I thought using integer arithmetic as a workaround did the trick. However, now I run into the exact same issue.

I'm trying to compute the intersection of the convex hulls of various point sets:

#include <iostream>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/multi/geometries/multi_point.hpp>
#include <boost/geometry/geometries/polygon.hpp>

int main()
{
    typedef boost::geometry::model::d2::point_xy<int> Point;
    typedef boost::geometry::model::multi_point<Point> MultiPoint;
    typedef boost::geometry::model::ring<Point> Polygon;

    MultiPoint mp0, mp1;
    boost::geometry::read_wkt("MULTIPOINT((54 74),(54 75),(54 75),(62 75),(86 75),(94 75),(118 75),(124 75),(13 50),(13 51),(147 130),(281 51),(281 50))", mp0);
    boost::geometry::read_wkt("MULTIPOINT((52 74),(54 75),(135 90),(175 74),(54 74),(52 74))", mp1);

    Polygon hull0, hull1;
    boost::geometry::convex_hull(mp0, hull0);
    boost::geometry::convex_hull(mp1, hull1);

    std::vector<Polygon> results;
    boost::geometry::intersection(hull0, hull1, results);

    assert(results.size() == 1);

    // This results in the exception.
    assert(!boost::geometry::detail::overlay::has_self_intersections(results[0]));

    return EXIT_SUCCESS;
}

This fails with boost::geometry::overlay_invalid_input_exception.

The convex hulls hull0 and hull1 look like this:

hull0 and hull1

Is there something I am doing wrong? I'd really like to not have to implement computing the convex hull and intersections myself, which seems like a lot of unnecessary error prone work.

Upvotes: 1

Views: 1013

Answers (1)

Adam Wulkiewicz
Adam Wulkiewicz

Reputation: 2098

The use-case looks ok.

We have some numerical robustness upgrades but they're not released yet (Boost 1.55). If you'd like to test them or ask some more detailed questions I suggest to contact us on the Boost.Geometry mailing list: http://lists.boost.org/mailman/listinfo.cgi/geometry.

Upvotes: 1

Related Questions