Vejkryds problem
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den
version , der blev gennemgået den 11. maj 2021; verifikation kræver
1 redigering .
Problemet med skæringspunktet mellem segmenter er at bestemme, om to segmenter fra en given liste skærer hinanden i planet .
Simple algoritmer kontrollerer hvert par af segmenter. Men hvis et stort antal linjestykker skal kontrolleres for skæring, bliver opgaven gradvist ineffektiv, da de fleste par af linjestykker ikke ligger tæt på hinanden i normal input. Den mest almindelige og mere effektive måde at løse dette problem på for et stort antal segmenter er at bruge sweeping line-algoritmen , hvor vi forestiller os en linje, der passerer gennem segmenterne og sporer segmenternes skæringspunkter ved hjælp af en datastruktur baseret på binær søgning træer . Shamos-Howey-algoritmen [1] anvender dette princip til at løse problemet med at finde skæringspunktet mellem linjestykker, som beskrevet ovenfor. Bentley-Ottmann algoritmearbejder efter samme princip og finder en liste over alle skæringspunkter i logaritmisk tid pr. skæringspunkt.
Se også
Noter
- ↑ Shamos og Hoey 1976 , s. 208.
Litteratur
- Shamos MI, Hoey D. 17th Annual Symposium on Foundations of Computer Science (sfcs 1976) . - 1976. - doi : 10.1109/SFCS.1976.16 .
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Kapitel 2: Linjesegmentskrydsning // Beregningsgeometri . — 2. - Springer, 2000. - S. 19-44. — ISBN 3-540-65620-0 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Afsnit 33.2: Bestemmelse af, om et par af segmenter skærer // Introduktion til algoritmer . - Anden version. - MIT Press og McGraw-Hill, 1990. - S. 934-947. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: Konstruktion og analyse , 3. udgave = Introduktion til algoritmer, tredje udgave. - M. : "Williams" , 2013. - 1328 s. - ISBN 978-5-8459-1794-2 .
- Bentley JL, Ottmann T. Algoritmer til rapportering og optælling af geometriske skæringspunkter // IEEE Trans. Comput. - 1979. - Udgave. C28 . — S. 643–647 .
Links