【详解】平面中最接近点对问题

红太狼 2022-06-15 12:56 197阅读 0赞

## 数组当中的最接近点对问题详解 ##

在一个一维数组当中要找出两个值相减得到的差值最小，当然有的人会说这个很简单，只要将数组当中的值两两相减，然后对最后的结果找一个最小值就可以了，这种方法想必是可以，这就是所谓的暴力解法，时间复杂度是非常大的。  
我们这里我介绍一种时间复杂度比较低的算法，我们利用分治的策略，将大规模的问题缩小化，首先我们将数组平分一半，左边的数值均小于右边的数值，但是左边和右边分别是乱序的，不需要排序，然后找到左边的最接近点的值，右边最接近点的值，当然还有可能左边的最大值和右边的最小值的差也可能是最小值，将这三个值作比较取最小值也就是最接近点的差值，有人会问那么左边和右边的最小值怎么计算呢，这就是分治的妙处所在了，左边和右边跟原问题是一样了的，只是规模减小了，因此方法一样，代码一样，使用递归就可实现。  
**代码**

const int MAXDISTENT = 0x7fffffff;
    int Select_K(int *ar, int left,int right, int k);
    int FindMax(int *ar, int left, int right)
    {
        int Max = ar[left];
        for (int i = left; i < right; i++)
        {
            if (Max < ar[i])
            {
                Max = ar[i];
            }
        }
        return Max;
    }
    int FindMin(int *ar, int left, int right)
    {
        int Min = ar[left];
        for (int i = left; i < right; i++)
        {
            if (Min > ar[i])
            {
                Min = ar[i];
            }
        }
        return Min;
    }
    int MyMin(int a, int b)
    {
        return a > b ? b : a;
    }
    int MyMin(int a, int b, int c)
    {
        return MyMin(MyMin(a, b), c);
    }
    int Cpair(int *ar, int left, int right)
    {
        if (right - left <= 0)
            return MAXDISTENT;
        int m = (right - left + 1)/2;
        Select_K(ar, left, right, m);
        int d1 = Cpair(ar, left, left+m - 1);//记得加left
        int d2 = Cpair(ar, left+m, right);
        int LMax = FindMax(ar, left, left+m - 1);
        int RMin = FindMin(ar, left+m, right);
        return MyMin(d1, d2, RMin-LMax);
    
    }
    int Cpair(int *ar, int len)
    {
        if (ar == NULL || len < 2)
            return MAXDISTENT;
        return Cpair(ar, 0, len - 1);
    }

## 平面中最接近点对问题详解 ##

平面中最接近点对的求解和上述的思想是一样的，还是采用分治的思想，但是处理起来就比较麻烦了，主要是左边和右边的点的距离的计算，中线的划分就按照x排个序取中就是中线，y轴上是同样的道理，纵向的三根线围起来的部分之间的点距离均大于左边和右边的最小距离d，而6个小方格里面，每个小方格里面最多一个点，因此，每个点只需要和这方格里面的点算距离就是最小距离  
![这里写图片描述][SouthEast]  
**代码**

#define MAXFLOAT 3.14e38f;
    
    struct Point_X
    {
        float x;
        float  y;
        int id;
        operator float()const{ return x; }
    };
    struct Point_Y
    {
        float x;
        float  y;
        int p;
        operator float()const { return y; }
    };
    /////////////////////////////////////
    template<class Type>
    void Merge(Type *sd, Type *si, int left, int m, int right)
    {
        int i = left, j = m + 1;
        int k = left;
        while (i <= m && j <= right)
        {
            sd[k++] = si[i] < si[j] ? si[i++] : si[j++];
        }
        while (i <= m)
        {
            sd[k++] = si[i++];
        }
        while (j <= right)
        {
            sd[k++] = si[j++];
        }
    }
    template<class Type>
    void Copy(Type *sd, Type *si, int left, int right)
    {
        for (int i = left; i <= right; ++i)
        {
            sd[i] = si[i];
        }
    }
    template<class Type>
    void MergePass(Type *br, Type *ar, int left, int right)
    {
        if (left < right)
        {
            int m = (right - left) / 2 + left;
            MergePass(br, ar, left, m);
            MergePass(br, ar, m + 1, right);
            Merge(br, ar, left, m, right);
            Copy(ar, br, left, right);
        }
    
    }
    template<class Type>
    void MergeSort(Type *ar, int n)
    {
        Type *br = new Type[n];
        MergePass(br, ar, 0, n - 1);
        delete[]br;
    }
    ///////////////////////////////////
    
    
    void PrintPoint(Point_X *point, int num)
    {
        for (int i = 0; i < NUM; i++)
        {
            cout <<point[i].id<<"=》"<< point[i].x << setw(6) << point[i].y << endl;
        } 
        cout << endl;
    }
    template<typename type>
    float Distance(const type &p1,const type &p2)
    {
        float dx = p1.x - p2.x;
        float dy = p1.y - p2.y;
        return sqrt(dx*dx + dy*dy);
    }
    float Closest(Point_X*X, Point_Y* Y, Point_Y*Z, int left,int right, Point_X&a, Point_X&b)
    {
        int num = right - left;
        if (num <= 0)
            return MAXFLOAT;
        if (num == 1)
        {
    
            a = X[left];
            b = X[right];
            return Distance(X[left], X[right]);
        }
        if (num == 2)
        {
            float dis1=Distance(X[left], X[left+1]);
            float dis2 = Distance(X[left + 1], X[left + 2]);
            float dis3 = Distance(X[left + 2], X[left]);
            if (dis1 < dis2&&dis1 < dis3)
            {
                a = X[left];
                b = X[left+1];
                return dis1;
            }
            if (dis2 < dis1&&dis2 < dis3)
            {
                a = X[left+1];
                b = X[left+2];
                return dis2;
            }
            else
            {
                a = X[left];
                b = X[left+2];
                return dis3;
            }
        }
        int m = (right - left) / 2 + left;
        //int z1 = left, m1 = m + 1;
    
        float d1 = Closest(X, Y,Z, left, m, a, b);
        Point_X a1, b1;
        float d2 = Closest(X, Y, Z, m + 1, right, a1, b1);
        float d = MAXFLOAT;
        if (d1 < d2)
            d = d1;
        else
        {
            d = d2;
            a = a1;
            b = b1;
        }
        //Merge(Y, Z, left, m, right);
        int k = left;
        for (int i = left; i < right;i++)
        {
            if (fabs(X[m].x - Y[i].x) < d)
            {
                Z[k++] = Y[i];
            }
        }
        for (int i = left; i < k; i++)
        {
            for (int j = i + 1; j < k; j++)
            {
                if (fabs(Z[i].y - Z[j].y) >= d)//Z中本来就是按照Y排序的，因此一旦遇到比d大的后面也就都比d大
                    break;
                float d3 = Distance(Z[i], Z[j]);
                if (d3 > d)
                {
                    a = X[Z[i].p];
                    b = X[Z[j].p];
                    d = d3;
                }
            }
        }
        return d;
    }
    float Cpair(Point_X*X, int num, Point_X &a, Point_X &b)
    {
        MergeSort(X, num);
        Point_Y *Y =new Point_Y[num];
        for (int i = 0; i < num; i++)
        {
            Y[i].p = i;
            Y[i].x = X[i].x;
            Y[i].y = X[i].y;
        }
        Point_Y *Z = new Point_Y[num];
        MergeSort(Y, num);
        float mindis = Closest(X, Y, Z, 0,num-1, a, b);
        return mindis;
    }

[SouthEast]: /images/20220615/e8d1efbd1a464405873b71e5399fe5ca.png