Sweeping Line Algorithm

A söprővonal -algoritmus vagy síkseprő-algoritmus  egy olyan algoritmikus paradigma, amely spekulatív söprővonalat vagy söprőfelületet használ az euklideszi tér különböző problémáinak megoldására . Ez a számítási geometria egyik kulcstechnikája.

Az ilyen típusú algoritmusok ötlete egy képzeletbeli egyenes vonal (általában függőleges) elképzelése, amely a sík mentén mozog, néhány ponton megállva. A geometriai műveletek azokra a geometriai objektumokra korlátozódnak, amelyek vagy metszik a söprő vonalat, vagy szomszédosak vele, és a teljes megoldás akkor érhető el, ha a vonal áthalad az összes objektumon.

Történelem

Ez a megközelítés a számítógépes grafikában a vonal-letapogatási algoritmusokra vezethető vissza , majd ezt a megközelítést alkalmazták a korai integrált áramkör-elrendezési algoritmusokban , amelyekben az integrált áramkör geometriai leírását párhuzamos formában végezték el. csíkok, mivel a teljes leírás nem fért be a memóriába.

Alkalmazások

Ennek a megközelítésnek az alkalmazása áttörést hozott a geometriai algoritmusok számítási bonyolultságában, amikor Shamos és Howey algoritmusokat mutatott be a vonalszakaszok síkban történő metszésére, és különösen azt írták le, hogyan lehet kombinálni a pásztázási vonal megközelítést hatékony adatstruktúrákkal ( kiegyensúlyozott bináris fák ) lehetővé teszi annak kimutatását, hogy van-e a síkban N szakasz metszéspontja, O bonyolultságú [1] . A szorosan kapcsolódó Bentley-Ottmann algoritmus a sweeping line technikát használja, hogy megkapja az összes K metszéspontot bármely N vonalszakasz között egy időbeli és memóriabonyolultságú síkban [2] .

Azóta ezt a megközelítést hatékony algoritmusok kifejlesztésére használták számos problémára, például Voronoi-diagram ( Fortune algoritmus ) felépítésére, Delaunay-háromszögelésre vagy Boole-műveletek sokszögekre .

Általánosítások és kiterjesztések

A topologikus ballayage egy olyan síkbalayage, amely lazítja a feldolgozott pontok sorrendjére vonatkozó követelményeket, így elkerülhető a pontok teljes rendezése, és lehetővé teszi a söprővonal-algoritmus hatékonyabb működését.

A geometriai algoritmusok készítésére szolgáló forgó tolómérő technika egyfajta balayageként is értelmezhető a projektív kettős síkban – a projektív dualitása síkban lévő egyenes meredekségét a kettős síkban lévő pont x -koordinátájává alakítja, hogy a vonal áthaladása a meredeksége szerint legyen rendezve. Így a forgó tolómérő algoritmus folyamata a síkbalayage algoritmusban az x koordinátáik szerint rendezett pontokon való áthaladás kettős folyamata

Az elsöprő megközelítés magasabb dimenziókra is általánosítható.

Jegyzetek

1. ↑ Shamos és Hoey 1976 , p. 208–215.
2. ↑ Souvaine, 2008 .

Irodalom

• Michael I. Shamos, Dan Hoey. Geometriai metszésponti problémák // Proc. 17. IEEE Symp. A számítástechnika alapjai (FOCS '76). - 1976. - S. 208-215. - doi : 10.1109/SFCS.1976.16 .
• Diane Souvaine. Vonalszakasz metszéspontja Sweep Line Algoritmus használatával . – 2008.