1

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.

2
  • has_self_intersections can only return false or throw the exception. It was likely not intended for general use, since it's hidden in the detail namespace.
    – Cubbi
    Apr 18, 2014 at 18:17
  • @Cubbi, yes, and it's used by many functions to check the consistency of the underlying data. Therefore if it fails, things will go wrong the next time one uses results[0].
    – Xoph
    Apr 18, 2014 at 18:44

1 Answer 1

1

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.

3
  • I filed this bug report: svn.boost.org/trac/boost/ticket/9934 The bug can be reproduced with the current git repository which I suppose contains the robustness upgrades?
    – Xoph
    Apr 22, 2014 at 11:28
  • No, they're in the branch rescale_to_integer. Keep in mind that it's work in progress. For future readers: this branch may no longer exist and the updates might be merged with develop and/or master. Apr 22, 2014 at 13:25
  • 1
    Thanks, I now resolved it for now by resorting to converting everything to a boost::polygon polygon, intersecting there, and then converting it back to boost::geometry. I need the code in a production environment and therefore cannot really use a work in progress code base.
    – Xoph
    Apr 23, 2014 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.