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

Question

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

我有一个由点 vector 组成的 vector :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 个 vector ，如果它们靠得很近，则将它们合并。

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

对于半径查询，我会建议类似 k-d tree 的查询.将所有轮廓输入到树中，然后您可以在 O(log n) 中查询邻居，而不是像现在那样在 O(n) 中查询。

对于合并部分，我建议使用 union-find data structure .这使您可以在几乎恒定的时间内进行合并。最后，您可以将所有轮廓数据收集到一个大的集群轮廓中。