В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися.
Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде (квадратичною) для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті відрізки, які пряма перетинає в кожен момент часу в динамічній структурі даних побудованій на основі бінарного дерева пошуку. застосовує цей принцип для розв'язання задачи виявлення перетину відрізків, як зазначено вище, для визначення того, чи має множина відрізків перетин. Алгоритм Бентлі — Оттманна працює за тим же принципом для того, щоб перелічити всі перетини за логарифмічний час.
Див. також
Примітки
- 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»
Література
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 33.2: Перевірка наявності непорожнього попарного перетину серед множини відрізків. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Mark de Berg; Marc van Kreveld; Mark Overmars; and Otfried Schwarzkopf (2000). Computational Geometry (вид. 2nd). Springer. ISBN . 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 в — бібліотеці алгоритмів обчислювальної геометрії
- «Line Segment Intersection» Конспекти лекцій Джеффа Еріксона.
- Line-Line Intersection Method With C Code Sample від Дарела Рекса Фінлі
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V obchislyuvalnij geometriyi zadacha pro peretin vidrizkiv dlya zadanogo spisku vidrizkiv na evklidovij ploshini z yasovuye chi znajdetsya sered nih para vidrizkiv yaki budut peretinatisya Primitivnij algoritm yakij virishuye cyu zadachu mozhe pereviryati kozhnu paru vidrizkiv na peretin Shvidkist takogo algoritmu bude kvadratichnoyu O n 2 displaystyle O n 2 dlya n displaystyle n vidrizkiv Tomu koli potribno pereviriti duzhe veliku kilkist vidrizkiv na peretin cej algoritm staye vse bilsh neefektivnim oskilki bilshist par vidrizkiv ne ye blizkimi odin do odnogo dlya dovilnoyi poslidovnosti vidrizkiv Najposhirenishij i bilsh efektivnij sposib rozv yazati cyu zadachu dlya velikoyi kilkosti vidrizkiv ce vikoristovuvati metod zamitannya pryamoyu v yakomu pryama prosuvayetsya po vporyadkovanij poslidovnosti vidrizkiv a mi pereviryayemo na peretin ti vidrizki yaki pryama peretinaye v kozhen moment chasu v dinamichnij strukturi danih pobudovanij na osnovi binarnogo dereva poshuku zastosovuye cej princip dlya rozv yazannya zadachi viyavlennya peretinu vidrizkiv yak zaznacheno vishe dlya viznachennya togo chi maye mnozhina vidrizkiv peretin Algoritm Bentli Ottmanna pracyuye za tim zhe principom dlya togo shob perelichiti vsi peretini za logarifmichnij chas Div takozhAksioma paralelnosti Evklida Proyekciya tochki na pryamu Peretin pryamihPrimitkiShamos 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 Literatura T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 33 2 Perevirka nayavnosti neporozhnogo poparnogo peretinu sered mnozhini vidrizkiv Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Mark de Berg Marc van Kreveld Mark Overmars and Otfried Schwarzkopf 2000 Computational Geometry vid 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 PosilannyaIntersections of Lines and Planes Algoritmi ta zrazok kodu vid Dena Sandi Robert Pless Lecture 4 notes Universitet Vashingtona v Sent Luyisi CS 506 Obchislyuvalna geometriya Line segment intersection v biblioteci algoritmiv obchislyuvalnoyi geometriyi Line Segment Intersection Konspekti lekcij Dzheffa Eriksona Line Line Intersection Method With C Code Sample vid Darela Reksa Finli