副标题#e#
给定n个点（xi，yi）（1≤i≤n），要求找出个中间隔最近的两个点。
例14-7 假设在一片金属上钻n个巨细一样的洞，假如洞太近，金属大概会断。若知道任意两个洞的最小间隔，可预计金属断裂的概率。这种最小间隔问题实际上也就是间隔最近的点对问题。
通过查抄所有的n(n- 1 ) / 2对点，并计较每一对点的间隔，可以找出间隔最近的一对点。这种要领所需要的时间为(n2 )。我们称这种要领为直接要领。图1 4 – 1 3中给出了分而治之求解算法的伪代码。该算法对付小的问题回收直接要领求解，而对付大的问题则首先把它分别为两个较小的问题，个中一个问题（称为A）的巨细为「n /2ù，另一个问题（称为B）的巨细为「n /2ù。初始时，最近的点对大概属于如下三种景象之一： 1) 两点都在A中（即最近的点对落在A中）；2) 两点都在B中；3) 一点在A，一点在B。假定按照这三种环境来确定最近点对，则最近点对是所有三种环境中间隔最小的一对点。在第一种环境下可对A举办递归求解，而在第二种环境下可对B举办递归求解。
if (n较小) {用直接法寻找最近点对
R e t u r n ; }
// n较大
将点集分成大抵相等的两个部门A和B
确定A和B中的最近点对
确定一点在A中、另一点在B中的最近点对
从上面获得的三对点中，找出间隔最小的一对点
图14-13 寻找最近的点对
为了确定第三种环境下的最近点对，需要回收一种差异的要领。这种要领取决于点集是如何被分别成A、B的。一个公道的分别要领是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分派，以便满意A、B的巨细。
例2-8 考查图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1，垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A，右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上，可将个中两个插手A, 另一个插手B，以便A、B中包括沟通的点数。假设d ,m插手A，g插手B。
设是i的最近点对和B的最近点对中间隔较小的一对点。若第三种环境下的最近点比拟小。则每一个点距垂线的间隔必小于，这样，就可以裁减那些距垂线间隔≥的点。图1 4 – 1 5中的虚线是支解线。阴影部门以支解线为中线，宽为2 。界线线及其以外的点均被裁减掉，只有阴影中的点被保存下来，以便确定是否存在第三类点对（对应于第三种环境）其间隔小于。用RA、RB 别离暗示A和B中剩下的点。假如存在点对(p,q)，p?A, q?B且p, q的间隔小于，则p?RA，q?RB。可以通过每次查抄RA 中一个点来寻找这样的点对。假设考查RA 中的p 点，p的y 坐标为p.y，那么只需查抄RB 中满意p.y- ＜q.y＜p.y+的q 点，看是否存在与p 间距小于的点。在图14-16a 中给出了包括这种q 点的RB的范畴。因此，只需将RB 中位于×2 阴影内的点逐个与p 配对，以判定p 是否是间隔小于的第三类点。这个×2 区域被称为是p的较量区（comparing region）。
例2-9 考查例2 – 8中的1 4个点。A中的最近点对为(b,h)，其间隔约为0 . 3 1 6。B中最近点对为(f, j)，其间隔为0 . 3，因此= 0 . 3。当考查是否存在第三类点时，除d, g, i, l, m 以外的点均被裁减，因为它们距支解线x= 1的间隔≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m的较量区中没有点，只需考查i即可。i的较量区中仅含点l。计较i 和l的间隔，发明它小于，因此(i, l) 是最近的点对。
为了确定一个间隔更小的第三类点，RA 中的每个点最多只需和RB 中的6个点较量，如图1 4 – 1 6所示。
#p#副标题#e#
1. 选择数据布局
为了实现图1 4 – 1 3的分而治之算法，需要确定什么是“小问题”以及如何暗示点。由于荟萃中少于两点时不存在最近点对，因此必需担保解析进程不会发生少于两点的点集。假如将少于四点的点集做为“小问题”，就可以制止发生少于两点的点集。
每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见措施1 4 – 8）来暗示。为了便于按x 坐标对各个点排序，可重载操纵符＜=。合并排序措施如1 4 -3所示。
措施14-8 点类
class Point1 {
friend float dist(const Point1&, const Point1&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&,float&);
friend void main();
p u b l i c :
int operator<=(Point1 a) const
{return (x <= a.x);}
p r i v a t e :
int ID; // 点的编号
float x, y; // 点坐标
} ;
class Point2 {
friend float dist(const Point2&, const Point2&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&, float&);
friend void main();
p u b l i c :
int operator<=(Point2 a) const
{return (y <= a.y);}
p r i v a t e :
int p; // 数组X中沟通点的索引
float x, y; // 点坐标
} ;
#p#分页标题#e#
所输入的n个点可以用数组X来暗示。假设X中的点已凭据x 坐标排序，在支解进程中假如当前考查的点是X [l :r]，那么首先计较m= (l+r) / 2，X[ l:m]中的点属于A，剩下的点属于B。计较出A和B中的最近点对之后，还需要计较RA 和RB，然后确定是否存在更近的点对，个中一点属于RA，另一点属于RB。假如点已按y 坐标排序，那么可以用一种很简朴的方法来测试图1 4 – 1 6。按y 坐标排序的点生存在另一个利用类P o i n t 2 (见措施14-8)的数组中。留意到在P o i n t 2类中，为了便于y 坐标排序，已重载了操纵符＜＝。成员p 用于指向X中的对应点。
确定了须要的数据布局之后，再来看看所要发生的代码。首先界说一个模板函数d i s t (见措施1 4 – 9 )来计较点a, b 之间的间隔。T大概是P o i n t 1或P o i n t 2，因此d i s t必需是P o i n t 1和P o i n t 2类的友元。
措施14-9 计较两点间隔
template
inline float dist(const T& u, const T& v)
{ / /计较点u 和v之间的间隔
float dx = u.x-v. x ;
float dy = u.y-v. y ;
return sqrt(dx * dx + dy * dy);
}
假如点的数目少于两个，则函数c l o s e s t (见措施1 4 – 1 0 )返回f a l s e，假如乐成时函数返回t r u e。当函数乐成时，在参数a 和b 中返回间隔最近的两个点，在参数d 中返回间隔。代码首先验证至少存在两点，然后利用M e rg e S o r t函数(见措施14-3) 按x 坐标对X中的点排序。接下来把这些点复制到数组Y中并按y 坐标举办排序。排序完成时，对任一个i，有Y [i ] . y≤Y [i+ 1 ] . y，而且Y [i ] .p给出了点i 在X中的位置。上述筹备事情做完今后，挪用函数close (见措施1 4 – 11 )，该函数实际求解最近点对。
措施14-10 预处理惩罚及挪用c l o s e
bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)
{// 在n >= 2个点中寻找最近点对
// 假如少于2个点，则返回f a l s e
// 不然，在a 和b中返回间隔最近的两个点
if (n < 2) return false;
// 按x坐标排序
M e r g e S o r t ( X , n ) ;
// 建设一个按y坐标排序的点数组
Point2 *Y = new Point2 [n];
for (int i = 0; i < n; i++) {
// 将点i 从X 复制到Y
Y[i].p = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
M e r g e S o r t ( Y,n); // 按y坐标排序
// 建设姑且数组
Point2 *Z = new Point2 [n];
// 寻找最近点对
c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
// 删除数组并返回
delete [] Y;
delete [] Z;
return true;
}
措施1 4 – 11 计较最近点对
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)
{//X[l:r] 按x坐标排序
//Y[l:r] 按y坐标排序
if (r-l == 1) {// 两个点
a = X[l];
b = X[r];
d = dist(X[l], X[r]);
r e t u r n ; }
if (r-l == 2) {// 三个点
// 计较所有点对之间的间隔
float d1 = dist(X[l], X[l+1]);
float d2 = dist(X[l+1], X[r]);
float d3 = dist(X[l], X[r]);
// 寻找最近点对
if (d1 <= d2 && d1 <= d3) {
a = X[l];
b = X[l+1];
d = d1;
r e t u r n ; }
if (d2 <= d3) {a = X[l+1];
b = X[r];
d = d2;}
else {a = X[l];
b = X[r];
d = d3;}
r e t u r n ; }
/ /多于三个点，分别为两部门
int m = (l+r)/2; // X[l:m] 在A中，余下的在B中
// 在Z[l:m] 和Z [ m + 1 : r ]中建设按y排序的表
int f = l, // Z[l:m]的游标
g = m+1; // Z[m+1:r]的游标
for (int i = l; i <= r; i++)
if (Y[i].p > m) Z[g++] = Y[i];
else Z[f++] = Y[i];
// 对以上两个部门举办求解
c l o s e ( X , Z , Y, l , m , a , b , d ) ;
float dr;
Point1 ar, br;
c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;
// (a,b) 是两者中较近的点对
if (dr < d) {a = ar;
b = br;
d = dr;}
M e r g e ( Z , Y,l,m,r);// 重构Y
/ /间隔小于d的点放入Z
int k = l; // Z的游标
for (i = l; i <= r; i++)
if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i];
// 通过查抄Z [ l : k - 1 ]中的所有点对，寻找较近的点对
for (i = l; i < k; i++){
for (int j = i+1; j < k && Z[j].y - Z[i].y < d;
j + + ) {
float dp = dist(Z[i], Z[j]);
if (dp < d) {// 较近的点对
d = dp;
a = X[Z[i].p];
b = X[Z[j].p];}
}
}
}
#p#分页标题#e#
函数c l o s e（见措施1 4 – 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间功效。找到最近点对今后，将在a, b中返回最近点对，在d 中返回间隔，数组Y被规复为输入状态。函数并未修改数组X。
首先考查“小问题”，即少于四个点的点集。因为支解进程不会发生少于两点的数组，因此只需要处理惩罚两点和三点的景象。对付这两种景象，可以实验所有的大概性。当点数高出三个时，通过计较m = ( 1 + r ) / 2把点集分为两组A和B，X [ 1 : m ]属于A，X [ m + 1 : r ]属于B。通过从左至右扫描Y中的点以及确定哪些点属于A，哪些点属于B，可以建设别离与A组和B组对应的，按y 坐标排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此时Y和Z的脚色相互互换，依次执行两个递归挪用来获取A和B中的最近点对。在两次递归挪用返回后，必需担保Z不产生改变，但对Y则无此要求。不外，仅Y [ l : r ]大概会产生改变。通过归并操纵（见措施1 4 – 5）可以以Z [ 1 : r ]重构Y [ 1 : r ]。
为实现图1 4 – 1 6的计策，首先扫描Y [ 1 : r ]，并收集距支解线小于的点，将这些点存放在Z [ 1 : k – 1 ]中。可按如下两种方法来把RA中点p 与p的较量区内的所有点举办配对：1) 与RB 中y 坐标≥p.y的点配对；2) 与y 坐标≤p.y的点配对。这可以通过将每个点Z [ i ]（1≤i < k，不管该点是在RA
照旧在RB中）与Z[j] 配对来实现，个中i＜j 且Z [ j ] . y – Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所查抄的点如图1 4 – 1 7所示。由于在每个2 ×子区域内的点至少相距。因此每一个子区域中的点数不会高出四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。
2. 巨大性阐明
令t (n) 代表处理惩罚n个点时，函数close 所需要的时间。当n＜4时，t (n) 便是某个常数d。当n≥4时，需耗费(n) 时间来完成以下事情：将点集分别为两个部门，两次递归挪用后重构Y，裁减距支解线很远的点，寻找更好的第三类点对。两次递归挪用需别离耗时t (「n /2ù」和t (?n /2?).
这个递归式与合并排序的递归式完全一样，其功效为t (n) = (nl o gn)。别的，函数c l o s e s t还需耗时(nl o gn)来完成如下特别事情：对X举办排序，建设Y和Z，对Y举办排序。因此分而治之最近点对求解算法的时间巨大性为(nl o gn)。
