Opened 6 years ago
Closed 6 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: |
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 (2)
Change History (7)
Changed 6 years ago by
Attachment: | distance_pythagoras-sqrt-fix.patch added |
---|
comment:1 Changed 6 years ago by
Also, please check FIXME comment strategies/agnostic/simplify_douglas_peucker.hpp:148 (r74600)
comment:2 Changed 6 years ago by
The test program is now in the trunk, as l01_multipolygon_simplify.cpp example (r74598)
Changed 6 years ago by
Attachment: | l01_multipolygon_simplify.cpp.log added |
---|
l01_multipolygon_simplify.cpp test run log
comment:3 Changed 6 years ago by
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:5 Changed 6 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
(In [74761]) Fix ticket 5954, use strategy directly, not the comparable strategy (unless fixed otherwise)
Patch fixing missing sqrt() callin distance_pythagoras.hpp. Also fixes oordinates/points mismatch, trivial.