Průsečík víceřádkových segmentů - Multiple line segment intersection - Wikipedia

v výpočetní geometrie, průsečík víceřádkových segmentů problém dodává seznam úsečky v Euklidovské letadlo a ptá se, zda jsou dva protínají (přejít).

Jednoduché algoritmy zkoumají každou dvojici segmentů. Pokud však má být zkontrolováno velké množství potenciálně protínajících se segmentů, stává se to stále neúčinnější, protože většina párů segmentů není v typické vstupní posloupnosti blízko sebe. Nejběžnějším a efektivnějším způsobem, jak vyřešit tento problém u vysokého počtu segmentů, je použití a algoritmus zatáčkové čáry, kde si představujeme úsečku klouzající po úsečkách a sledujeme, které úsečky protíná v každém časovém bodě pomocí dynamické datové struktury založené na binární vyhledávací stromy. The Algoritmus Shamos – Hoey^[1] aplikuje tento princip na vyřešení problému detekce průsečíků úseček, jak je uvedeno výše, při určování, zda má řada úseček průsečík; the Algoritmus Bentley – Ottmann funguje na stejném principu, aby vypsal všechny křižovatky v logaritmickém čase na křižovatku.

Reference

Další čtení

• Mark de Berg; Marc van Kreveld; Mark Overmars; a Otfried Schwarzkopf (2000). Výpočetní geometrie (2. vyd.). Springer. ISBN  3-540-65620-0. Kapitola 2: Průsečík úseček, str. 19–44.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 1990. ISBN  0-262-03293-7. Oddíl 33.2: Určení, zda se protíná některá dvojice segmentů, s. 934–947.
• J. L. Bentley a T. Ottmann., Algoritmy pro hlášení a počítání geometrických křižovatek, IEEE Trans. Comput. C28 (1979), 643–647.

externí odkazy

• Křižovatky čar a rovin Algoritmy a ukázkový kód od Dan Sunday
• Robert Pless. Přednáška 4 poznámky. Washingtonská univerzita v St. Louis, CS 506: Výpočetní geometrie (kopie v mezipaměti ).
• Průsečík úsečky v CGAL, Knihovna algoritmů výpočetní geometrie
• „Průsečík segmentu čáry“ poznámky k přednášce Jeff Erickson.
• Metoda průsečíku mezi řádky se vzorkem kódu C. Darel Rex Finley

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.