Expectation for robustness and rescale policy

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

Expectation for robustness and rescale policy

Martinez, Max

A recent upgrade from boost 1.55 to 1.61 resulted in a number of unit test failures in our development environment related to the robustness polices in boost geometry (specifically the rescale policy in the context of intersection) that seem to now be applied by default. The failures go away (previous behavior is restored) if we set BOOST_GEOMETRY_NO_ROBUSTNESS, but we were wondering what our expectations should be with respect to robustness (there doesn’t seem to be any documentation on it). I’m not a COGO expert so after googling around a bit my impression is that a robust algorithm is one that behaves correctly (and fast) even for “degenerate” cases.

 

The failures are related to floating point differences but one that was surprising to us was that intersections generated on horizontal (and vertical?) line segments did not result in points that had the exact y (x) value as the points representing the line segment intersected.

 

The example below illustrates this. It is a test that has been massaged a bit so that it can be examined outside our environment. It passes if the coordinate type is float, but not if it is double (which our adaptation is based upon). I understand that the results will be slightly different due to the scaling to integer and back to double, but is it expected that the horizontal line intersection, which can easily (and will) be inspected by the geospatial end user, might not have a y value that matches the horizontal line (value ends up as 3647747.9999977136)? Is this also possible if robustness is disabled (i.e., were/are we just getting lucky with this set of values)?

 

#include <boost/geometry.hpp>

#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/geometries/ring.hpp>

#include <boost/geometry/geometries/point_xy.hpp>

#include <boost/convert.hpp>

.

.

.

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

       typedef boost::geometry::model::box<point_2d> box_2d;

       typedef boost::geometry::model::ring<point_2d> ring_2d;

 

       box_2d b = boost::geometry::make<box_2d>(598413.0, 3647748.0, 598641.0, 3647586.5);

       ring_2d r1;

       boost::geometry::convert(b, r1);

 

       b = boost::geometry::make<box_2d>(598427.84499100002, 3647759.164202, 598607.84499100002, 3647619.164202);

       ring_2d r2;

       boost::geometry::convert(b, r2);

 

       {

             using namespace boost::geometry;

             std::deque<ring_2d> outputs;

             ring_2d &rRing1 = r1;

             ring_2d &rRing2 = r2;

 

             ring_2d rRing1Corrected = rRing1;

             boost::geometry::correct(rRing1Corrected);

             ring_2d rRing2Corrected = rRing2;

             boost::geometry::correct(rRing2Corrected);

 

             intersection(rRing1Corrected, rRing2Corrected, outputs);

 

             box_2d bounds;

             envelope(outputs[0], bounds);

 

       CPPUNIT_ASSERT_EQUAL(boost::geometry::traits::coordinate_type<point_2d>::type(3647748.0), bounds.max_corner().y());

       }


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

Re: Expectation for robustness and rescale policy

Barend
Hi Max,

Op 2-8-2016 om 20:34 schreef Martinez, Max:

A recent upgrade from boost 1.55 to 1.61 resulted in a number of unit test failures in our development environment related to the robustness polices in boost geometry (specifically the rescale policy in the context of intersection) that seem to now be applied by default. The failures go away (previous behavior is restored) if we set BOOST_GEOMETRY_NO_ROBUSTNESS, but we were wondering what our expectations should be with respect to robustness (there doesn’t seem to be any documentation on it). I’m not a COGO expert so after googling around a bit my impression is that a robust algorithm is one that behaves correctly (and fast) even for “degenerate” cases.

 

The failures are related to floating point differences but one that was surprising to us was that intersections generated on horizontal (and vertical?) line segments did not result in points that had the exact y (x) value as the points representing the line segment intersected.

 

The example below illustrates this. It is a test that has been massaged a bit so that it can be examined outside our environment. It passes if the coordinate type is float, but not if it is double (which our adaptation is based upon). I understand that the results will be slightly different due to the scaling to integer and back to double, but is it expected that the horizontal line intersection, which can easily (and will) be inspected by the geospatial end user, might not have a y value that matches the horizontal line (value ends up as 3647747.9999977136)? Is this also possible if robustness is disabled (i.e., were/are we just getting lucky with this set of values)?

 


Sorry for the delayed reaction. The rescaling was introduced to solve several overlay cases which were failing because of robustness issues. During that, several refactorings have been applied. Besides rescaling, the overall robustness issues also reduced.

Currently we have the rescaling still enabled, and now on its turn this gives some failures which are hard to fix. Therefore we are working to remove this again and fix the remaining issues in a different way.

So you can indeed set the BOOST_GEOMETRY_NO_ROBUSTNESS define to run the algorithms without rescaling, and in a future version (but it will not be 1.62) the need of the flag is gone.

Thanks also for the testcase.

Regards, Barend


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry