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

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

Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною $O(n^{2})$ для $n$ відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті відрізки, які пряма перетинає в кожен момент часу в динамічній структурі даних побудованій на основі бінарного дерева пошуку. Алгоритм Шамоса - Хойї[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»

Література

Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (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 від Дарела Рекса Фінлі

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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»