Слияние определенных элементов в векторе c ++ или аналогичной структуре данных наиболее эффективным способом

Question

Как объединить определенные элементы в векторной или аналогичной структуре данных, выполнив итерацию по всему списку только один раз?Есть ли более эффективный способ, чем у меня есть?

У меня есть вектор векторов точек: std::vector<std::vector<cv::Point>> contours

И мне нужно всегда сравнивать два из них, а затем решать, буду ли яхотите объединить их или продолжить сравнение.

ContourMoments имеет некоторые вспомогательные функции, например, для вычисления расстояния между точками.Функция merge() только берет все точки из одного объекта ContourMoments и добавляет их к вызывающему объекту ContourMoments.

#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;
}

Заранее спасибо!

С наилучшими пожеланиями

Edit

опубликовал полный пример - сначала установите opencv

Это генерирует 2000 векторов до 10 точек и объединяет их, если они находятся близко друг к другу.

Answer 1

Для каждого из ваших контуров вы можете предварительно вычислить центры.Затем вы хотите сгруппировать контуры.Каждая пара контуров, центр которых находится на расстоянии не более d друг от друга, должна принадлежать одному кластеру.

Это можно сделать с помощью простого запроса радиуса.Например:

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

Для запроса радиуса я бы предложил что-то вроде kd tree .Введите все свои контуры в дерево, а затем вы можете запросить соседей в O(log n) вместо O(n), как вы делаете сейчас.

Для сливающейся части я бы предложил union-найти структуру данных .Это позволяет выполнять слияние практически в постоянное время.В конце вы можете просто собрать все данные контуров в большой кластерный контур.

Answer 2

Я не проверял твой код.Если вы хотите отсканировать вектор, сформировать группы смежных точек и выдать одну точку на группу в последовательности, например,

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

, то самое простое - выполнить операцию на месте.

Сохраняйте индекс после последней отправленной точки, пусть n (изначально 0), и всякий раз, когда вы отправляете новую, сохраняйте ее в array[n++], перезаписывая этот элемент, который уже был обработан.В конце измените размер массива.

Можно подумать о микрооптимизации, чтобы сравнить n с текущим индексом и избежать перезаписи элемента самим собой.В любом случае, как только элемент был отброшен, тест становится контрпродуктивным.