Intersection precision problem

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Intersection precision problem

Edwin Boom
Hi all,

I have come across a problem regarding the precision with boost::geometry::intersection.

In the code below I have two clockwise polygons (named 'green' and 'blue') with 'double' points and a precision of 17 decimals.
There are two slightly rotated rectangular polygons. A larger polygon(blue) consisting of 6 points, and another polygon(green) overlapping half of the blue-polygon with 4 (mutual) points.

The intersection of the 'green' with the 'blue' polygon fails to return a result but boost::geometry::intersects indicates there is an intersection.
The reverse intersection 'blue' with 'green' returns the correct result.

If the 17th precision decimal is removed (using 16 decimals), both intersections behave as expected.

Is this a bug, or is there a rule-of-thumb on how to handle these precision problems?

Kind regards,
Edwin


#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/foreach.hpp>
using boost::geometry::dsv;

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

void intersect_output(std::string const& what, polygon const& poly1, polygon const& poly2)
{
    std::cout << "Intersecting: " << what << std::endl;
    bool b = boost::geometry::intersects(poly1, poly2);
    std::cout << " - intersects: " << (b ? "YES" : "NO") << std::endl;

    std::deque<polygon> output;
    boost::geometry::intersection(poly1, poly2, output);
    int i = 0;
    std::cout << " - result:" << std::endl;
    BOOST_FOREACH(polygon const& poly, output)
    {
        std::cout << i++ << " area: " << boost::geometry::area(poly) << std::endl;
        std::cout << "  poly:" << dsv(poly) << std::endl;
    }
}

int main()
{
    polygon cw_green, cw_blue;
        //                                       1                    1      
    // number of decimals         x-12345678901234567  y-12345678901234567
    boost::geometry::read_wkt(
        "POLYGON(("
                                "-0.02610213295603003  0.40648309674964367,"
                                " 0.39289786704396956 -6.11851690325035680,"
                                "-2.85042208165307500 -6.32678526470691780,"
                                "-3.26942208165307460  0.19821473529308273,"
                                "-0.02610213295603003  0.40648309674964367"
            "))", cw_green);

    boost::geometry::read_wkt(
        "POLYGON(("
                                " 0.39289786704396956 -6.11851690325035680,"
                                "-2.85042208165307500 -6.32678526470691780,"
                                "-5.59476973055057500 -6.50301233978554640,"
                                "-6.01376973055057460  0.02198766021445422,"
                                "-3.26942208165307460  0.19821473529308273,"
                                "-0.02610213295603003  0.40648309674964367,"
                                " 0.39289786704396956 -6.11851690325035680"
            "))", cw_blue);

    intersect_output("cw_green && cw_blue", cw_green, cw_blue);
    intersect_output("cw_blue && cw_green", cw_blue, cw_green);

    return 0;
}
Reply | Threaded
Open this post in threaded view
|

Re: Intersection precision problem

Barend
Hi Edwin,

Thanks for your report.



> If the 17th precision decimal is removed (using 16 decimals), both
> intersections behave as expected.
>
> Is this a bug, or is there a rule-of-thumb on how to handle these precision
> problems?

This has been solved in the meantime a few weeks ago. So Boost 1.49
gives still this error, but the Boost Trunk handles it correctly. I
could reproduce it using your program.

So hope you are able to upgrade to the Trunk (it's also possible to copy
only Boost.Geometry from the trunk, plus (a part of) Boost.Math).

The general rule is that ttmath handles these cases correctly. I've
never found problems with them. The next rule is that if there is an
issue using a double precision type, it is usually solvable too, so in
that case reports are welcome.

Regards, Barend


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: Intersection precision problem

Edwin Boom
Hi Barend,

Thanks for your reply.
In future I'll check with the trunk version first.
Thank's for the great geometry lib!

Greetings,
Edwin