id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
12268,Boost Polygon: Overflow issue with euclidean_distance() when using large (32-bit) coordinates.,Pallav Gupta <drpallavgupta@…>,Lucanus Simonson,"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.

",Bugs,new,To Be Determined,polygon,Boost 1.61.0,Problem,,euclidean_distance,