Risteyksen ongelma
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. toukokuuta 2021 tarkistetusta
versiosta . vahvistus vaatii
1 muokkauksen .
Janan leikkauspisteen ongelmana on määrittää , leikkaavatko mitkään kaksi janaa tietystä listasta tasossa .
Yksinkertaiset algoritmit tarkistavat jokaisen segmentin parin. Jos kuitenkin tarkastetaan suuri määrä viivan osia leikkauspisteiden varalta, tehtävästä tulee asteittain tehoton, koska useimmat janaparit eivät ole lähellä toisiaan normaalissa syötössä. Yleisin ja tehokkaampi tapa ratkaista tämä ongelma suurella määrällä segmenttejä on käyttää pyyhkäisyviivaalgoritmia , jossa kuvittelemme osien läpi kulkevan suoran ja seuraamme segmenttien leikkauspisteitä binäärihakuun perustuvan tietorakenteen avulla. puita . Shamos-Howey-algoritmi [1] käyttää tätä periaatetta ratkaistakseen viivaosien leikkauspisteen löytämisongelman, kuten edellä on kuvattu. Bentley-Ottmann-algoritmitoimii samalla periaatteella ja löytää luettelon kaikista risteyksistä logaritmisessa ajassa per leikkaus.
Katso myös
Muistiinpanot
- ↑ Shamos ja Hoey 1976 , s. 208.
Kirjallisuus
- 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. Luku 2: Viivasegmenttien leikkaus // Laskennallinen geometria . – 2. - Springer, 2000. - S. 19-44. — ISBN 3-540-65620-0 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Osio 33.2: Sen määrittäminen, leikkaako jokin segmenttipari // Algoritmien esittely . - Toinen painos. - MIT Press ja McGraw-Hill, 1990. - S. 934-947. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmit: Rakentaminen ja analyysi , 3. painos = Algoritmien johdatus, kolmas painos. - M. : "Williams" , 2013. - 1328 s. - ISBN 978-5-8459-1794-2 .
- Bentley JL, Ottmann T. Algoritmit geometristen leikkauspisteiden raportointiin ja laskemiseen // IEEE Trans. Comput. - 1979. - Numero. C28 . — S. 643–647 .
Linkit