Merging certain elements in a c++ vector or similar data structure in the most efficient way

Question

How do I merge certain elements in a vector or similar data structure by only iterating over the complete list once? Is there a more efficient way than what I have got?

I have a vector of vectors of points: std::vector<std::vector<cv::Point>> contours

And I need to compare always two of them and then decide if I want to merge them or continue comparing.

ContourMoments has some helper functions to calculate the distance between points for example. The function merge() only takes all the points from one ContourMoments object and adds them to the calling ContourMoments object.

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>

#include <opencv/cv.h>
#include <opencv2/imgproc/imgproc.hpp>


class ContourMoments
{
private:
    void init()
    {
        moments = cv::moments(contour);
        center = cv::Point2f(moments.m10 / moments.m00, moments.m01 / moments.m00);
        float totalX = 0.0, totalY = 0.0;
        for (auto const&p : contour)
        {
            totalX += p.x;
            totalY += p.y;
        }
        gravitationalCenter = cv::Point2f(totalX / contour.size(), totalY / contour.size());
    }
public:
    cv::Moments moments;
    std::vector<cv::Point2f> contour;
    cv::Point2f center;
    cv::Point2f gravitationalCenter;
    
    ContourMoments(const std::vector<cv::Point2f> &c)
    {
        contour = c;
        init();
    }
    
    ContourMoments(const ContourMoments &cm)
    {
        contour = cm.contour;
        init();
    }
    
    void merge(const ContourMoments &cm)
    {
        contour.insert(contour.end(), std::make_move_iterator(cm.contour.begin()), std::make_move_iterator(cm.contour.end()));
        init();
    }
    
    float horizontalDistanceTo(const ContourMoments &cm)
    {
        return std::abs(center.x - cm.center.x);
    }

    float verticalDistanceTo(const ContourMoments &cm)
    {
        return std::abs(center.y - cm.center.y);
    }

    float centerDistanceTo(const ContourMoments &cm)
    {
        return std::sqrt(std::pow(center.x - cm.center.x, 2) + std::pow(center.y - cm.center.y, 2));
    }
    
    ContourMoments() = default;
    ~ContourMoments() = default;
};

float RandomFloat(float a, float b) {
    float random = ((float) rand()) / (float) RAND_MAX;
    float diff = b - a;
    float r = random * diff;
    return a + r;
}

std::vector<std::vector<cv::Point2f>> createData()
{
    std::vector<std::vector<cv::Point2f>> cs;
    for (int i = 0; i < 2000; ++i) {
        std::vector<cv::Point2f> c;
        int j_stop = rand()%11;
        for (int j = 0; j < j_stop; ++j) {
            c.push_back(cv::Point2f(RandomFloat(0.0, 20.0), RandomFloat(0.0, 20.0)));
        }
        cs.push_back(c);
    }
    return cs;
}

void printVectorOfVectorsOfPoints(const std::vector<std::vector<cv::Point2f>> &cs) {
    std::cout << "####################################################" << std::endl;
    for (const auto &el : cs) {
        bool first = true;
        for (const auto &pt : el) {
            if (!first) {
                std::cout << ", ";
            }
            first = false;
            std::cout << "{x: " + std::to_string(pt.x) + ", y: " + std::to_string(pt.y) + "}";
        }
        std::cout << std::endl;
    }
    std::cout << "####################################################" << std::endl;
}

void merge(std::vector<std::vector<cv::Point2f>> &contours, int &counterMerged){
    for(auto it = contours.begin() ; it < contours.end() ; /*++it*/)
    {
        int counter = 0;
        if (it->size() < 5)
        {
            it = contours.erase(it);
            continue;
        }
        for (auto it2 = it + 1; it2 < contours.end(); /*++it2*/)
        {
            if (it2->size() < 5)
            {
                it2 = contours.erase(it2);
                continue;
            }
            ContourMoments cm1(*it);
            ContourMoments cm2(*it2);
            if (cm1.centerDistanceTo(cm2) > 4.0)
            {
                ++counter;
                ++it2;
                continue;
            }
            counterMerged++;
            cm1.merge(std::move(cm2));
            it2 = contours.erase(it2);
        }
        if (counter > 0)
        {
            std::advance(it, counter);
        }
        else
        {
            ++it;
        }
    }
}

int main(int argc, const char * argv[])
{
    srand(time(NULL));
    std::vector<std::vector<cv::Point2f>> contours = createData();
    printVectorOfVectorsOfPoints(contours);
    int counterMerged = 0;
    merge(contours, counterMerged);
    printVectorOfVectorsOfPoints(contours);
    std::cout << "Merged " << std::to_string(counterMerged) << " vectors." << std::endl;
    return 0;
}

Thanks in advance!

Best wishes

Edit

posted the complete example - install opencv first

This generates 2000 vectors of up to 10 points and merges them if they are close together.

Answer 1

For each of your contours, you can pre-compute the centers. Then, what you want to do is to cluster the contours. Each pair of contours whose center is at most a distance of d apart should belong to the same cluster.

This can be done with a simple radius query. Like this:

for each contour ci in all contours
    for each contour cj with cluster center at most d away from ci
        merge cluster ci and cj

For the radius query, I would suggest something like a k-d tree. Enter all your contours into the tree and then you can query for the neighbors in O(log n) instead of O(n) like you are doing now.

For the merging part, I would suggest a union-find data structure. This lets you do the merge in practically constant time. At the end, you can just gather all your contour data into a big cluster contour.

Answer 2

I didn't scrutinize your code. If what you want to do is to scan the vector, form groups of contiguous points and emit a single point per group, in sequence, e.g.

a b c|d e|f g h|i j k|l => a b c d f i l

the simplest is to perform the operation in-place.

Keep an index after the last emitted point, let n (initially 0), and whenever you emit an new one, store it at array[n++], overwriting this element, which has already been processed. In the end, resize the array.

One might think of a micro-optimization to compare n to the current index, and avoid overwriting an element with itself. Anyway, as soon as an element has been dropped, the test becomes counter-productive.