[Boost-bugs] [Boost C++ Libraries] #12268: Boost Polygon: Overflow issue with euclidean_distance() when using large (32-int) coordinates.

Subject: [Boost-bugs] [Boost C++ Libraries] #12268: Boost Polygon: Overflow issue with euclidean_distance() when using large (32-int) coordinates.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-06-14 07:46:32

#12268: Boost Polygon: Overflow issue with euclidean_distance() when using large
(32-int) coordinates.
--------------------------------------------+----------------------
 Reporter:  Pallav Gupta <drpallavgupta@…>  |      Owner:  ljsimons
     Type:  Bugs                            |     Status:  new
Milestone:  To Be Determined                |  Component:  polygon
  Version:  Boost 1.61.0                    |   Severity:  Problem
 Keywords:  euclidean_distance              |
--------------------------------------------+----------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/12268>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.