Problema intersectiei
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită pe 11 mai 2021; verificarea necesită
1 editare .
Problema intersectării segmentelor este de a determina dacă oricare două segmente dintr-o listă dată se intersectează în plan .
Algoritmii simpli verifică fiecare pereche de segmente. Cu toate acestea, dacă un număr mare de segmente de linie urmează să fie verificate pentru intersecție, sarcina devine progresiv ineficientă, deoarece majoritatea perechilor de segmente de linie nu se află aproape una de alta în intrarea normală. Cea mai comună și mai eficientă modalitate de a rezolva această problemă pentru un număr mare de segmente este folosirea algoritmului de sweeping line , în care ne imaginăm o linie care trece prin segmente și urmărim intersecțiile segmentelor folosind o structură de date bazată pe căutare binară . copaci . Algoritmul Shamos-Howey [1] aplică acest principiu pentru a rezolva problema găsirii intersecției segmentelor de linie, așa cum este descris mai sus. Algoritmul Bentley-Ottmann funcționează pe același principiu și găsește o listă a tuturor intersecțiilor în timp logaritmic per intersecție.
Vezi și
Note
- ↑ Shamos și Hoey 1976 , p. 208.
Literatură
- Shamos MI, Hoey D. Simpozionul anual al 17-lea despre fundamentele informaticii (sfcs 1976) . - 1976. - doi : 10.1109/SFCS.1976.16 .
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Capitolul 2: Intersecția segmentului de linie // Geometrie computațională . — al 2-lea. - Springer, 2000. - S. 19-44. — ISBN 3-540-65620-0 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Secțiunea 33.2: Determinarea dacă vreo pereche de segmente se intersectează // Introducere în algoritmi . - A doua editie. - MIT Press și McGraw-Hill, 1990. - S. 934-947. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: Construcție și analiză , ediția a treia = Introducere în algoritmi, ediția a treia. - M. : „Williams” , 2013. - 1328 p. - ISBN 978-5-8459-1794-2 .
- Bentley JL, Ottmann T. Algoritmi pentru raportarea și numărarea intersecțiilor geometrice // IEEE Trans. Calculator. - 1979. - Emisiune. C28 . — S. 643–647 .
Link -uri