接下來我將用三種不同的方法求解“平面最近點(diǎn)對”問題。
問題描述：在一個(gè)平面上隨機(jī)分布著 n 個(gè)點(diǎn)，現(xiàn)給定 n 個(gè)點(diǎn)的坐標(biāo)，要求給出最近的兩個(gè)點(diǎn)之間的距離。
方法一：原始方法
題目要求求出最近的兩點(diǎn)之間的距離，先整理一下已知的線索：首先點(diǎn)的總個(gè)數(shù)為 n ；其次已知 n 個(gè)點(diǎn)的坐標(biāo)。掌握了每個(gè)點(diǎn)的坐標(biāo)，就相當(dāng)于間接地掌握了任意兩點(diǎn)之間的距離。假設(shè)兩個(gè)點(diǎn)為 A : ( x1 , y1 ) , B : ( x2 , y2 ) ,兩點(diǎn)間的距離為 distance ，根據(jù)平面坐標(biāo)系中的兩點(diǎn)間距離公式可得：
distance ^ 2 ＝ ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2，
運(yùn)用該公式對每兩個(gè)點(diǎn)的距離進(jìn)行計(jì)算，并不斷更新最小值 min_distance 。
這個(gè)方法很直觀也最容易想到，不過，由以上的兩層循環(huán)可知，該方法的時(shí)間復(fù)雜度為 o （ n ^ 2 ) ，當(dāng) n 的值不斷增大時(shí)，這個(gè)方法處理起來就顯得力不從心了。因此我們必須尋找另一種更有效的方法，或者在此方法上進(jìn)行適當(dāng)?shù)母倪M(jìn)。
接下來一起了解一下第二種方法－－分治法
方法二：分治法
為了做到有理有據(jù)，正式敘述解法之前，我得再啰嗦幾句選擇分治法的原因，希望不會引起大家的反感。在本問題中，需要求得最近兩點(diǎn)之間的距離，整個(gè)問題的規(guī)模為 n 個(gè)點(diǎn)，不妨將這 n 個(gè)點(diǎn)一分為二，就變成兩個(gè)求解 n ／2 個(gè)點(diǎn)規(guī)模下最近點(diǎn)對的距離問題， 如此不斷縮小規(guī)模，當(dāng)變成兩個(gè)點(diǎn)的規(guī)模下求解最近點(diǎn)對問題時(shí)，顯而易見，即為這兩個(gè)點(diǎn)的距離，這樣隨著問題規(guī)模的縮小解決的難易程度逐漸降低的特征正是可以用分治法解答的問題所具備的特征。
接下來，我們按照分治法解題步驟 分割－－求解－－合并 分析這個(gè)問題。將n 個(gè)點(diǎn)分為兩部分后，最近的兩個(gè)點(diǎn)有可能出現(xiàn)在第一部分中，也有可能出現(xiàn)在第二部分中，當(dāng)然還有可能一個(gè)在第一部分中，另一個(gè)在第二部分中，于是我們可以分別求出三種情況下最近點(diǎn)對的距離 dis1 dis2 dis3 ，從這三者中選擇出最小的一個(gè)作為本規(guī)模下的解。
分割：將 n 個(gè)點(diǎn)分為兩部分，每部分包含 n ／2 個(gè)點(diǎn)，
求解：分別對兩部分按照同樣的方法求得最近距離 dis1 和dis2 ，
合并：求解兩點(diǎn)分別分布在兩個(gè)部分的情況下的最近距離 dis3 ，取 dis1 dis2
dis3 三者中的最小者。
思路如上，我們再對具體的細(xì)節(jié)進(jìn)行完善
如何求子規(guī)模下的最近距離？
我們可以使用遞歸調(diào)用的方法來實(shí)現(xiàn)子規(guī)模的求解，遞歸有終止條件，這個(gè)問題的遞歸終止條件應(yīng)該是當(dāng)規(guī)模為 2 時(shí)，最近點(diǎn)對的距離即為這兩點(diǎn)的距離。
如何求合并后兩點(diǎn)分屬兩個(gè)部分時(shí)的最近距離？
由于兩點(diǎn)分屬兩個(gè)部分這種情況下，找尋任意一個(gè)點(diǎn)的范圍都太過寬泛，因此我們需要使用技巧來縮小尋找范圍。
這時(shí)候我們假設(shè)從兩部分分別求出的最近距離為 dis1 和 dis2 ，
dis ＝ min（ dis1， dis2 ），再假設(shè)分屬兩部分的情況下，A ( x1 , y1 ) 屬于第一部分 ,B ( x2 , y2 )屬于第二部分，且以 x 軸作為分割的量，我們可以斷定 如果存在解 ，A 、B 兩點(diǎn)一定處在中心分割線兩側(cè) 2＊dis 長度之內(nèi)的區(qū)間內(nèi)，（考慮到極端情況下有一點(diǎn)處在分割線上的情況，因此不能選擇 dis 長度區(qū)間），示意如下圖：
中心分割線為 x ＝ mid ，ans ＝ dis ，那么，A 點(diǎn)一定存在于 x ＝ mid － ans 和 x ＝ mid 這兩條直線之間的區(qū)域，同時(shí)， B 點(diǎn)一定存在于 x ＝ mid 和 x ＝ mid ＋ ans 這兩條直線之間的區(qū)域。
這時(shí)候，只要在中軸線左右兩側(cè)分別不超過 dis 的距離范圍內(nèi)進(jìn)行求解即可。
我們可以逐個(gè)枚舉x = mid-dis 與 x=mid+dis 兩條線之間所有點(diǎn)的兩兩距離。在處理之前我們可以做一些準(zhǔn)備工作進(jìn)一步優(yōu)化求解過程。首先將所有點(diǎn)按照 y 坐標(biāo)值升序進(jìn)行排序，這樣做有一個(gè)好處：當(dāng)某一點(diǎn) A的縱坐標(biāo) y1 與 某一點(diǎn) B 的縱坐標(biāo) y2 滿足 y2 － y1 > dis 時(shí)，可以直接斷定當(dāng)前的 A點(diǎn)與 縱坐標(biāo)大于 y2 的任意一個(gè)點(diǎn)的距離都會超過 dis ，也就不用判斷其余的點(diǎn)，省去了不少時(shí)間。
思路已經(jīng)描述完畢，接下來為大家奉上本方法的核心代碼。
下面給大家分享第三種方法。
方法三：分治法改進(jìn)版
在完整介紹這種方法之前，我們先來了解一個(gè)知識
如上圖所示，上圖中有一個(gè)邊長為 L *2L 的矩形，將該矩形等分成六個(gè) 1/2 L ＊2/3 L 的小矩形。假設(shè)在該區(qū)域內(nèi)散布著若干個(gè)點(diǎn)，并且任意兩點(diǎn)之間的距離不小于 L ，請?jiān)囍_定一下最多可以分布幾個(gè)點(diǎn)？
答案是 最多可以分布六個(gè)點(diǎn)，每個(gè)小矩形內(nèi)最多可以分布一個(gè)點(diǎn)。
我們用反證法來證明一下這個(gè)結(jié)論：
假設(shè) 分布的點(diǎn)數(shù)多于六個(gè)
由假設(shè)可知，
必然存在一個(gè)甚至多個(gè)矩形內(nèi)有多于一個(gè)點(diǎn)；
同時(shí)，處在同一塊矩形區(qū)域內(nèi)的兩個(gè)點(diǎn)的最大距離 ma x_dis 不會超過對角線的長度。在 1/2 L ＊ 2/3L 的矩形中，對角線長度為
sqrt（ ( 1/2 L)^2 + ( 2/3 L )^2 ）= 5/6 L , max_dis <= 5/6 L < L ，即最大距離不超過 L ，這與題目的要求相違背，因此，點(diǎn)數(shù)不會超過 6 。
再看下面這張圖片：
已知：
中心軸線將一塊區(qū)域分成 1 區(qū) 和 2 區(qū) 兩個(gè)區(qū)間長度均為 L 的區(qū)域；
1 區(qū) 和 2 區(qū)中散布著若干個(gè)點(diǎn)，并且在 1 區(qū)內(nèi)部任意兩點(diǎn)之間的距離大于 L ，2 區(qū)也是如此；
我們稱 1 區(qū)內(nèi)的點(diǎn)為 A ， 2 區(qū)中的點(diǎn)為 B ，A 、B 兩點(diǎn)的極限位置可以在中心軸線 x ＝ mid 上，如上圖；
我們需要求滿足以上條件的 A、B 兩點(diǎn)的最近距離是否存在小于 L 的情況。
由以上條件，我們可以推測 當(dāng) A ( x1 , y1 ) 點(diǎn)的位置確定的時(shí)候，B ( x2 , y2 ) 點(diǎn)可能位置也必然確定，
即 y2 >= y1 - L 且 y2 <= y1 + L ， x2 >= mid 且 x2 <= mid + L ,
換言之，在上圖中，只要 1 區(qū) 的點(diǎn)處在 A 點(diǎn)所在的水平線上，那么 2 區(qū) 中點(diǎn)的可能位置一定在圖中的矩形區(qū)域中，因此，對于 1 區(qū)中的每個(gè)點(diǎn)，在 2 區(qū)中最多需要判斷 6 個(gè)點(diǎn)就可以下結(jié)論。
有了上面的知識鋪墊，那我們可以利用以上知識進(jìn)一步優(yōu)化分治法求最近點(diǎn)對距離的方法，可以預(yù)見對第二種方法改進(jìn)的地方發(fā)生在合并兩個(gè)子集合時(shí)對兩點(diǎn)不屬于同一個(gè)子集合的處理上，現(xiàn)在的任務(wù)就是對于 1 區(qū)的任意一個(gè)點(diǎn)，求出對應(yīng) 2 區(qū)范圍內(nèi)需要判斷的數(shù)目不超過六個(gè)的點(diǎn)都有哪些。我們可以在找這六個(gè)點(diǎn)的時(shí)候先用橫坐標(biāo)限制范圍，再用縱坐標(biāo)限制范圍。每求一個(gè)點(diǎn)，都確定一次 2 區(qū)亂序的點(diǎn)哪些在范圍內(nèi)和遍歷所有點(diǎn)實(shí)現(xiàn)上是一樣麻煩的，我們需要有突破。這時(shí)候如果能將 2 區(qū)所有的點(diǎn)按照縱坐標(biāo)進(jìn)行排序，那么我們只要求得上、下界就可以了。為了省事，一般只求得上、下界之一，并連續(xù)的判斷6個(gè)點(diǎn)即可。
具體的實(shí)現(xiàn)思路是，建立兩個(gè)點(diǎn)集，集合一按照橫坐標(biāo) x 的升序進(jìn)行排列，集合二按照 y 的升序進(jìn)行排列，同一規(guī)模下利用集合一求出 1 區(qū) 和 2 區(qū)的區(qū)間長度 L ，再利用 L 將集合二中處在 1 區(qū) 和 2 區(qū)范圍內(nèi)的點(diǎn)按照之前在集合二中的順序挑選出來。接著逐個(gè)枚舉 1 區(qū)中的點(diǎn)，確定該點(diǎn)對應(yīng)在 2 區(qū)中需要判斷的六個(gè)點(diǎn)并給予精準(zhǔn)的判斷。
下面我將此方法的核心代碼向大家展示，文字沒有解釋清楚的地方，希望代碼部分能夠補(bǔ)足。
struct point
{
int x;//橫坐標(biāo)
int y;//縱坐標(biāo)
}p[1000];
vector<point> part_x,//按照 x 升序點(diǎn)集
part_y;//按照 y 升序點(diǎn)集
int compare_x( point a ,point b )//根據(jù)點(diǎn)的橫坐標(biāo)比大小
{
return a.x < b.x;
}
int compare_y(point a , point b )//根據(jù)點(diǎn)的縱坐標(biāo)比大小
{
return a.y < b.y;
}
double calculate_dis(point a,point b)//計(jì)算兩點(diǎn)間距離
{
return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 );
}
double min(double a ,double b)//求兩個(gè)數(shù)中的較小者
{
return a<b?a:b;
}
int max(int a,int b)//求兩個(gè)數(shù)中的較大者
{
return a>b?a:b;
}
//中心軸線為 mid_x，當(dāng)前最小點(diǎn)對距離為 dis ，求兩個(gè)按照 y 升序的點(diǎn)集合并處的最小點(diǎn)對距離，并更新 dis 值
//返回值為更新后的 dis 值。
//參數(shù) left_part_y 為 按照 y 升序的左半點(diǎn)集
//參數(shù) right_part_y 為 按照 y 升序的右半點(diǎn)集
double merge(vector<point>& left_part_y, vector<point> right_part_y , double dis,int mid_x)
{
vector<point> p1,//按照 y 升序存儲 1 區(qū)的點(diǎn)
p2;//按照 y 升序存儲 2 區(qū)的點(diǎn)
for(int i = 0 ; i < left_part_y.size() ; i ++)
{
if(left_part_y[i].x>=mid_x - dis)//將左半點(diǎn)集中處在 1 區(qū)的點(diǎn)存入p1
{
p1.push_back(left_part_y[i]);
}
}
for(int i = 0 ; i < right_part_y[i].size() ; i ++)
{
if(right_part_y[i].x <= mid_x + dis)//將右半點(diǎn)集中處在 2 區(qū)的點(diǎn)存入p2
{
p2.push_back(right_part_y[i]);
}
}
for(int i = 0 ; i < p1.size();i++)//對 1 區(qū)中的點(diǎn)逐個(gè)枚舉
{
int j = 0;
while(p2[j].y<p1[i].y && j<p2.size()) j++;//找到 2 區(qū)中與 1 區(qū)當(dāng)前枚舉點(diǎn)縱坐標(biāo)差的絕對值最小的點(diǎn)的索引
int begin,end;
begin = max(0,j-3);
if(j+3<p2.size()-1)
{
end = j+3;
}
else end = p2.size()-1;//實(shí)際上此處最多枚舉了七個(gè)點(diǎn)
for( int k = begin;k<= end; k++)
{
dis = min(dis,calculate_dis(p1[i],p2[k]));
}
}
return dis;
}
//給定按照 x 升序的點(diǎn)集 part_x 和按照 y 升序的同一點(diǎn)集 part_y, 排序是為了合并處理時(shí)方便
//返回該點(diǎn)集中最近點(diǎn)對的距離
int min_distance(vector<point>& part_x , vector<point>& part_y )
{
vector<point> left_part_x,//存儲 按照 x 升序的 part_x 點(diǎn)集的左半部分
right_part_x,//存儲按照 x 升序的 part_x 點(diǎn)集的右半部分
left_part_y,//存儲按照 y 升序的 part_y 點(diǎn)集的左半部分
right_part_y;//存儲按照 y 升序的 part_y 點(diǎn)集的右半部分
int mid = part_x.size()/2;
for( int i = 0 ; i < part_x.size() ; i ++)
{
if(i <= mid )//將 part_x 點(diǎn)集左半部分存入left_part_x
{
left_part_x.push_back( part_x[i] );
}
else//將 part_x 點(diǎn)集右半部分存入right_part_x
{
right_part_x.push_back( part_x[i]);
}
if(part_y[i].x<=part_x[mid].x)//將 part_y 點(diǎn)集中屬于 left_part_x 中的點(diǎn)存入 left_part_y
{
left_part_y.push_back( part_y[i]);
}
else//將 part_y 點(diǎn)集中屬于right_part_x 的點(diǎn)存入 right_part_y
{
right_part_y.push_back( part_y[i]);
}
}
if(part_x.size() == 2 )//處理 part_x 中只有兩個(gè)點(diǎn)的情況
{
return distance = calculate_dis(part_x[0],calculate_dis[1]);
}
//處理多余兩個(gè)點(diǎn)的情況
double dis1 ,dis2,dis3,dis;
dis1 = min_distance(left_part_x ,left_part_y);//將左半?yún)^(qū)間點(diǎn)集遞歸處理
dis2 = min_distance(right_part_x,right_part_y);//將右半?yún)^(qū)間點(diǎn)集遞歸處理
dis = min(dis1,dis2);
dis = merge(left_part_y,right_part_y,dis,part_x[mid].x);//求合并處的最近點(diǎn)對距離并更新 dis 值
return dis;
}
```3