Материал: 252_337
{Обчислення відстані від поточної точки /до точки р[к],} {з якої ведеться спостереження.}
d_k_i := sqrt(sqr(x[i] - x[p[k]]) + sqr(y[i] - y[p[k]]));
{Обчислення лівого кута повороту від останньої точки, включеної} {до послідовності вершин опуклої оболонки, до поточної /-Ї точки.} angl := (у[і] - y[p[k]])/d_k_i); {Обчислення значення синуса лівого кута.}
c a s e pr of |
{Визначення частини ланцюга опуклої оболонки.} |
0: |
{Нижня частина ланцюга.} |
|
{Якщо /-та точка знаходиться} |
if (х[і] - х[р[к]] > 0) and ((angl < angljmin) {у правій ПІВПЛОЩИНІ}
|
or ((angl = angljmin) and (d_k_i < d_k_st))) |
{і є найближчою,} |
|
{то вона вибирається} |
|
|
then begin p_st := і; anglmin := angl end; |
{як поточна.} |
1: |
{Верхня частина ланцюга.} |
|
|
{Якщо /-та точка знаходиться у лівій півплощині і є} |
|
if (х[і] - х[р[к]] <= 0) and ((angl > anglmin) |
{у ЛІВІЙ ПІВПЛОЩИНІ} |
|
|
or ((angl = anglmin) and ( d k i < d k s t ) ) ) |
{і є найближчою,} |
|
{то вона вибирається} |
|
|
then begin p s t := i; angl_min := angl end; |
{як поточна.} |
end;
end;
{Додавання визначеної точки до послідовності вершин опуклої оболонки та до) inc(k);p[k] := p_st; st := st + [p_st]; {множини включених до неї вершин.}
end;
Оцінка ефективності роботи алгоритму Джарвіса визначає ться наступним чином. На кожному кроці визначається міні мальне значення лівого кута відхилення від поточної стартової точки. Кількість переглядів заданих точок при цьому ста новить О(п). Таких кроків буде стільки, скільки точок серед множини заданих увійде до опуклої оболонки. Якщо кількість вершин опуклої оболонки позначити k, то загальна оцінка алгоритму Джарвіса буде 0(kn).
Порівняно з першими двома методами, алгоритм Джарвіса виглядає найкращим. Але якщо детальніше проаналізувати, то можна зробити висновок, що кожний із розглянутих методів має як свої переваги, так і свої недоліки.
У методі додавання точок, який, на перший погляд, видаєть ся найменш ефективним, у розрахунках беруть участь саме неперетворені координати заданих точок.
Валгоритмі Грехема всі точки розглядаються лише по одно му разу, однак це досягається їх упорядкуванням за розрахова ним кутом відхилення від стартової точки. Для розрахунку цих кутів використовується формула з операцією ділення та добування квадратного кореня. Це може привести до певної по хибки у результуючих розрахунках.
Валгоритмі Джарвіса, де, як нібито видається, кількість ви конуваних операцій досить невелика, також задіяні розрахун ки з використанням операцій ділення та добування квадратного
287
кореня. Окрім цього, оцінка ефективності виконання цього ал горитму дуже чутлива до кількості вершин опуклої оболонки, тобто якщо всі задані точки виявляться вершинами опуклої обо лонки, то ефективність цього алгоритму перетвориться на 0(п2).
Тестування алгоритму Джарвіса варто проводити на тих са мих тестах, що і попередні алгоритми. Слід також зауважити, що серед тестів бажано, щоб були такі, які дають змогу побачи ти переваги та недоліки всіх трьох алгоритмів. А саме, варто згенерувати такі множини точок, які:
-усі були б вершинами опуклої оболонки;
-половина з них входила до опуклої оболонки;
-якнайбільша кількість точок знаходилась усередині опук лої оболонки.
Завдання
1.Розробити і реалізувати у вигляді програми алгоритм визна чення перетину двох відрізків, заданих координатами своїх кінців.
2.Розробити і реалізувати у вигляді програми алгоритм визна чення положення точки, заданої координатами (х; у), відносно багатокутника, заданого координатами вершин у порядку їх обходу.
3.Виконати завдання 2 для N < 10, N < 100, N < 1000 і для ви падків, коли точка знаходиться:
-всередині багатокутника і не лежить на одній горизон тальній прямій з його вершинами;
-всередині багатокутника і лежить на одній горизонталь ній прямій з його вершинами, перетинаючи їх;
-всередині багатокутника і лежить на одній горизонталь ній прямій з його вершинами, дотикаючись до них;
-поза багатокутником і не лежить на одній горизонтальній прямій з його вершинами;
-поза багатокутником і лежить на одній горизонтальній прямій з його вершинами, перетинаючи їх;
-поза багатокутником і лежить на одній горизонтальній прямій з його вершинами, дотикаючись до них;
-лежить на стороні багатокутника;
-збігається з вершиною багатокутника.
Результат виконання програми окремо для кожного тесту вивести у файл.
4.Розробити і реалізувати у вигляді програми алгоритм побу дови опуклої оболонки методом додавання точок.
5.Розробити і реалізувати у вигляді програми алгоритм Грехема для побудови опуклої оболонки.
6.Розробити і реалізувати у вигляді програми алгоритм Джарвіса для побудови опуклої оболонки.
288
7. Виконати завдання 4-6 для множини точок кількістю N < 10, N ^ 100, N ^ 1000 і для випадків, коли точки розміщені:
-в однаковій кількості у верхній та нижній підмножинах;
-тільки у верхній підмножині;
-тільки у нижній підмножині;
-на одній горизонтальній прямій;
-на одній вертикальній прямій;
-всередині трикутника;
-на сторонах прямокутника.
Результат виконання програми вивести у файл.
8. Зробити письмовий аналіз результатів виконання завдань 7.
/Запитання для самоконтролю
1.Якою ознакою доцільно скористатися для оптимального визна чення умови перетину двох відрізків?
2.Який математичний вираз дає змогу визначити наявність пере тину двох відрізків?
3.Які умови дають змогу визначити тип перетину двох відрізків?
4.Яка умова визначає відсутність перетину двох відрізків?
5.Опишіть алгоритм визначення перетину двох відрізків.
6.Наведіть приклад фрагмента програми, що реалізує алгоритм визначення перетину двох відрізків.
7.Як можна використати систему двох лінійних рівнянь для визна чення перетину двох відрізків? Проаналізуйте ефективність та кого підходу.
8.Як можна використовувати традиційні підходи для визначення положення точки відносно багатокутника?
9.Яким чином можна використати умову перетину відрізків для визначення положення точки відносно багатокутника?
10.Опишіть алгоритм визначення положення точки відносно багато кутника з використанням умови перетину відрізків.
11.Наведіть фрагмент програми, що реалізує алгоритм визначення положення точки відносно багатокутника з використанням умо ви перетину відрізків.
12.Що розуміється під опуклою оболонкою? Наведіть власний приклад.
13.Що є ознакою того, що побудований на заданій множині точок багатокутник є опуклою оболонкою?
14.У чому полягає ідея методу додавання точок для побудови опук лої оболонки?
15.Опишіть алгоритм побудови опуклої оболонки методом дода вання точок.
16.Наведіть фрагмент програми, що реалізує алгоритм побудови опуклої оболонки методом додавання точок.
17.Якою є оцінка ефективності виконання алгоритму побудови опуклої оболонки методом додавання точок?
18.На якій ідеї ґрунтується алгоритм Грехема для побудови опуклої оболонки?
19.Опишіть алгоритм Грехема для побудови опуклої оболонки.
20.Виконайте покроково на власному прикладі алгоритм Грехема для побудови опуклої оболонки.
10 Інформатика, 9-Ю кл. |
ї |
289 |
|
|
21. Наведіть фрагмент програми, що реалізує алгоритм Грехема побудови опуклої оболонки.
22.Якою є оцінка ефективності виконання побудови опуклої обо лонки з використанням алгоритму Грехема?
23.Якою є ідея побудови опуклої оболонки алгоритмом Джарвіса?
24.Опишіть алгоритм Джарвіса для побудови опуклої оболонки.
25.Обґрунтуйте математичну складову алгоритму Джарвіса.
26.Виконайте покроково на власному прикладі алгоритм Джарвіса для побудови опуклої оболонки.
27.Наведіть фрагмент програми, що реалізує алгоритм Джарвіса побудови опуклої оболонки.
28.Якою є оцінка ефективності виконання побудови опуклої обо лонки з використанням алгоритму Джарвіса?
29.Проведіть порівняльний аналіз трьох алгоритмів побудови опук лої оболонки.
Визначення пари найближчих та найвіддаленіших точок
Найближчі точки
Задача знаходження пари найближчих точок серед множи ни заданих є досить поширеною і корисною на практиці. На приклад, може виникнути необхідність попередження можли вого зіткнення транспортних засобів під час контролю їх руху або визначення найближчої патрульної машини до місця
транспортної пригоди тощо. |
|
|
|
||||||
|
_ |
|
|
|
|
На перший погляд задача |
ви- |
||
|
щ- |
|
|
|
щ. |
дається нескладною: можливо, не- |
|||
|
|
|
|
||||||
/ |
\ |
|
|
Рг |
обхідно |
спочатку |
визначити |
дві |
|
/ |
\ |
|
|
|
|
точки з найменшою відстанню між |
|||
pt |
\ |
|
|
|
|
значеннями їхніх абсцис, а потім і |
|||
|
\ |
|
|
|
ординат? Однак такий підхід мож- |
||||
|
\ |
|
|
|
на назвати «жадібним», і про це |
||||
|
*Р1 |
|
|
|
свідчить |
приклад, |
зображений |
на |
|
|
|
М а л |
1 6 5 |
|
|
малюнку 165. На перший погляд, |
|||
|
|
|
|
|
|
найближче по осі абсцис розташо |
|||
вані точки рх |
і р2, |
а по осі ординат - точки р2 |
і р3. Однак вияв |
||||||
ляється, що найменшою є відстань між точками р2 ір4. Можна зробити висновок, що неможливо встановити пріори
тет щодо аналізу відстані між точками по осі абсцис та ординат. Необхідно обчислювати відстань між точками за формулою
yjix'i -хі+1)2 + {уі -уі+1)2 та порівнювати отримані значення. Най простіший алгоритм полягає у дослідженні всіх можливих пар точок і порівнянні обчислених значень відстаней між ними. Та кий алгоритм матиме оцінку ефективності 0(п2).
290
•£
a) |
6) |
Мал. 166
Однак у 1985 p. вченим Мішелем Яном Шамосом був за пропонований інший алгоритм, що дає значно кращу оцінку.
Воснову алгоритму покладено метод «розділяй і володарюй». Розглянемо множину із п точок р і відповідні масиви їх ко
ординат хі і уг Кожний із масивів координат точок упорядкова ний за зростанням їх значень.
Нескладно переконатися, що у разі, коли п < 3, то, перебира ючи всі можливі пари цих точок, а їх не більше трьох, і порівню ючи відстані між ними, можна визначити найближчі дві точки.
Якщо п > 3, то діятимемо наступним чином. Побудуємо умовну вертикальну пряму / так, щоб вона розділила множину точок р на дві максимально рівні частини рь і pR. Цю пряму можна провести між двома центральними точками в упорядко ваній послідовності xt, якщо їх кількість є парною (мал. 166, а), або через точку, що має значення xk, де k = п div 2 (мал. 166, б). Вважатимемо, що точки, які можуть опинитися на прямій І, а саме точки з однаковими значеннями xk та з різними по осі ор динат, так само будуть якимось чином розділені на дві побудо вані під множини. Оскільки поділ точок на ліву і праву частини відбувся з урахуванням їх значень по осі абсцис, то і масив їх значень по осі ординат уі буде розбито на дві частини ана логічним чином.
Далі пошук найближчих точок перенесемо окремо у ліву pL та праву рд частини і вчинимо з цими частинами так само, як і із заданою множиною точок р. У кожній із цих частин маси ви xL і хя упорядковані за зростанням, а масиви yL і yR поділені таким чином, що відповідають точкам у цих частинах. Зро зуміло, що даний алгоритм є рекурсивним: саме організація рекурсії дає змогу реалізувати звернення до кожної із частин з таким самим алгоритмом, що і на початку. Отже, у кожній із частин побудуємо уявні вертикальні прямі, що ділять точки, які їм належать, на дві максимально рівноцінні частини.
Цей процес продовжуватиметься до того часу, поки не буде отримано підмножину точок із кількістю, що не перевищує 3. А для цієї кількості точок, як відомо, нескладно за три обчис лення знайти найближчу пару точок.
10* |
291 |