Ticket #5954 (closed Bugs: fixed)
distance_pythagoras skips sqrt() step
Reported by: | mloskot | Owned by: | barendgehrels |
---|---|---|---|
Milestone: | To Be Determined | Component: | geometry |
Version: | Boost Development Trunk | Severity: | Problem |
Keywords: | pythagoras,geos,douglas,peucker,algorithm | Cc: |
Description
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
Change History
Changed 3 years ago by mloskot
- attachment distance_pythagoras-sqrt-fix.patch added
comment:1 Changed 3 years ago by mloskot
Also, please check FIXME comment strategies/agnostic/simplify_douglas_peucker.hpp:148 (r74600)
comment:2 Changed 3 years ago by mloskot
The test program is now in the trunk, as l01_multipolygon_simplify.cpp example (r74598)
Changed 3 years ago by mloskot
- attachment l01_multipolygon_simplify.cpp.log added
l01_multipolygon_simplify.cpp test run log
comment:3 Changed 3 years ago by mloskot
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!
Patch fixing missing sqrt() callin distance_pythagoras.hpp. Also fixes oordinates/points mismatch, trivial.