求點(diǎn)集中的最近點(diǎn)對(duì)有以下兩種方法:

設(shè)p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S，設(shè)計(jì)算法找出集合S中距離最近的點(diǎn)對(duì)。

1、蠻力法（適用于點(diǎn)的數(shù)目比較小的情況下）

1） 算法描述： 已知集合S中有n個(gè)點(diǎn)，一共可以組成n(n-1)/2對(duì)點(diǎn)對(duì)，蠻力法就是對(duì)這 n(n-1)/2 對(duì)點(diǎn)對(duì)逐對(duì)進(jìn)行距離計(jì)算， 通過循環(huán)求得點(diǎn)集中的最近點(diǎn)對(duì)：

2）代碼描述：

double MinDistance = double.maxvalue； //設(shè)置一個(gè)MinDistance存儲(chǔ)最近點(diǎn)對(duì)的距離，初始值為無窮大

int PointIndex1,PointIndex2； //設(shè)置PointIndex1,PointIndex2分別存儲(chǔ)最近點(diǎn)對(duì)的兩個(gè)點(diǎn)編號(hào)

for (i=1; i< n; i++) //循環(huán)計(jì)算 n(n-1)/2對(duì)點(diǎn)對(duì)的距離
{

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

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

if PointDistance < MinDistance; //如果當(dāng)前點(diǎn)對(duì)距離小于最小點(diǎn)對(duì)距離，則設(shè)置最小點(diǎn)對(duì)距離等于當(dāng)前點(diǎn)對(duì)距離

{

MinDistance = PointDistance;

PointIndex1 = i;

PointIndex2 = j;

}

}

}

}
3）算法時(shí)間復(fù)雜度：算法一共要執(zhí)行 n(n-1)/2次循環(huán)，因此算法復(fù)雜度為O(n ² )

2、分治法

1）算法描述： 已知集合S中有n個(gè)點(diǎn)，分治法的思想就是將S進(jìn)行拆分，分為2部分求最近點(diǎn)對(duì)。算法每次 選擇一條垂線L，將S拆分左右兩部分為SL和SR ，L一般取 點(diǎn)集S中所有點(diǎn)的中間點(diǎn)的x坐標(biāo)來劃分，這樣可以保證SL和SR中的點(diǎn)數(shù)目各為n/2 ，

（否則以其他方式劃分S，有 可能導(dǎo)致 S L 和S R 中點(diǎn)數(shù)目一個(gè)為1，一個(gè)為n-1，不利于算法效率，要盡量保持樹的平衡性）

依次找出這兩部分中的最小點(diǎn)對(duì)距離： δ L和 δ R，記 SL和SR 中最小點(diǎn)對(duì)距離 δ = min（ δ L， δ R），如圖1：

以L為中心， δ為半徑劃分一個(gè)長帶， 最小點(diǎn)對(duì)還有可能存在于 SL和SR的交界處 ， 如下圖2左圖中的虛線帶，p點(diǎn)和q點(diǎn)分別位于 SL和SR 的虛線范圍內(nèi)，在這個(gè)范圍內(nèi)，p點(diǎn)和q點(diǎn)之間的距離才會(huì)小于δ，最小點(diǎn)對(duì)計(jì)算才有意義。

Figure 2

對(duì)于 S L虛框范圍內(nèi)的p點(diǎn)，在 SR 虛框中與p點(diǎn)距離小于δ的頂多只有六個(gè)點(diǎn)，就是圖二右圖中的2個(gè)正方形的6的頂點(diǎn)。這個(gè)可以反推證明，如果右邊這2個(gè)正方形內(nèi)有7個(gè)點(diǎn)與p點(diǎn)距離小于 δ ，例如q點(diǎn)，則q點(diǎn)與下面正方形的四個(gè)頂點(diǎn)距離小于 δ ，則和 δ 為 S L 和 S R 中 的最小點(diǎn)對(duì)距離相矛盾。因此對(duì) 于S L虛框中的p點(diǎn) ，不需求出p點(diǎn)和右邊虛線框內(nèi)所有點(diǎn)距離，只需計(jì)算 S R中 與p點(diǎn)y坐標(biāo)距離最近的6個(gè)點(diǎn)，就可以求出最近點(diǎn)對(duì)，節(jié)省了比較次數(shù)。

（否則的話， 最壞情形下， 在 S R 虛框中有可能會(huì)有n/2個(gè)點(diǎn)，對(duì)于 S L 虛框中的p點(diǎn) ， 每次要比較 n/2 次，浪費(fèi)了算法的效率 ）

代碼描述：

1）對(duì)點(diǎn)集S的點(diǎn)x坐標(biāo)和y坐標(biāo)進(jìn)行升序排序，獲得點(diǎn)集Sx和Sy

2）令 δ =∞; // δ為最小點(diǎn)位距離

3）Divide_conquer（ Sx，Sy ， δ ） // 分治法

if （ Sx.count=1） then δ =∞; // 如果 Sx 中只有一個(gè)點(diǎn)，則 δ = ∞

return δ ;

else if （Sx.count=2 and d（ Sx.[0], Sx.[1]）< δ ） // 如果 Sx 中只有2個(gè)點(diǎn)，則 δ 為兩點(diǎn)之間距離

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

return δ ;

else // 如果 Sx 中多于2個(gè)點(diǎn)，則 將 Sx , Sy 分治，以中心點(diǎn)畫線，將 Sx 分為左右兩部分 SxL 和SxR，Sy 分為 SyL 和 S yR

j1=1, j2=1 , k1=1 , k2=1;

mid = Sx.count/2; // mid 為 Sx 中的中間點(diǎn)點(diǎn)號(hào)

L = Sx.[mid].x; // L 為 Sx 中的中間點(diǎn)x坐標(biāo)

for(i=1,i< Sx.count ,i++)

{

if(i<= mid ) //將 Sx 中間線以左地方的點(diǎn)存入到 SxL ，新數(shù)組保持原來的升序性質(zhì)

SxL[ k1 ] = Sx[i] k1++;

else //將 Sx 中間線以右的地方的點(diǎn)存入到 SxR ， 新 數(shù)組保持原來的升序性質(zhì)

SxR.count[k2] = Sx[i] k2++;

if( Sy [i]. x <L) //將 Sy 中間線以左地方的點(diǎn)存入到 SyL ， 新 數(shù)組保持原來的升序性質(zhì)

SyL[j1] = Sx[i] j1++;

else //將 Sy 中間線以右地方的點(diǎn)存入到 SyR ， 新 數(shù)組保持原來的升序性質(zhì)

SyR[j2] = Sx[i] j2++;

}

δL = Divide_conquer（SxL，SyL ， δ） ; //獲取 Sx 中的的最小點(diǎn)位距離 δL

δR = Divide_conquer（SxR，SyR ， δ） ; //獲取 Sy 中的的最小點(diǎn)位距離 δR

δ = min ( δL , δR );

δ = merge( SyL，SyR ， δ); //獲 Sx 中 Sy 交界處的最小點(diǎn)位距離，并綜合 δL 和 δR 求出點(diǎn)集的最小點(diǎn)位距離 δ

return δ ;

函數(shù)merge(SyL，SyR ， δ)

merge(SyL，SyR ， δ)

{

i1=1,i2=1;

for(i=1,i< SyL .count,i++) //獲取 SyL 中在左邊虛框(距離小于 δ) 內(nèi)的點(diǎn) ，存入到 S' yL 中 ， 新 數(shù)組保持原來的升序性質(zhì)

{

if( SyL [i].x>L- δ )

then S'yL[ i1 ]= SyL[i], i1++,

}

for(i=1,i<SyR.count,i++) //獲取 SyR 中在右邊虛框(距離小于 δ) 內(nèi)的點(diǎn) ，存入到 S' yR 中 ， 新 數(shù)組保持原來的升序性質(zhì)

{

if( SyR [i].x<L+ δ )

then S'yR[ i2 ]= SyR[i], i2++,

}

t=1;

for (i=1,i<S'yL.count,i++)

{

while(S'yR[t].y< S'yL[t].yand t < SyR.count) //獲取點(diǎn)集 S'yR 內(nèi)距離點(diǎn) S'yL[t] y坐標(biāo)最接近的點(diǎn)號(hào)

{ t++; }

for( j= max(1,t-3), j<=min(t+3,S'yR.count),j++) //計(jì)算S'yR中的點(diǎn)與S'yL[t]y坐標(biāo)相鄰的六個(gè)點(diǎn)的距離

{

if(d(S'yL[ i ],S'yL[j])< δ ) //如果 前兩點(diǎn)之間距離 小于 δ

then δ = d(S'yL[ i ],S'yL[j]); //則最小點(diǎn)位距離 δ 為當(dāng)前兩點(diǎn)之間距離

}

return δ

}

3）算法時(shí)間復(fù)雜度：

首先 對(duì)點(diǎn)集S的點(diǎn)x坐標(biāo)和y坐標(biāo)進(jìn)行升序排序 ，需要循環(huán)2nlogn次，復(fù)雜度為 O(2nlogn )

接下來在分治過程中，對(duì)于每個(gè)S'yL中的點(diǎn)，都需要與S'yR中的6個(gè)點(diǎn)進(jìn)行比較

O(n)= 2O(n/2) + (n/2)*6（一個(gè)點(diǎn)集劃分為左右兩個(gè)點(diǎn)集，時(shí)間復(fù)雜度為左右兩個(gè)點(diǎn)集加上中間區(qū)域運(yùn)算之和）

其解為O(n)< O(3nlogn )

因此總的時(shí)間復(fù)雜度為O(3nlogn ) ，比蠻力法的 O(n ² ) 要高效。

分治法基礎(chǔ)知識(shí)可參考http://blog.csdn.net/junerfsoft/archive/2008/09/25/2975495.aspx

改進(jìn)算法可參考“求平面點(diǎn)集最近點(diǎn)對(duì)的一個(gè)改進(jìn)算法”

平面最近點(diǎn)對(duì)