Modify

Opened 2 years ago

Last modified 2 years ago

#11470 new Bugs

Invalid results using convex_hull with unsigned integer points coordinates

Reported by: Eric Noirfalise <eric.noirfalise@…> Owned by: Barend Gehrels
Milestone: To Be Determined Component: geometry
Version: Boost 1.58.0 Severity: Problem
Keywords: Cc:

Description

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.

Attachments (1)

Clipboard02.tif (15.0 KB) - added by Eric Noirfalise <eric.noirfalise@…> 2 years ago.

Download all attachments as: .zip

Change History (3)

Changed 2 years ago by Eric Noirfalise <eric.noirfalise@…>

Attachment: Clipboard02.tif added

comment:1 Changed 2 years ago 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 :

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

comment:2 Changed 2 years ago by anonymous

Hi,

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

Regards, Eric Noirfalise

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain Barend Gehrels.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.