时间戳

首页 > 解决方案 > 以最有效的方式合并 C++ 向量或类似数据结构中的某些元素

c++ - 以最有效的方式合并 C++ 向量或类似数据结构中的某些元素

问题描述

如何通过仅遍历完整列表一次来合并向量或类似数据结构中的某些元素？有没有比我所拥有的更有效的方法？

我有一个点向量的向量：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;
}

提前致谢！

最好的祝愿

编辑

发布了完整的示例 - 首先安装 opencv

这会生成最多 10 个点的 2000 个向量，如果它们靠近，则将它们合并。

标签： c++algorithmopencvc++11

解决方案

对于每个轮廓，您可以预先计算中心。然后，您要做的是对轮廓进行聚类。每对中心至多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-find data structure。这使您可以在几乎恒定的时间内进行合并。最后，您可以将所有轮廓数据收集到一个大的集群轮廓中。

推荐阅读