Boost Polygon: Overflow issue with euclidean_distance() when using large (32-bit) coordinates.

[Pallav Gupta <drpallavgupta@…>]

Hi,

When using large (32-bit) ints for coordinates, there seems to be a problem in getting the correct result with boost::polygon::euclidean_distance(). The sample program demonstrates the issue (compiled with GCC 4.7.3 + Boost 1.61.0).

#include <iostream>
#include <cmath>
#include <boost/polygon/polygon.hpp>
#include <boost/geometry.hpp>

namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

typedef gtl::rectangle_data<int> LayoutRectangle;

int main(int argc, char** argv)
{
    LayoutRectangle t(16740130,29759232,16740350,29760652);
    LayoutRectangle n(16808130,29980632,16808350,29982052);

    std::cout << gtl::euclidean_distance(t, n) << std::endl;

    std::cout << gtl::euclidean_distance(t, n, gtl::HORIZONTAL) << " "
              << gtl::euclidean_distance(t, n, gtl::VERTICAL) << std::endl;

    std::cout << gtl::square_euclidean_distance(t, n) << std::endl;
    std::cout << std::sqrt(gtl::square_euclidean_distance(t, n)) << std::endl;
    std::cout << (int) std::sqrt(gtl::square_euclidean_distance(t, n)) << std::endl;

    return 0;
}

The output of this program is:

38022.6 67780 219980 52985328800 230185 230185

230185 is the correct answer, but euclidean_distance() gives 38022.6. I traced the program above in GDB, and the culprit seems to be 'return (xdist * xdist) + (ydist * ydist)' in the library code shown below. xdist/ydist have correct values but taking the square root is most likely causing overflow.

rectangle_concept.hpp:

  square_euclidean_distance(const rectangle_type& lvalue, const rectangle_type_2& rvalue) {
    typename coordinate_traits<typename rectangle_coordinate_type<rectangle_type>::type>::coordinate_difference xdist, ydist;
    xdist = euclidean_distance(lvalue, rvalue, HORIZONTAL);
    ydist = euclidean_distance(lvalue, rvalue, VERTICAL);
    return (xdist * xdist) + (ydist * ydist);
  }

I notice coordinate_difference is defined as 'long long' which is 8 bytes (sizeof(long long)) on my machine. So not sure why this is happening.

I also posted this as a question on stackoverflow: ​http://stackoverflow.com/questions/37804930/boost-polygon-issue-with-euclidean-distance

For now, I can use std::sqrt(gtl::square_euclidean_distance())' as a workaround. Thanks.

[anonymous]

I think the problem is in the code fragment below. Don't know why the return value of square_euclidean_distance() is being casted on an 'int'.

  template <typename rectangle_type, typename rectangle_type_2>
  typename enable_if< typename gtl_and_3<y_r_edist2, typename is_rectangle_concept<typename geometry_concept<rectangle_type>::type>::type,
                                                          typename is_rectangle_concept<typename geometry_concept<rectangle_type_2>::type>::type>::type,
                       typename rectangle_distance_type<rectangle_type>::type>::type
  euclidean_distance(const rectangle_type& lvalue, const rectangle_type_2& rvalue) {
    double val = (int)square_euclidean_distance(lvalue, rvalue);
    return std::sqrt(val);
  }