search

boostorg / polygon

Boost.org polygon module
http://boost.org/libs/polygon
57 stars 70 forks source link

Aboated at boost::polygon::polygon_set_data<long long>::get() #76

Open mleon08 opened 2 years ago

mleon08 commented 2 years ago

Executing this code aborted in version 1.66.0. I confirmed that aborted in version 1.79.0. Aborted when run in debug mode.

#include <stdio.h>
#include <stdlib.h>
#include <vector>

#include <boost/polygon/polygon.hpp>

namespace gtl = boost::polygon;
int main(int argc, char* argv[])
{
    gtl::polygon_set_data<long long>* polyset = new gtl::polygon_set_data<long long>;

    {
        gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
        std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
        vpoint.reserve(4);
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(346862000, 438294000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(346533000, 438337000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353343000, 490071000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353673000, 490027000));
        set_points(*ppoly, vpoint.begin(), vpoint.end());
        (*polyset).insert(*ppoly);
        delete ppoly;
    }

    {
        gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
        std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
        vpoint.reserve(4);
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353626000, 489671000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353176000, 489730000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353223000, 490087000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353673000, 490027000));
        set_points(*ppoly, vpoint.begin(), vpoint.end());
        (*polyset).insert(*ppoly);
        delete ppoly;
    }

    {
        gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
        std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
        vpoint.reserve(4);
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354911000, 489643000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354791000, 489659000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354838000, 490016000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354958000, 490000000));
        set_points(*ppoly, vpoint.begin(), vpoint.end());
        (*polyset).insert(*ppoly);
        delete ppoly;
    }

    {
        gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
        std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
        vpoint.reserve(4);
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353296000, 489714000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353176000, 489730000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353223000, 490087000));
        vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353343000, 490071000));
        set_points(*ppoly, vpoint.begin(), vpoint.end());
        (*polyset).insert(*ppoly);
        delete ppoly;
    }

    std::vector<gtl::polygon_data<long long>> result;
    polyset->get(result);

    delete  polyset;

    return 0;
}

This is the call stack and The value of the variable when aborting.

Please investigate the cause of the abort.

jsenn commented 7 months ago

I've just run into this issue, and it seems to cause a subsequent crash (though that could be unrelated).

This is an assertion failure when inserting a value into the std::map that holds scanline data. The assertion essentially checks that if a < b then !(b < a).

The buggy comparator is scanline_base::less_half_edge. It's easy to see that it's incorrect. For example, let a=(0, 0), b=(1, 1), c=(3, 2), and d=(4, 1). Let the first edge be elm1=a->b and the second elm2=c->d. In this case, less_half_edge will consider elm1 to be below elm2, but it will also consider elm2 to be below elm1!

I'm not sure what this function is trying to do exactly. It's comparing y values, but then also doing a cross product check, and yet it isn't sensitive to the orientation of the edges in some cases.

EDIT: actually, it looks like every failing case I've found is one in which there's no overlap between the 2 half-edges along the x axis. But in a scanline all elements by definition should overlap at at least one x-value (the current position of the scanline). Indeed, I've found that in the original geometry that tripped the assert for me, there are some edges in the scanline that don't overlap it at all. So the bug is probably in the inclusion of those edges rather than in the predicate being wrong.