Invalid results using convex_hull with unsigned integer points coordinates

[Eric Noirfalise <eric.noirfalise@…>]

Hi, I think convex_hull algorithm does not support unsigned integer points coordinates.

The following code works well with signed integer but return a wrong result for unsigned version :

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <deque>
 

int main()
{
    typedef boost::geometry::model::d2::point_xy<unsigned int> PointInt;
    typedef boost::geometry::model::polygon<PointInt> polygon_type;

    polygon_type poly1, convPoly1;
    polygon_type poly2, convPoly2;
    boost::geometry::read_wkt("POLYGON((245 143, 243 113, 236 101, 228 100, 222 106, 217 121, 217 144, 220 155, 227 165, 233 166, 237 163, 245 143))", poly1);
    boost::geometry::convex_hull(poly1, convPoly1);

    return 0;
}

Attached file is a representation of input polygon (orange) and output result (blue) curve.

[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...

[anonymous]

Hi,

I just come to the news, will that bug be planned for correction ?

Regards, Eric Noirfalise