问题：平面点集求其中距离最近的两个点及其距离。

思路：采用分治法，将“求n个点之间最小距离”问题划分为很多个“求n/t个点之间最小距离”问题。

（1）将lstPoint根据X坐标由小到大排序得到点集pointsSortedX，方法很多，冒泡、选择、插入、归并，快排等，本文采用快排，其优点就不多说了。

（2）pointsSortedX为一个点集，可以采用二分法分为两个数量均分的点集pointsX1（[0,indexMid]），pointsX2（[indexMid,Count-1]），对于每个分点集，求其中距离最近的两个点及其距离，方法如前，采用递归求解；

（3）对于2个分点集，可得两个最小距离，取其小者，为分点集各自内的最小距离dis，但是仍然存在这种情况，即可能存在两个点分别位于两个分点集中，所以还需考虑2个分点集间的情况。而参考已求得的dis，2个分点集间区域可根据X坐标取

X∈[pointsSortedX[indexMid].X - dis,pointsSortedX[indexMid].X + dis]范围的点并构成临时点集pointsTemp；

（4）将点集pointsTemp根据Y坐标进行由小到大排序，对于每个点ptCurrent，求Y坐标∈[ptCurrent.Y - dis, ptCurrent.Y + dis]的点ptCurrent的距离，并与dis取最小赋给dis；

图解如下：

讯享网

图1 根据X坐标排序

图2 二分法分解

图3 递归求解并考虑区域间点距离最小情况

图4 代码运行效果

public class ShortestDisPointFinder { public delegate bool CompareDelegate(HPoint2d point0, HPoint2d point1); public class ShortestDisPointResult { public ShortestDisPointResult(double dis, HPoint2d point0, HPoint2d point1) { Distance = dis; Point0 = point0; Point1 = point1; } public double Distance { get; set; } public HPoint2d Point0 { get; set; } public HPoint2d Point1 { get; set; } } private List<HPoint2d> m_lstPoint; public ShortestDisPointFinder(List<HPoint2d> lstPoint) { m_lstPoint = new List<HPoint2d>(lstPoint); } public ShortestDisPointResult GetShortestDistance() { // 首先按X坐标排序 QuikSort(m_lstPoint, 0, m_lstPoint.Count - 1, CompareX); // 分治法求最短距离 return Binarysearch(m_lstPoint, 0, m_lstPoint.Count - 1); } private ShortestDisPointResult Binarysearch(List<HPoint2d> lstPoint, int indexS, int indexE) { if (indexS + 1 == indexE) return new ShortestDisPointResult(lstPoint[indexE].Distance(lstPoint[indexS]), lstPoint[indexS], lstPoint[indexE]); else if (indexS + 2 == indexE) { double dis1 = lstPoint[indexE].Distance(lstPoint[indexS]); double dis2 = lstPoint[indexS + 1].Distance(lstPoint[indexS]); double dis3 = lstPoint[indexS + 1].Distance(lstPoint[indexE]); var result = new ShortestDisPointResult(dis1, lstPoint[indexS], lstPoint[indexE]); if (result.Distance > dis2) { result.Distance = dis2; result.Point0 = lstPoint[indexS]; result.Point1 = lstPoint[indexS + 1]; } if (result.Distance > dis3) { result.Distance = dis3; result.Point0 = lstPoint[indexS + 1]; result.Point1 = lstPoint[indexE]; } return result; } ShortestDisPointResult resultRe = null; int indexM = (indexE + indexS) / 2; var result1 = Binarysearch(lstPoint, indexS, indexM); var result2 = Binarysearch(lstPoint, indexM, indexE); if (result1.Distance < result2.Distance) resultRe = result1; else resultRe = result2; // 判断两区域之间X坐标在[indexM].X - dis到[indexM].X + dis内是否存在距离比dis小的两个点 // 找出X坐标在[indexM].X - dis到[indexM].X + dis内的点 var lstPtTemp = new List<HPoint2d>(); for(int index = indexS; index <= indexE; index++) { if (Math.Abs(lstPoint[index].X - lstPoint[indexM].X) < resultRe.Distance) lstPtTemp.Add(lstPoint[index]); } // 将点集按Y坐标排序 QuikSort(lstPtTemp, 0, lstPtTemp.Count - 1, CompareY); // 对于点集中的任一点，其它点若在该点的[Y - dis, Y + dis]内即判断与该点距离 for (int i = 0; i < lstPtTemp.Count - 1; i++) { for (int j = i + 1; j < lstPtTemp.Count; j++) { if (lstPtTemp[j].Y - lstPtTemp[i].Y < resultRe.Distance) { var disTemp = lstPtTemp[i].Distance(lstPtTemp[j]); if (resultRe.Distance > disTemp) { resultRe.Distance = disTemp; resultRe.Point0 = lstPtTemp[i]; resultRe.Point1 = lstPtTemp[j]; } } else break; } } return resultRe; } private bool CompareX(HPoint2d pointL, HPoint2d pointR) { if (pointL.X <= pointR.X) return true; return false; } private bool CompareY(HPoint2d pointL, HPoint2d pointR) { if (pointL.Y <= pointR.Y) return true; return false; } public void QuikSort(List<HPoint2d> lstPoint, int indexS, int indexE, CompareDelegate compare) { if (indexE <= indexS) return; int indexP = Partition(lstPoint, indexS, indexE, compare); QuikSort(lstPoint, indexS, indexP - 1, compare); QuikSort(lstPoint, indexP + 1, indexE, compare); } public int Partition(List<HPoint2d> lstPoint, int indexS, int indexE, CompareDelegate compare) { HPoint2d ptBase = lstPoint[indexE]; int i = indexS - 1; for(int j = indexS; j < indexE; j++) { if(compare(lstPoint[j], ptBase)) { i++; var ptTemp = lstPoint[i]; lstPoint[i] = lstPoint[j]; lstPoint[j] = ptTemp; } } var ptTemp2 = lstPoint[i + 1]; lstPoint[i + 1] = lstPoint[indexE]; lstPoint[indexE] = ptTemp2; return i + 1; } }