Перетин відрізків

В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізоків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися.

Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою[en], в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті відрізки, які пряма перетинає в кожен момент часу в динамічній структурі даних побудованій на основі бінарного дерева пошуку. Алгоритм Шамоса - Хойї[1] застосовує цей принцип для розв'язання задачи виявлення перетину відрізків, як зазначено вище, для визначення того, чи має множина відрізків перетин. Алгоритм Бентлі — Оттманна працює за тим же принципом для того, щоб перелічити всі перетини за логарифмічний час.

Див. такожРедагувати

ПриміткиРедагувати

  1. Shamos, M. I.; Hoey, D. (1976). 17th Annual Symposium on Foundations of Computer Science (sfcs 1976). с. 208. doi:10.1109/SFCS.1976.16.  Chapter: «Geometric intersection problems»

ЛітератураРедагувати

ПосиланняРедагувати