Kereszteződés probléma
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 11-én felülvizsgált
verziótól ; az ellenőrzéshez
1 szerkesztés szükséges .
A szakaszok metszéspontjának problémája annak meghatározása , hogy egy adott listából bármelyik két szakasz metszi -e egymást a síkban .
Egyszerű algoritmusok minden szegmenspárt ellenőriznek. Ha azonban nagyszámú vonalszakasz metszéspontját kell ellenőrizni, a feladat fokozatosan hatástalanná válik, mivel a legtöbb vonalszakaszpár normál bemenetben nem esik közel egymáshoz. A probléma megoldásának legelterjedtebb és leghatékonyabb módja nagyszámú szegmens esetén a sweeping line algoritmus használata , amelyben elképzelünk egy vonalat, amely áthalad a szegmenseken, és egy bináris keresésen alapuló adatstruktúra segítségével követjük a szakaszok metszéspontjait. fák . A Shamos-Howey algoritmus [1] ezt az elvet alkalmazza a vonalszakaszok metszéspontjának megtalálásának problémájának megoldására, a fent leírtak szerint. A Bentley-Ottmann algoritmus ugyanezen az elven működik, és megkeresi az összes metszéspontot logaritmikus időben metszéspontonként.
Lásd még
Jegyzetek
- ↑ Shamos és Hoey 1976 , p. 208.
Irodalom
- 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. 2. fejezet: Vonalszakasz metszéspont // Számítógépes geometria . — 2. - Springer, 2000. - S. 19-44. — ISBN 3-540-65620-0 .
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . 33.2. szakasz: Annak meghatározása, hogy bármely szegmenspár metszi-e egymást // Bevezetés az algoritmusokba . - Második kiadás. - MIT Press és McGraw-Hill, 1990. - S. 934-947. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmusok: Konstrukció és elemzés , 3. kiadás = Bevezetés az algoritmusokba, harmadik kiadás. - M. : "Williams" , 2013. - 1328 p. - ISBN 978-5-8459-1794-2 .
- Bentley JL, Ottmann T. Algoritmusok geometriai metszéspontok jelentéséhez és számlálásához // IEEE Trans. Comput. - 1979. - Kiadás. C28 . – S. 643–647 .
Linkek