Opened 7 years ago

Closed 7 years ago

#5954 closed Bugs (fixed)

distance_pythagoras skips sqrt() step

Reported by: Mateusz Loskot Owned by: Barend Gehrels
Milestone: To Be Determined Component: geometry
Version: Boost Development Trunk Severity: Problem
Keywords: pythagoras, geos, douglas, peucker, algorithm Cc:


A problem with Polygon Douglas–Peucker simplification results have been reported.

There seems to be a bug in calculation of distance using Pythagoras Theorem. The problem is that the distance calculation is somehow omitting call to sqrt() leading to incomplete results.

It may be a problem with dispatching and execution execution paths in distance_pythagoras.hpp, so this part needs to be thoroughly reviewed.

Meanwhile, the patch attached provides a quick fix. The fix solves the reported problem, so the Boost.Geometry generates expected results. Also, the posted test case has been checked using GEOS and the patched distance_pythagoras generates results consistent with those obtained from GEOS. Means, the fix seems to be correct.

But, it causes number of unit test failures, so I decided to not to commit it this fix.

Barend, please get in touch when you will have a moment.

Attachments (2)

distance_pythagoras-sqrt-fix.patch (1021 bytes) - added by Mateusz Loskot 7 years ago.
Patch fixing missing sqrt() callin distance_pythagoras.hpp. Also fixes oordinates/points mismatch, trivial.
l01_multipolygon_simplify.cpp.log (1.2 KB) - added by Mateusz Loskot 7 years ago.
l01_multipolygon_simplify.cpp test run log

Download all attachments as: .zip

Change History (7)

Changed 7 years ago by Mateusz Loskot

Patch fixing missing sqrt() callin distance_pythagoras.hpp. Also fixes oordinates/points mismatch, trivial.

comment:1 Changed 7 years ago by Mateusz Loskot

Also, please check FIXME comment strategies/agnostic/simplify_douglas_peucker.hpp:148 (r74600)

comment:2 Changed 7 years ago by Mateusz Loskot

The test program is now in the trunk, as l01_multipolygon_simplify.cpp example (r74598)

Changed 7 years ago by Mateusz Loskot

l01_multipolygon_simplify.cpp test run log

comment:3 Changed 7 years ago by Mateusz Loskot

The patch has been proven incorrect as the sqrt is supposed to not to be called where I added it. However, I'm still confused why different strategy is selected in the simplify.

Here is illustration of what strategy is actually called:

#include <boost/geometry.hpp>
#include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
using namespace boost::geometry;

int main()
  typedef model::d2::point_xy<double> point_xy;

  point_xy p1(0.0, 0.0);
  point_xy p2(5.0, 0.0);

  // 1) This is direct call to Pythagoras algo
  typedef strategy::distance::pythagoras<point_xy, point_xy, double> strategy1_type;
  strategy1_type strategy1;
  strategy1_type ::calculation_type d1 = strategy1.apply(p1, p2);

  // 2) This is what is effectively called by simplify
  typedef strategy::distance::comparable::pythagoras<point_xy, point_xy, double> strategy2_type;
  strategy2_type strategy2;
  strategy2_type::calculation_type d2 = strategy2.apply(p1, p2);

  return 0;  

The 1) calls all expected implementation stages:

1 -> boost::geometry::strategy::distance::comparable::pythagoras<...>::apply() [Note 1]
2 ->-> boost::geometry::strategy::distance::pythagoras<...>::apply()
3 ->->-> sqrt()

Note 1, with the patch attached above, this will lead to double call to sqrt(), because the step 2 squares the result of step 1 (as expected), so the sqrt in step 1 is redundant and incorrect.

The 2) execution path seems to be missing the step 2 from the call stack above leading to no call to sqrt() at all what yields partial/incorrect result:

1 -> boost::geometry::strategy::distance::comparable::pythagoras<...>::apply() [Note 2]
3 ->->-> sqrt()

Note 2, that's why I hardcoded sqrt call in this function directly, but it is not correct in big picture, as explained in Note 1 above.

I'm having troubles with following the selection of pythagoras vs comparable. I may not understand well what's happening in boost::geometry::strategy::distance::services. So, all my hope in Barend!

comment:4 Changed 7 years ago by anonymous

Is this related #5730 ?

comment:5 Changed 7 years ago by Barend Gehrels

Resolution: fixed
Status: newclosed

(In [74761]) Fix ticket 5954, use strategy directly, not the comparable strategy (unless fixed otherwise)

Note: See TracTickets for help on using tickets.