|
На кроці повернення із рекурсив |
||
|
них поділів отримані |
результати |
|
\ |
порівнюватимуться, і |
врешті-решт |
|
* Ps |
буде визначено найкращий. |
||
Однак в описаному алгоритмі є |
|||
|
|||
I |
один недолік: при поділі точок на |
||
дві підмножини залишилися поза |
|||
Мал. 167 |
увагою ті точки, що лежать у при |
||
кордонній зоні. Адже |
саме серед |
||
|
|||
них може знайтися найближча пара (мал. 167). За описаним алгоритмом пошук пари найближчих точок вівся окремо у лі вій та правій частинах, тобто для точок рх, р4, р6 і р2, р3, рь. Із прикладу, зображеного на малюнку 167, можна побачити, що в окремо взятих частинах найменшою є відстань між точками рг і р5. Однак, якщо розглядати всю множину заданих точок, то точки рх ір2 розташовані ще ближче одна від одної. Цієї помил ки можна уникнути, якщо додатково на кожному кроці після повернення із рекурсії, маючи поточне значення найменшої відстані між двома точками, дослідити точки, що потрапили у прикордонну зону поточного поділу. При цьому деякі точки, що мають однакове значення по осі абсцис, можуть знаходи тись і на самій прямій.
Розглянемо k-w. крок виконання рекурсивного алгоритму. Насамперед необхідно визначити, якої ширини має бути при кордонна досліджувана зона. Якщо на поточному кроці значен ня найменшої відстані між парою точок становить d, то нас ці кавитимуть тільки ті точки, відстань між якими менша.
Прикордонна зона може містити точки як зліва і справа від вертикальної прямої поділу, так і на самій прямій (мал. 168). Оскільки під час поділу множини точок на дві підмножини точ ки, що розміщені на самій прямій, можуть потрапити у різні під множини, то можливий випадок, коли точка рі буде відноситися до лівої частини, а точка р - до правої. Як видно з малюнка, на поточному кроці визначена пара найближчих точок і знаходить
ся вона у лівій частині, однак точкиpt |
T&PJ у прикордонній області |
|||
розміщені ще ближче і відстань між ними менша за d. |
||||
|
|
і |
|
|
-2d- |
і |
|
-d- |
|
|
|
|||
|
і |
|
|
о |
|
|
|
|
|
|
|
І |
|
|
|
|
ІІ |
|
|
• |
і |
ІІ |
|
|
І |
|
|
||
А |
*Р, |
|
-Тг- |
|
|
І |
|
||
|
Мал. 168 |
|
Мал. 169 |
|
292
Звідси можна зробити висновок, що ширина прикордонної області повинна дорівнювати d як справа, так і зліва від лінії поділу (мал. 169). Більшою її робити немає сенсу, оскільки ту ди попадуть точки, відстань між якими більша за d, а меншою неможливо, оскільки можна втратити точки, що дадуть кра щий результат.
Залишається тільки вирішити питання, яким чином пере глядати точки, що потрапили у прикордонну область. Якщо робити це повним переглядом усіх пар точок, то ефективність такого підходу не дуже висока.
Виявляється, цей процес можна звести до лінійного. Чи вар то переглядати всі можливі пари точок? Мабуть, ні: ті точки, відстань між якими більша за d, нас не цікавитимуть. А де мо жуть знаходитися точки, відстань між якими не більша за d? Вони можуть знаходитися лише у квадраті зі сторонами d, то му що відстань між ними і по осі абсцис, і по осі ординат не по винна перевищувати d.
Розглянемо лівий квадрат, зображений на малюнку 169, і доведемо, що у ньому може знаходитись не більше 4 точок, які є кандидатами на перегляд. Нехай ці точки знаходяться у вер шинах квадрата. У такому випадку умова щодо відстані між ними, яка не перевищує d, виконується. Якщо у середину квад рата помістити ще одну п'яту точку, то, де б вона не знаходила ся, серед решти чотирьох точок знайдеться хоча б одна, від стань до якої d' і має місце умова d' < d. А це означає, що саме відстань d' є найменшою і в такому разі ширина лівої частини прикордонної області визначена невірно.
Отже, можна підсумувати, що у лівій частині прикордонної області на кожному кроці слід досліджувати відстань лише між чотирма точками, які розміщені у масиві уі підряд (і = і', і' + 1, V + 2, і' + 3). Звичайно, що ці чотири точки не обов'язково по винні бути розташовані у вершинах квадрата зі стороною d, як це зображено на малюнку 169, вони можуть бути і всередині цього квадрата.
Аналогічно доведення проводиться і для квадрата, що зна ходиться у правій частині прикордонної області. Таким чином, загальна кількість досліджуваних точок, які розміщені у ма сиві уі підряд, становить 8 (на малюнку 169 точки, що наклада ються із лівої та правої частин, зображено незафарбованими). А це означає, що після визначення на й-му кроці найменшої відстані d між парами точок у лівій та правій підмножинах необхідно для кожної точки прикордонної області знайти найменшу відстань до кожної із семи наступних у масиві уг Якщо така відстань виявиться меншою за d, то вона є результа том пошуку на /г-му кроці.
293
Опишемо алгоритм визначення пари найближчих точок.
1 Упорядкувати за зростанням масив xt та масив уі множи ни заданих точок.
2. Прийняти L = 1, R = п.
3. Обчислити m-(L + В) div 2.
4. Розбити елементи масиву xt на дві частини xL (L = 1, 2,..., т),
xR (R = т + 1, т + 2, ..., п).
5. Розглянути ліву під множину точок, що відповідають ма
сиву xL.
6. Якщо кількість елементів у масиві більша за 3, то пере йти до п. 3.
7.Визначити найменшу відстань d між трьома точками мно жини.
8.Якщо підмножина точок, що розглядається, є правою, то визначити точки, які входять до прикордонної області, і знай ти для них найменшу відстань. Для цього розглядати групи по
вісім точок, що упорядковані за зростанням у масиві уг Якщо обчислена відстань є меншою за d, то прийняти її як d.
9.Розглянути праву під множину точок, що відповідають
масиву xR.
10.Якщо кількість елементів у масиві більша за 3, то пере йти до п. 3.
11.Визначити найменшу відстань d між трьома точками множини.
12.Якщо підмножина точок, що розглядається, є правою, то визначити точки, які входять до прикордонної області, і знайти для них найменшу відстань. Для цього розглядати групи по вісім точок, що упорядковані за зростанням у маси ві у.. Якщо обчислена відстань є меншою за d, то прийняти її як d.
Для реалізації алгоритму мовою програмування необхідно ввести деякі домовленості. Після упорядкування масивів xt та у. у п. 1 буде порушено відповідність між координатами зада них точок. Для збереження цієї інформації можна використати масив pt, у якому міститимуться порядкові номери елементів масиву yt, що відповідають точкам із масиву хг Наведемо при клад. Нехай задано три точки з координатами;?^; 5),р2(1; 10), р3 (4; 12). Спочатку упорядкуємо масив xt за зростанням з одно часним перенесенням відповідних елементів масиву yt: xt(l; 2; 4), yt(10; 5; 12). Якщо тепер виконати упорядкування за зростан ням у масиві yt, то відповідність координат заданих точок буде порушена: yt= (5; 10; 12). Але якщо у масиві/?, сформувати та ку інформацію (2; 1; 3), то це означатиме, що ордината точки з абсцисою хх = 1 міститься у масиві уі під порядковим номером pv а саме на 2-му місці.
294
З урахуванням усього зазначеного вище фрагмент основної програми, що реалізує алгоритм визначення пари найближчих точок, запропонований Шамотом, виглядатиме так:
а := х; flag := false; |
{Ініціалізація сортування заданих точок по осі абсцис.} |
||
SOrt( 1, п); |
{Сортування заданих точок по осі абсцис.} |
||
X := а; |
{Збереження відсортованої по осі абсцис вхідної інформації у масиві х.} |
||
|
|
{Початкове значення найменшої} |
|
d j m i n |
:= sqrt(sqr(x[1] - х[2]) + sqr(y[1] - у[2])); |
{відстані.} |
|
for І := 1 t o n do р[І] := І; |
|
{Створення масивур.) |
|
а := у; flag := true; |
{Ініціалізація сортування заданих точок по осі ординат.} |
||
SOrt(1, п); |
{Сортування заданих точок по осі ординат.} |
||
у1 := а; {Збереження відсортованої по осі ординат вхідної інформації у масиві у.) dist( 1, п); {Визначення найменшої відстані між заданими точками.}
Варто розглянути ще процедуру, яка упорядковує послідов ність координат заданих точок як по осі абсцис, так і по осі ор динат:
procedure sort(L, R: word); |
|
|
var і, j, L_R, c: word; w, d: real; |
|
|
begin |
|
|
i:=L;j:=R;L _ R:=(L+R)div2 ; |
|
|
w:=a[L_R]; |
|
|
repeat |
|
|
while a[i] < w do і := і + 1; |
|
|
while w < a[j] do j := j - 1; |
|
|
if і <= j then |
|
|
begin |
|
|
d :=a[i];a[i] |
:=a[j];a[j] : = d ; |
|
if not flag |
|
|
|
|
{Перше сортування} |
then begin d |
:=y[i];y[i] :=y[j];y[j] : = c 1 end; |
{по осі абсцис.} |
if flag |
|
|
|
|
{Друге сортування} |
then begin c := p[i]; p[i] := p[j]; p[j] := c end; |
{по осі ординат.} |
|
i:=i + 1 ; j : = j - 1 ; |
|
|
end; |
|
|
until і > j; |
|
|
if j > Lthensort(L, j); if i< Rthensort(i, R)
end;
Рекурсивна процедура dist, яка визначає мінімальну від стань між парою точок:
procedure dist(L, R: word); var і, j, m, k: word;
begin
І := L; j := R; m := (L + R) div 2; {Розбиття поточної групи точок на дві підгрупи.} if j - І <= 2 {Якщо кількість точок у групі менше трьох,}
295
/
then |
|
begin |
|
w h i l e І <= j do |
{то визначення найменшої відстані між точками групи:} |
begin |
|
k:=i + 1; |
|
while k <= j do |
|
begin
d := sqrt(sqr(x[i] - x[k]) + sqr(y[i] - y[k])); {обчислення відстані і,}
if d < d_min |
{якщо вона оптимальніша, то} |
|
then begin |
|
|
|
d_min := d; |
{запам'ятати цю відстань} |
|
xL:=x[i]; yl_ :=y[i]; |
{і координати} |
|
xR := x[k]; yR := y[k]; |
{відповідних точок;} |
|
end; |
|
inc(k) |
|
|
end; |
|
|
inc(i) |
|
|
end |
|
|
end |
|
|
else |
|
{у протилежному випадку перехід до} |
begin |
{рекурсивного поділу навпіл поточної групи точок.} |
|
dist(L, m); |
|
{Перехід до лівої підгрупи.} |
dist(m + 1, R); |
{Перехід до правої підгрупи.} |
|
limit(m + 1) |
{Пошук найменшої відстані між точками у прикордонній області.} |
|
end; |
|
|
end; |
|
|
Процедура limit, яка визначає мінімальну відстань між па рою точок у прикордонній області:
procedure limit(m: word); |
|
|
var L, R, k, min, max: word; |
|
|
begin |
|
|
k := m + 1; |
{Визначення правої межі прикордонної області для т-'і точки.} |
|
while x[k] - x [ m ] <= djmin do inc(k); |
||
R := k - 1; |
{R - номер найправішої точки прикордонної області.} |
|
k := m - 1; |
{Визначення лівої межі прикордонної області для т-'і точки.} |
|
while x[m] - x[k] <= d_min do dec(k); |
||
L := k + 1; |
{L - номер найлівішої точки прикордонної області.} |
|
{Визначення точок, які потрапляють у прикордонну область [L:R].} |
||
min := n; max := 0; k := L; |
{Визначення інтервалу [min.max] у масиві p,} |
|
while k <= R do |
{у якому знаходяться точки із прикордонної області.} |
|
begin |
|
|
if (L <= p[k]) and (p[k] <= R) |
{Вибір точок із масиву р,} |
|
then |
|
{які належать прикордонній області.} |
begin |
|
|
if p[k] < min then min := p[k];
if p[k] >= max then max := p[k]; end;
inc(k)
end;
296