Korsningsproblem
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 11 maj 2021; verifiering kräver
1 redigering .
Problemet med skärningspunkten mellan segment är att avgöra om några två segment från en given lista skär varandra i planet .
Enkla algoritmer kontrollerar varje par av segment. Men om ett stort antal linjesegment ska kontrolleras för skärning, blir uppgiften progressivt ineffektiv, eftersom de flesta par av linjesegment inte ligger nära varandra vid normal inmatning. Det vanligaste och mer effektiva sättet att lösa detta problem för ett stort antal segment är att använda sveplinjealgoritmen , där vi föreställer oss en linje som passerar genom segmenten och spårar segmentens skärningspunkter med hjälp av en datastruktur baserad på binär sökning träd . Shamos-Howey-algoritmen [1] tillämpar denna princip för att lösa problemet med att hitta skärningspunkten för linjesegment, som beskrivits ovan. Bentley-Ottmann-algoritmen fungerar på samma princip och hittar en lista över alla korsningar i logaritmisk tid per korsning.
Se även
Anteckningar
- ↑ Shamos och Hoey 1976 , sid. 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: Linjesegmentkorsning // Computational Geometry . — 2:a. - Springer, 2000. - S. 19-44. — ISBN 3-540-65620-0 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Avsnitt 33.2: Bestämma om något par av segment skär varandra // Introduktion till algoritmer . - Andra upplagan. - MIT Press och McGraw-Hill, 1990. - S. 934-947. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: Konstruktion och analys , 3:e upplagan = Introduktion till algoritmer, tredje upplagan. - M. : "Williams" , 2013. - 1328 sid. - ISBN 978-5-8459-1794-2 .
- Bentley JL, Ottmann T. Algoritmer för rapportering och räkning av geometriska skärningar // IEEE Trans. Comput. - 1979. - Utgåva. C28 . — S. 643–647 .
Länkar