jeudi 28 juillet 2016

Partition std::vector of 2D points

Suppose I have a std::vector<Point> where Point is struct Point { double x; double y;} I'd like to partition such a vector into groups (buckets), where all Points in same bucket have same Euclidean norm between each other (e.g dist(PointA,PointB) == X, where X is constant). I've decided to use std::map for such task with custom sorting operator:

struct ClosePoints
{
    bool operator()(Point const& A, Point const& B) const
    {
        bool same = dist(A,B) < x;
        //If not close enough use lexical sort
        return same ? false : std::tie(A.x, A.y) < std::tie(B.x,); 
    }
}

Partitioning code:

std::map<Point, std::list<Point>, ClosePoints> map;
for(const auto& p : pointsVector)
    map[p].push_back(p);

After some testing and printing the buckets I've noticed that some points that do obey given Euclidean norm limit X ended in different buckets. I can't figure out why is it so ?

Aucun commentaire:

Enregistrer un commentaire