Перетин відрізків
В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися.
Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті відрізки, які пряма перетинає в кожен момент часу в динамічній структурі даних побудованій на основі бінарного дерева пошуку. Алгоритм Шамоса - Хойї[1] застосовує цей принцип для розв'язання задачи виявлення перетину відрізків, як зазначено вище, для визначення того, чи має множина відрізків перетин. Алгоритм Бентлі — Оттманна працює за тим же принципом для того, щоб перелічити всі перетини за логарифмічний час.
Див. також ред.
Примітки ред.
- ↑ Shamos, M. I.; Hoey, D. (1976). 17th Annual Symposium on Foundations of Computer Science (sfcs 1976) (PDF): 208. doi:10.1109/SFCS.1976.16. Chapter: «Geometric intersection problems»
Література ред.
- Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019), Розділ 33.2: Перевірка наявності непорожнього попарного перетину серед множини відрізків, Вступ до алгоритмів (вид. 3), К.І.С., с. 1025—1032, ISBN 978-617-684-239-2
- Mark de Berg; Marc van Kreveld; Mark Overmars; and Otfried Schwarzkopf (2000). Computational Geometry (вид. 2nd). Springer. ISBN 3-540-65620-0. Chapter 2: Line Segment Intersection, pp. 19–44.
- J. L. Bentley and T. Ottmann., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput. C28 (1979), 643—647.
Посилання ред.
- Intersections of Lines and Planes Алгоритми та зразок коду від Дена Санді
- Robert Pless. Lecture 4 notes. Університет Вашингтона в Сент-Луїсі, CS 506: Обчислювальна геометрія.
- Line segment intersection в CGAL — бібліотеці алгоритмів обчислювальної геометрії
- «Line Segment Intersection» Конспекти лекцій Джеффа Еріксона.
- Line-Line Intersection Method With C Code Sample від Дарела Рекса Фінлі