Re: [Boost-bugs] [Boost C++ Libraries] #11470: Invalid results using convex_hull with unsigned integer points coordinates

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11470: Invalid results using convex_hull with unsigned integer points coordinates
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-07-10 13:20:21

#11470: Invalid results using convex_hull with unsigned integer points coordinates
-------------------------------------------------+-------------------------
  Reporter:  Eric Noirfalise                     |      Owner:
  <eric.noirfalise@…>                            |  barendgehrels
      Type:  Bugs                                |     Status:  new
 Milestone:  To Be Determined                    |  Component:  geometry
   Version:  Boost 1.58.0                        |   Severity:  Problem
Resolution:                                      |   Keywords:
-------------------------------------------------+-------------------------

Comment (by Eric Noirfalise <eric.noirfalise@…>):

 Ok after some code exploration I think that problem comes from :

 {{{
 template
     <
         typename CoordinateType,
         typename PromotedType,
         typename P1,
         typename P2,
         typename P,
         typename EpsPolicy
     >
 static inline
 PromotedType side_value(P1 const& p1, P2 const& p2, P const& p, EpsPolicy
 & eps_policy)
 {
         CoordinateType const x = get<0>(p);
         CoordinateType const y = get<1>(p);

         CoordinateType const sx1 = get<0>(p1);
         CoordinateType const sy1 = get<1>(p1);
         CoordinateType const sx2 = get<0>(p2);
         CoordinateType const sy2 = get<1>(p2);

         PromotedType const dx = sx2 - sx1;
         PromotedType const dy = sy2 - sy1;
         PromotedType const dpx = x - sx1;
         PromotedType const dpy = y - sy1;

         eps_policy = EpsPolicy(dx, dy, dpx, dpy);

         return geometry::detail::determinant<PromotedType>
                 (
                     dx, dy,
                     dpx, dpy
                 );

     }
 }}}
 in file boost/geometry/trategies/cartesian/side_by_triangle.hpp

 In my case :
 - CoordinateType = unsigned int
 - PromotedType = double

 So, for example, on line

 {{{
 PromotedType const dpy = y - sy1;
 }}}
 a case where y < sy1 will lead to wrong result.
 A simple cast of y to PromotedType like
 {{{
 PromotedType const dpy = PromotedType (y) - sy1;
 }}}
 should in my case solve the problem.

 If my understanding is good, PromotedType will be the most precise type
 between double and CoordinateType. So if I use input unsigned int 64, a
 similar error can happen and my correction will fail...

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