Modify

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)

distance_pythagoras-sqrt-fix.patch (1021 bytes) - added by Mateusz Loskot 6 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 6 years ago.
l01_multipolygon_simplify.cpp test run log

Download all attachments as: .zip

Change History (7)

Changed 6 years ago by Mateusz Loskot

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

comment:1 Changed 6 years ago by Mateusz Loskot

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

comment:2 Changed 6 years ago by Mateusz Loskot

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

Changed 6 years ago by Mateusz Loskot

l01_multipolygon_simplify.cpp test run log

comment:3 Changed 6 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 6 years ago by anonymous

Is this related #5730 ?

comment:5 Changed 6 years ago by Barend Gehrels

Resolution: fixed
Status: newclosed

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Barend Gehrels.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.