距离最近的点对

韩冰

<>给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。

- L7 {2 e% Z1 x- A5 t例14-7 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。

; w3 L; v) z) u: ?4 A% s通过检查所有的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进行递归求解。
7 J( `  U- W* x2 s/ o* c* {& L* G
$ j7 ]) o1 N) o8 D  Z( g5 h& J  e
3 C& U* B4 T' H' Kif (n较小) {用直接法寻找最近点对
: f6 e  R5 @. Y" S/ r6 ?
7 {8 Z& J: g! ]R e t u r n ; }
! Y' a0 V  P/ R  l& d7 G
// n较大

将点集分成大致相等的两个部分A和B
0 n, ^) u, n7 G
6 h* D6 t: t! h0 p9 W; P1 p确定A和B中的最近点对
3 ~8 u% t- Y! t3 V0 R
确定一点在A中、另一点在B中的最近点对

8 t  X. M' m, L2 y, v8 ]; n1 H) m从上面得到的三对点中，找出距离最小的一对点
) H2 S7 [0 Q; g) d  G# }
图14-13 寻找最近的点对

! y6 b+ }1 B, S6 D0 b0 t
为了确定第三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成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）。
# c. T* q6 ?& h5 o
例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) 是最近的点对。
4 V; R' k# g7 e; ~
为了确定一个距离更小的第三类点，RA 中的每个点最多只需和RB 中的6个点比较，如图1 4 - 1 6所示。

1. 选择数据结构
4 Q4 b3 ~. J7 m# j; |
% s% V0 Z$ e9 m% a3 s$ |. |* i为了实现图1 4 - 1 3的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。

每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见程序1 4 - 8）来表示。为了便于按x 坐标对各个点排序，可重载操作符＜=。归并排序程序如1 4 -3所示。

程序14-8 点类
/ o, `$ S/ y! a" p5 W/ L0 ]
class Point1 {

friend float dist(const Point1&amp;, const Point1&amp;);
) o2 k3 d7 \4 t" P
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);
  h+ b. z) L9 s/ V5 E
friend bool closest(Point1 *, int, Point1&amp;, Point1&amp;,float&amp;);

& t% ^6 [* u  o( Tfriend void main();
0 a- X0 Q/ o& R( A1 V
p u b l i c :
1 V, W% Q$ ]. Q9 Y( m3 X/ ]
int operator&lt;=(Point1 a) const
. p4 v& |& f9 H! T8 B
{return (x &lt;= a.x);}
$ y; D- i+ l, O( ~4 m
p r i v a t e :

6 E( {* S" Y3 R8 \int ID; // 点的编号
+ O! c5 `2 _4 ~, b! b
float x, y; // 点坐标
/ l) X# M& O3 `. k, u/ ~
} ;
+ _% W  Q8 @0 J" z5 t: N
class Point2 {

friend float dist(const Point2&amp;, const Point2&amp;);

! o( X1 Q9 S# P' N7 e2 q. Kfriend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);
3 w8 I; K8 Z: i- ?5 P
friend bool closest(Point1 *, int, Point1&amp;, Point1&amp;, float&amp;);

friend void main();

p u b l i c :
- ^* k/ _; L1 |' X. f
int operator&lt;=(Point2 a) const
9 w7 t) t0 T4 z1 U, H7 I- Y5 Z
{return (y &lt;= a.y);}
% w( V6 v, U4 U! i
9 u2 E# J& p/ ~* v$ l( ?! Up r i v a t e :

int p; // 数组X中相同点的索引
7 D; i. U( B3 N
float x, y; // 点坐标

. ~2 U- k  W8 {, F1 i} ;

- @: u6 }+ X1 \: s) t所输入的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中的对应点。
& g; @, T' z/ w1 w2 j- I; G
确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数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类的友元。

$ A2 e# ~6 k& w+ L3 |2 E+ f8 g3 B程序14-9 计算两点距离
6 v, u! e9 U7 X# d! k
template<CLASS T>

. l7 J8 r( g, tinline float dist(const T&amp; u, const T&amp; v)
, A1 m/ [! L3 I- V" v* y
{ / /计算点u 和v之间的距离
- r# G* {, ^6 S/ M9 O4 w3 N1 I  i
float dx = u.x-v. x ;

3 y# N6 j  z  z& xfloat dy = u.y-v. y ;
, X3 H. R- c! @/ v
return sqrt(dx * dx + dy * dy);
" J5 v* t7 W) N% ~4 x- O( P+ y
}

8 j" O3 p' ]; p6 R! y- E如果点的数目少于两个，则函数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 )，该函数实际求解最近点对。
" W" _# B% Q6 f# @6 ~: L* [. }
( e& E6 I; I1 r2 A+ E程序14-10 预处理及调用c l o s e

. d9 j. p' I0 u- k  L% @/ W! x+ Vbool closest(Point1 X[], int n, Point1&amp; a, Point1&amp; b, float&amp; d)
  S' @' _6 Z. L5 w0 E4 E; S7 h
{// 在n &gt;= 2 个点中寻找最近点对

// 如果少于2个点，则返回f a l s e

' F2 g' [! l2 g/ _( q// 否则，在a 和b中返回距离最近的两个点

if (n &lt; 2) return false;

// 按x坐标排序

  q% L. S( j% ]M e r g e S o r t ( X , n ) ;
4 y3 B& A0 E7 k5 y
- ?8 a9 o4 p, Y( H( H// 创建一个按y坐标排序的点数组

# E9 }+ C. X8 wPoint2 *Y = new Point2 [n];
4 u  r7 c+ S* \0 G
0 r! X" Z3 m! v. |for (int i = 0; i &lt; n; i++) {

1 s3 x' E+ B  e// 将点i 从X 复制到Y

Y.p = i;
) @8 M6 z' f* X6 }
" \, \% x+ g! P% [Y.x = X.x;
2 ~3 d" d; q$ P$ \& p
8 B. p. ^5 j1 {/ y: A8 w+ F- b; ZY.y = X.y;
* Q1 H2 e! K; U, ]& `8 c/ r. L
- d& m9 @- k- ~# ~: _' r}
) d# P$ Z  m% \
M e r g e S o r t ( Y,n); // 按y坐标排序
! Q) p8 t/ T. \( O3 o1 Q- w2 m
9 l! m' l* d; ^; {5 U+ j1 W( u& p// 创建临时数组

Point2 *Z = new Point2 [n];
# V1 y1 s* a4 I; }; p* p4 r
% O) v2 ^& l) U! m// 寻找最近点对

c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
7 p0 H( P4 ^' n7 m  g# U5 I
" R0 U. W" Y/ c+ s// 删除数组并返回
3 X) j+ z5 n; X4 {
delete [] Y;
  u( T9 n2 I3 g" d8 K+ `$ u
delete [] Z;

return true;

5 f, k  i) }/ w5 g}
4 U1 O7 a; n+ g* w
程序1 4 - 11 计算最近点对
0 |% r- W9 p; ^( e: ?  \5 W
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1&amp; a, Point1&amp; b, float&amp; d)
1 S) j; c7 l8 J  w  L4 b
{//X[l:r] 按x坐标排序
9 l* p1 C; Q. |% L) m8 ?
//Y[l:r] 按y坐标排序

if (r-l == 1) {// 两个点
8 J" h; R" a- J; j+ v( t8 I: L
a = X[l];
8 P/ f7 A8 D0 K. R
: k6 ]* Q; I* ub = X[r];
% K, p6 h. f  L. V0 ]
d = dist(X[l], X[r]);
3 [3 t% V! X1 c% P! `+ p) @
r e t u r n ; }

) j8 o5 [1 S( ^& `4 x9 k3 Jif (r-l == 2) {// 三个点
8 S( r" y) D" X. _; @) c3 q: E' u5 |* i
// 计算所有点对之间的距离

float d1 = dist(X[l], X[l+1]);
  g% l0 k% T5 E* ]
/ a8 S7 V8 o& `  i' D: V. }float d2 = dist(X[l+1], X[r]);
4 d( k- Z. V9 f. W
float d3 = dist(X[l], X[r]);
: s$ _/ X* p* l
  S, V4 [* j+ M9 X// 寻找最近点对
& k3 R5 K* u# N  u. o! s
0 l2 L1 f7 }# x/ f; @if (d1 &lt;= d2 &amp;&amp; d1 &lt;= d3) {
" X. O: H8 K, b" {- c9 g
a = X[l];

b = X[l+1];

d = d1;

& m* B  C# R2 [1 [8 Z! ~r e t u r n ; }
2 K* X' K: k( X) n/ H' W
* t, v/ M* h( w! Uif (d2 &lt;= d3) {a = X[l+1];

: R$ d, n% g4 h  k* f; }! z2 hb = X[r];

d = d2;}
' M9 G8 ~" k; R2 I5 z5 o% a
else {a = X[l];

b = X[r];

5 h8 H3 e* W6 A" b- Jd = 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排序的表
, A" K$ x- p9 }+ O8 I8 {+ I7 i0 m# e
0 p# ^+ v% f: `1 n& u" Z) Uint f = l, // Z[l:m]的游标

" Q" W- q) C: m' a$ Bg = m+1; // Z[m+1:r]的游标
6 m7 n& T6 t* G, B# \' l
' t% \, \3 E8 P3 T; P' Rfor (int i = l; i &lt;= r; i++)

: l5 V8 A( Q2 {2 f' K' oif (Y.p &gt; m) Z[g++] = Y;

else Z[f++] = Y;

0 p' z. Z5 c  B( ^/ R" h// 对以上两个部分进行求解

c l o s e ( X , Z , Y, l , m , a , b , d ) ;

float dr;
$ @  H8 e1 M7 W$ I- @- v
Point1 ar, br;

c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;
' z) E/ \* b! x( m& m! s. K
// (a,b) 是两者中较近的点对
5 ]7 G  D) x" @$ c+ o
if (dr &lt; d) {a = ar;

b = br;
. O: {5 B) v, L! t( y1 `$ C/ P. s0 a
d = dr;}

! k( H# K  j- ]0 p* ]* SM e r g e ( Z , Y,l,m,r);// 重构Y
4 h9 Z% p+ \& U3 J+ ~: w4 h
/ /距离小于d的点放入Z
0 H# D9 K/ g  Q) I: N# ^" s* m3 w
4 h) W  `& J. H  Q; z* w' l! kint k = l; // Z的游标

for (i = l; i &lt;= r; i++)
4 K" Y+ V8 M! q2 B4 a8 Y
if (fabs(Y[m].x - Y.x) &lt; d) Z[k++] = Y;

// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对
2 E! k! i' k& ^  l& ~+ y/ A$ `
: @5 r: d* ?% f. Gfor (i = l; i &lt; k; i++){

% v1 b7 S$ V6 \9 j. h  d# Pfor (int j = i+1; j &lt; k &amp;&amp; Z[j].y - Z.y &lt; d;
& Z& w) j3 d; @" L0 R/ h
2 s$ {# v& s. C1 Gj + + ) {
- E7 P) L  e0 k, B* c9 f
. P0 `3 A, Z8 l8 w; \8 qfloat dp = dist(Z, Z[j]);
* S8 t2 Q8 A2 h$ W% E2 T$ b
7 f2 e0 `  y0 G4 b1 m6 R/ H/ Tif (dp &lt; d) {// 较近的点对
8 G+ |" p0 c0 d  O
d = dp;
5 X6 k4 b* h0 P# W
* R* ~2 X/ M* @8 k/ k& e- i* P: g; u  Ja = X[Z.p];
/ }" N/ x. Q1 L0 T
1 h; X0 M+ [" N% C9 q3 J# Ib = X[Z[j].p];}
. [5 [0 r; G/ d& l
}

% l8 r0 U8 B/ i1 U8 s" M}

}
! F, U9 b1 X4 C
& u+ F6 K& |/ `9 M: c* a8 @函数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 ]。
3 K' x& l) \# {5 \6 N) g. `" n
; h% I4 x1 ^9 ?$ |7 I) B6 j* G为实现图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 &lt; k，不管该点是在RA

7 \1 h+ r" M, e8 [% E) |0 R" u还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。
' M4 v5 _' g9 R; v: B4 V- i
( F% u% V% Y& ?6 f* c9 F# ]6 G+ c$ j2. 复杂性分析
% k; E9 |# x1 P$ g0 w
令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?).

+ ]2 Q2 r5 v/ |% H. P这个递归式与归并排序的递归式完全一样，其结果为t (n) = (nl o gn)。另外，函数c l o s e s t还需耗时(nl o gn)来完成如下额外工作：对X进行排序，创建Y和Z，对Y进行排序。因此分而治之最近点对求解算法的时间复杂性为(nl o gn)。</P>