编程之美2.11：寻找最近的点对

2023-09-25 12:35:22

求点集中的最近点对有以下两种方法:

设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

 解体思路

1、蛮力法（适用于点的数目比较小的情况下）

     1）算法描述：已知集合S中有n个点，一共可以组成n(n-1)/2对点对，蛮力法就是对这n(n-1)/2对点对逐对进行距离计算，通过循环求得点集中的最近点对：

     2）代码描述：

double MinDistance = double.maxvalue；  //设置一个MinDistance存储最近点对的距离，初始值为无穷大

int PointIndex1,PointIndex2； //设置PointIndex1,PointIndex2分别存储最近点对的两个点编号

for (i=1; i< n; i++)    //循环计算n(n-1)/2对点对的距离
{

     for (j=i+1; j<=n; j++)
     {

           double PointDistance = Distance(S[i],S[j]);   //求得point i和point j之间的距离

           if PointDistance < MinDistance;  //如果当前点对距离小于最小点对距离，则设置最小点对距离等于当前点对距离

           {

                 MinDistance = PointDistance;

                 PointIndex1 = i;

                 PointIndex2 = j;

            }

       }

 }

      }  
     3）算法时间复杂度：算法一共要执行 n(n-1)/2次循环，因此算法复杂度为O(n2)

 

2、分治法

     1）算法描述：已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点对。算法每次选择一条垂线L，将S拆分左右两部分为SL和SR，L一般取点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2，

（否则以其他方式划分S，有可能导致SL和SR中点数目一个为1，一个为n-1，不利于算法效率，要尽量保持树的平衡性）

依次找出这两部分中的最小点对距离：δL和δR，记SL和SR中最小点对距离δ= min（δL，δR），如图1：

   

编程之美2.11：寻找最近的点对

     以L为中心，δ为半径划分一个长带，最小点对还有可能存在于SL和SR的交界处，如下图2左图中的虚线带，p点和q点分别位于SL和SR的虚线范围内，在这个范围内，p点和q点之间的距离才会小于δ，最小点对计算才有意义。

    

编程之美2.11：寻找最近的点对

 

 

Figure 2

 

 

      对于SL虚框范围内的p点，在SR虚框中与p点距离小于δ的顶多只有六个点，就是图二右图中的2个正方形的6的顶点。这个可以反推证明，如果右边这2个正方形内有7个点与p点距离小于δ，例如q点，则q点与下面正方形的四个顶点距离小于δ，则和δ为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点，不需求出p点和右边虚线框内所有点距离，只需计算SR中与p点y坐标距离最近的6个点，就可以求出最近点对，节省了比较次数。

（否则的话，最坏情形下，在SR虚框中有可能会有n/2个点，对于SL虚框中的p点，每次要比较n/2次，浪费了算法的效率） 

代码描述：

     1）对点集S的点x坐标进行升序排序，获得点集point[] array

     2）令δ=∞;   //δ为最大点位距离

     3）Divide_conquer（point[] array,left，right）  //分治法

             if （left == right） then δ=∞;    //如果point[]中只有一个点，则δ=∞

                  return δ;

             else if (right - left ==1) // point[]中只有2个点，则直接求这两个点的距离

                   δ=d（Sx.[0],）Sx.[1]）; 

                   return δ;

             else    //如果point[]中多于2个点，则将point[]分治，以中心点画线，将point[]分为左右两部分A和B，

                  mid = (LeftIndex + rightIndex)>>1;   //mid为当前段中的中间点index           

　　　　　　double d1 = Closest_Pair(leftIndex,mid);                  

　　　　　　double d2 = Closest_Pair(mid +1,rightIndex); 

                  d  =min(d1,d2);  

 　　　　　  list<point> leftList = new <point>();

 　　　　　  list<point> lrightList = new <point>();

            // 分离出宽度为d,距point[mid]<=d的区间，其实也就是化了两条平行于x= point[mid].x的竖线。（之后还需要根据左边A的p,在右边选距离p.y<=d,在化两条横线，这样一个动态的矩形也就化出来了。(矩形包含两个正方形，一条边重合，也就是最多存在6（顶)点（鸽巢原理）,可能满足条件     （如上面的图figure2）

循环遍历 数组

  1. if (fabs(point[mid].x -point[i].x) <=d && i <= mid)

     leftList.add(point[i] //左边符合条件的点

  2. if (fabs(point[mid].x -point[i].x) <=d && i > mid)

      rightList.add(point[i]) //右边符合条件的点

   

// 线性扫描

  foreach ( point leftPoint in leftList)

  {

　　foreach(point rightPoint in rightList)

             d3=dis(leftPoint, rihgtPoint); //求左边点和右边点的最小值

            if (d >d3)

　　　　{

               d =d3; //更新最小值
　　　　}

}  

 return d;       

 

详细的代码如下：

 

?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication4
{
    public class Point
    {
 
        public Point(double a, double b)
        {
            X = a;
            Y = b;
        }
        double x;
 
        public double X
        {
            get { return x; }
            set { x = value; }
        }
 
        double y;
 
        public double Y
        {
            get { return y; }
            set { y = value; }
        }
 
        public static void Copy (Point a, Point b)
        {           
            a.X = b.X;
            a.Y = b.Y;
        }
 
        bool CompyX(Point a, Point b)
        {
            if (a.X != b.X)
            {
                return a.x < a.y;
            }
 
            return a.y < b.y;
        }
 
        public static double Dis(Point a, Point b)
        {
            return Math.Sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
        }
    }
 
    public static class SortHelper
    {
        public static void MergeSortByx(Point[] array)
        {
            int increaseMent = 1;
 
            while (increaseMent < array.Length)
            {
                MergeByx(array, increaseMent);
                increaseMent <<= 1;
            }
        }   
 
        public static void MergeByx(Point[] array, int increaseMent)
        {
            Point[] tempArray = new Point[array.Length];
 
            for (int t = 0; t < tempArray.Length; t++)
            {
                tempArray[t] = new Point(0, 0); // 初始化
            }
 
            int lastIndex = array.Length - 1;
 
            int l1 = 0;   //第1个有序表的起始位置
            int h1 = 0;   //第1个有序表的结束位置
            int l2 = 0;   //第2个有序表的起始位置
            int h2 = 0;   //第2个有序表的结束位置
 
            int m = 0;   //临时表的初始位置
 
 
            // 注意这里的临界条件(l2要存在，L2的index是： l1 + increaseMent<=lastIndex)
            while (l1 + increaseMent <= lastIndex)
            {
                l2 = l1 + increaseMent;
                h1 = l2 - 1;
                h2 = l2 + increaseMent - 1 < lastIndex ? l2 + increaseMent - 1 : lastIndex;
 
                int i = l1;
                int j = l2;
 
                //两个有序表中的记录没有排序完
                while (i <= h1 && j <= h2)
                {
                    //第1个有序表记录的关键码小于第2个有序表记录的关键码
                    if (array[i].X < array[j].X)
                    {
 
                        Point.Copy(tempArray[m], array[i]);
                        m++;
                        i++;                       
                    }
                    else //第2个有序表记录的关键码小于第1个有序表记录的关键码
                    {
                        Point.Copy(tempArray[m], array[j]);
                        m++;
                        j++;
                    }
                }
 
                //第1个有序表中还有记录没有排序完
                while (i <= h1)
                {
                    Point.Copy(tempArray[m], array[i]);
                    m++;
                    i++;
                }
 
                //第2个有序表中还有记录没有排序完
                while (j <= h2)
                {
                    Point.Copy(tempArray[m], array[j]);
                    m++;
                    j++;
                }
 
                l1 = h2 + 1;
            }
 
            //原顺序表中还有记录没有排序完
            while (l1 <= lastIndex)
            {
                Point.Copy(tempArray[m], array[l1]);
                m++;
                l1++;
            }
 
            //临时顺序表中的记录复制到原顺序表，使原顺序表中的记录有序
            for (int i = 0; i < array.Length; i++)
            {
                Point.Copy(tempArray[i], array[i]);
                m++;
                i++;
            }
        }      
    }
 
    public class CalculateHelper
    {
        public double GetClosetDistant(Point[] array)
        {
           return GetClosetDistant(array, 0, array.Length - 1);
        }
 
        public double GetClosetDistant(Point[] array, int leftIndex, int rightIndex)
        {
            double distant = double.MaxValue;
 
            //情况一： 当前区域只有一个点时，返回最大值，即当前值无效 (出口一）
            if (leftIndex == rightIndex)
            {
                return distant;
            }
 
            // 情况二：当前区域只有两个点时，直接返回这两个点的距离 (出口二）
            if (leftIndex + 1 == rightIndex)
            {
               return  Point.Dis(array[leftIndex], array[rightIndex]);
            }
 
            // 按照x排序
            SortHelper.MergeSortByx(array);
 
            // 情况三，当前区域点的个数大于2的时候,需要采用分治法，把当前区域分成左右两个部分,直到满足情况一或二
 
            int midIndex = (leftIndex + rightIndex) >> 1;
            double leftDistance = GetClosetDistant(array, leftIndex, midIndex);
            double rightDistance = GetClosetDistant(array, midIndex + 1, rightIndex);
 
            distant = Math.Min(leftDistance, rightDistance); //求出左右两边区域的最小距离
 
            if (distant < 0.43)
            {
                distant = distant;
            }
 
            for (int i = leftIndex; i <= midIndex; i++) //遍历左边的点
            {
                if (Math.Abs(array[i].X- array[midIndex].X) <distant) //选出左边区域距离x = array[midIndex].x <d的点 (画左边的1条竖线）                 
                {
                    for (int j = midIndex + 1; j <= rightIndex; j++) //遍历右边的点
                    {
                        if (Math.Abs(array[i].X - array[midIndex].X) < distant) //选出左边区域距离x = array[midIndex].x <d的点 (画右边的1条竖线）
 
                            if (Math.Abs(array[i].Y - array[midIndex].Y) < distant) // 画出两条平行于 y= array[midIndex].Y的两条横线,到这一步时，
                                //矩形区域已经画好了，符合条件的点最多有6个
                        {
                            double bothDistance = Point.Dis(array[i], array[j]); //计算左右点的距离
 
                            if (bothDistance < distant)
                            {
                                distant = bothDistance; // 更新最小距离
                            }
 
                            if (distant < 0.43)
                            {
                                distant = distant;
                            }
                        }
                    }
                }
            }
 
            if (distant < 0.43)
            {
                distant = distant;
            }
            return distant;
        }
    }
}
<br> // 主函数
 static void Main(string[] args)
        {
            CalculateHelper helper = new CalculateHelper();
 
            Point[] array = new Point[14];
 
            array[0] = new Point(2, 2);
            array[1] = new Point(0.5, 0.5);
            array[2] = new Point(0.25, 1);
            array[3] = new Point(1, 2);
 
            array[4] = new Point(3, 1);
            array[5] = new Point(2, 0.7);
            array[6] = new Point(1, 1);
            array[7] = new Point(0.6, 0.8);
 
            array[8] = new Point(0.9, 0.5);
            array[9] = new Point(2, 1);
            array[10] = new Point(4, 2);
            array[11] = new Point(1.1, 0.5);
 
            array[12] = new Point(8, 0.5);
            array[13] = new Point(0.7, 2);
 
            double dintance = helper.GetClosetDistant(array);
        }

　

编程之美2.11：寻找最近的点对

上一篇：咏南GO数据库中间件


下一篇：Photoshop画笔绘制夜空彩色星光