c++ - 相互比较点元素的最快方法是什么？我使用Nested for loop做到了，但这很慢

我想找到点之间的距离小于3的点，例如以下一些点，
(220,221)(220,119)(220,220)(20,90)(220,222)。
我使用(220,221)查找点。然后我可以获得(220,221)(220,119)(220,220)(220,222)
我使用(220,119)查找点，然后我可以获得(220,221)(220,119)(220,220)
我已经使用Nested for循环来做到这一点，但是它非常慢。它的工作效率很低。代码如下，

#include <opencv2/core/core.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <iostream>
#include <math.h>
using namespace cv;
using namespace std;

int main()
{

    vector<Point>  p;
    vector<Point> temp;
    vector<vector<Point> > centerbox;

    p.push_back(Point(110, 110));
    p.push_back(Point(110, 111));
    p.push_back(Point(110, 110));
    p.push_back(Point(110, 112));
    p.push_back(Point(111, 112));
    p.push_back(Point(150, 111));


    for (vector<Point> ::iterator iter1 = p.begin(); iter1 != p.end(); ++iter1) {


        for (vector<Point> ::iterator iter2 = p.begin(); iter2 != p.end();) {



            if (abs((*iter1).x - (*iter2).x) + abs((*iter1).y - (*iter2).y) < 3) {

                temp.push_back((*iter2));
                ++iter2;
            }
            else {
                ++iter2;
            }
        }


        centerbox.push_back(temp);

        temp.clear();

    }

        return 0;
}

与使用嵌套for循环相比，我如何做得更快？

最佳答案

对于20000个随机点，每个点大约有27个邻居，此函数使我加快了速度。与原始方法相比，它所需的时间减少了约33％。

std::vector<std::vector<cv::Point> > findNeighborsOptimized(std::vector<cv::Point> p, float maxDistance = 3.0f)
{

    std::vector<std::vector<cv::Point> > centerbox(p.size()); // already create a output vector for each input point

    /*
    // if you  have enough memory, you can reserve enough space for each point. If not, just remove this part, which will result in a lot of reallocations later.
    //unsigned int reserveSize = p.size(); // definitely enough space so no reallocations will happen but probably too much space reserved...
    //unsigned int reserveSize = p.size()/2;
    //unsigned int reserveSize = p.size()/3;
    //unsigned int reserveSize = p.size()/10;
    unsigned int reserveSize = 1;

    for(unsigned int i=0; i<centerbox.size(); ++i)
    {
        centerbox[i].reserve(reserveSize);
    }
    */
    // for me it turned out to be slower to reserve a lot of memory... maybe because of caching?!?
    // will depend on the average number of neighbors for each point...


    for(unsigned int j=0; j<p.size(); ++j)
    {
        std::vector<cv::Point> & p1Neighbors = centerbox[j];

        // create a reference to the point so that we dont need to GET it several times
         cv::Point & p1 = p[j];
         //p1Neighbors.push_back(p1); // uncomment this if you want to show the point be a neighbor of itself (dist to itself is alway == 0).
         // for p2 ignore p1 and start at the next point

         for(unsigned int i=j+1; i<p.size(); ++i)
         {
             cv::Point & p2 = p[i];

             // instead you might want to use cv::norm(p1-p2) or something, but I'll stay at your original logic
            if(abs(diff.x) + abs(diff.y) < maxDistance)
             {
                 p1Neighbors.push_back(p2);
                 // add p1 to neighbors of p2 too
                 centerbox[j].push_back(p1);
             }
         }
    }


    return centerbox;
}

根据应用程序中的点数以及它们的分布，空间分区或空间哈希可能会给您带来更好的改进。

关于c++ - 相互比较点元素的最快方法是什么？我使用Nested for loop做到了，但这很慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30963847/