寻找最近点对

落日映苍穹つ 2022-06-10 09:51 209阅读 0赞

在有n(n>=2)个点构成的集合Q中寻找最近的点对。其中的最近是通常意义下的欧几里得距离，即，点p1=\{x1,y1\},p2=\{x2,y2\},则它们之间的距离为sqrt((x2-x1)\*(x2-x1)+(y2-y1)\*(y2-y1))。这一问题可应用于交通控制，以便于发现两个距离最近的交通工具，避免可能发生的交通事故。

分治算法：

\#include <iostream>  
\#include <vector>  
\#include <algorithm>  
  
using namespace std;  
  
\#define min(a,b) ((a)<(b)?(a):(b))  
\#define MAXINT 0x7fffffff  
  
class point  
\{  
public:  
    int x;  
    int y;  
  
    point(int xPos,int yPos):x(xPos),y(yPos)\{\}  
\};  
  
bool CompareByX(const point& p1,const point& p2)  
\{  
    return p1.x<=p2.x;  
\}  
  
bool CompareByY(const point& p1,const point& p2)  
\{  
    return p1.y<=p2.y;  
\}  
  
int GetDistance(const point& p1,const point& p2)  
\{  
    return (p2.x - p1.x)\*(p2.x - p1.x) + (p2.y - p1.y)\*(p2.y - p1.y);  
\}  
  
int GetMiniDistance(vector<point>& v1)  
\{  
    if(v1.size()<=1)  
        return MAXINT;  
      
    if(v1.size() == 2)  
        return GetDistance(v1\[0\],v1\[1\]);  
  
    vector<point>::iterator midItr = v1.begin()+ v1.size()/2;  
    vector<point> vl(v1.begin(),midItr);  
    vector<point> vr(midItr,v1.end());  
    int distance = min(GetMiniDistance(vl),GetMiniDistance(vr));  
  
    vector<point> vt;  
    for(size\_t k = 0;k<v1.size();++k)  
    \{  
        if(abs(v1\[k\].x - midItr->x)<distance)  
            vt.push\_back(v1\[k\]);  
    \}  
  
    sort(vt.begin(),vt.end(),CompareByY);  
  
    for(size\_t i = 0;i<vt.size();++i)  
        for(size\_t j=i+1;j<min(i+7,vt.size());++j)  
        \{  
            int temp = GetDistance(vt\[i\],vt\[j\]);  
            if(temp<distance)  
                distance = temp;  
        \}  
  
        return distance;  
\}  
void CalcMiniDistance(vector<point> &vec)  
\{  
    vector<point> vecX(vec);  
    vector<point> vecY(vec);  
  
    sort(vecX.begin(),vecX.end(),CompareByX);  
    sort(vecY.begin(),vecY.end(),CompareByY);  
  
    cout<<GetMiniDistance(vecX)<<endl;  
  
\}  
  
int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
    point p\[5\]= \{point(0,0),point(1,1),point(3,3),point(6,5),point(12,10)\};  
  
    vector<point>vec(p,p+5);  
  
    CalcMiniDistance(vec);  
  
    system("pause");  
    return 0;

算法参考了算法导论，但是没有达到算法导论上讲的时间复杂度，以后继续改进吧。