Problém s křižovatkou
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 11. května 2021; ověření vyžaduje
1 úpravu .
Problém průsečíku segmentů je určit, zda se nějaké dva segmenty z daného seznamu protínají v rovině .
Jednoduché algoritmy kontrolují každý pár segmentů. Pokud však má být zkontrolováno, zda se protínají velké množství liniových segmentů, úloha se stává postupně neefektivní, protože většina párů liniových segmentů neleží blízko sebe při běžném vstupu. Nejběžnějším a nejúčinnějším způsobem, jak tento problém vyřešit pro velký počet segmentů, je použít algoritmus sweeping line , ve kterém si představíme čáru procházející segmenty a sledujeme průsečíky segmentů pomocí datové struktury založené na binárním vyhledávání . stromy . Algoritmus Shamos-Howey [1] používá tento princip k řešení problému nalezení průsečíku úseček, jak je popsáno výše. Algoritmus Bentley-Ottmann pracuje na stejném principu a najde seznam všech průsečíků v logaritmickém čase na průsečík.
Viz také
Poznámky
- ↑ Shamos and Hoey 1976 , str. 208.
Literatura
- Shamos MI, Hoey D. 17. výroční sympozium o základech informatiky (sfcs 1976) . - 1976. - doi : 10.1109/SFCS.1976.16 .
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Kapitola 2: Průsečík liniových segmentů // Výpočtová geometrie . — 2. - Springer, 2000. - S. 19-44. — ISBN 3-540-65620-0 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Oddíl 33.2: Určení, zda se nějaká dvojice segmentů protíná // Úvod do algoritmů . - Druhé vydání. - MIT Press a McGraw-Hill, 1990. - S. 934-947. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms: Construction and Analysis , 3rd Edition = Introduction to Algorithms, Third Edition. - M. : "Williams" , 2013. - 1328 s. - ISBN 978-5-8459-1794-2 .
- Bentley JL, Ottmann T. Algoritmy pro hlášení a počítání geometrických průniků // IEEE Trans. Počítat. - 1979. - Vydání. C28 . — S. 643–647 .
Odkazy