Skärning med flera linjesegment
I beräkningsgeometri tillhandahåller problemet med korsning av flera linjesegment en lista över linjesegment i det euklidiska planet och frågar om två av dem skär varandra (korsar).
Enkla algoritmer undersöker varje par av segment. Men om ett stort antal eventuellt korsande segment ska kontrolleras, blir detta allt mer ineffektivt eftersom de flesta par av segment inte är nära varandra i en typisk ingångssekvens. Det vanligaste och mer effektiva sättet att lösa detta problem för ett stort antal segment är att använda en sveplinjealgoritm , där vi föreställer oss en linje som glider över linjesegmenten och vi spårar vilka linjesegment den skär vid varje tidpunkt med hjälp av en dynamisk datastruktur baserad på binära sökträd . Shamos-Hoey-algoritmen tillämpar denna princip för att lösa detektionsproblemet för linjesegmentkorsning, som nämnts ovan, att bestämma huruvida en uppsättning linjesegment har en korsning eller inte; Bentley -Ottmann-algoritmen fungerar enligt samma princip för att lista alla korsningar i logaritmisk tid per korsning.
Se även
Vidare läsning
- Mark de Berg; Marc van Kreveld; Mark Overmars; och Otfried Schwarzkopf (2000). Computational Geometry (2:a upplagan). Springer. ISBN 3-540-65620-0 . Kapitel 2: Linjesegmentskorsning, s. 19–44.
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer, andra upplagan. MIT Press och McGraw-Hill, 1990. ISBN 0-262-03293-7 . Avsnitt 33.2: Bestämma om något par av segment skär varandra, s. 934–947.
- JL Bentley och T. Ottmann., Algoritmer för rapportering och räkning av geometriska skärningar, IEEE Trans. Comput. C28 (1979), 643-647.
externa länkar
- Skärningspunkter mellan linjer och plan Algoritmer och exempelkod av Dan Sunday
- Robert Pless. Föreläsning 4 anteckningar . Washington University i St Louis , CS 506: Computational Geometry ( cachad kopia ).
- Linjesegmentkorsning i CGAL , Computational Geometry Algorithms Library
- "Line Segment Intersection" föreläsningsanteckningar av Jeff Erickson.
- Linje-linje skärningsmetod med C-kodprov Darel Rex Finley