Корисник:Св4и8/превод2

Алгоритам померајуће праве

У рачунарској геометрији, алгоритам „померајуће праве“ или „sweep line“ алгоритам је алгоритамска парадигма која користи концептуалну праву или површ која се „помера“ како би решила различите проблеме у Еуклидском простору. Ово је једна од кључних техника у рачунарској геометрији.

Идеја иза ових алгоритама је замишљање да се права (често вертикална) „помера“ преко равни, заустављајући се на одређеним тачкама. Геометријске операције су ограничене на објекте који се пресецају или се налазе у непосредној близини ове праве када се она заустави, а коначно решење је доступно након што права пређе све објекте.

Историја

Овај приступ води порекло од алгоритама за скенирање (scanline algorithms) за рендеровање у компјутерској графици, а затим се примењује у разним алгоритмима за пројектовање интегрисаних кола, где је геометријски опис ИЦ-а обрађиван у паралелним тракама јер цео опис није могао да стане у меморију.

Примене

Примена овог приступа довела је до напретка у рачунарској сложености геометријских алгоритама када су Шамос и Хои представили алгоритме за пресецање дужи у равни 1976. године. Посебно су описали како комбинација овог приступа са ефикасним структурама података (само-балансирајућа бинарна стабла) омогућава детекцију да ли постоје пресекања између N дужи у равни са временском сложеношћу O(N log N)^[1]. Сродни Бентли-Отман алгоритам користи технику померајуће праве за проналажење свих K пресека међу N дужи у равни са временском сложеношћу O((N + K) log N) и просторном сложеношћу O(N)^[2].

Од тада, овај приступ се користи за дизајнирање ефикасних алгоритама за бројне проблеме у рачунарској геометрији, као што су конструкција Воронојевог дијаграма (Фортуне-ов алгоритам), Делонеова триангулација или Булове операције над полигонима.

Генерализације и проширења

Тополошко померање је облик „померајуће праве“ са једноставним редоследом обраде тачака, што избегава потребу за потпуним сортирањем тачака и омогућава да се неки алгоритми ове врсте изведу ефикасније.

Техника ротирајућих калпера за дизајнирање геометријских алгоритама такође се може интерпретирати као облик „померајуће праве“, у пројективном дуалу улазне равни: облик пројективног дуалитета трансформише нагиб праве у једној равни у x-координату тачке у дуалној равни, тако да је напредак кроз праве сортиране по нагибу у алгоритму са ротирајућим калпером дуалан напретку кроз тачке сортиране по x-координатама у алгоритму са померајућом правом.

Овај приступ се може генерализовати на више димензија.^[3]

Референце

↑ Shamos, Michael I.; Hoey, Dan (1976), "Geometric intersection problems", Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76), pp. 208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.
↑ Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm (PDF).
↑ Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG].

[1] Shamos, Michael I.; Hoey, Dan (1976), "Geometric intersection problems", Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76), pp. 208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.

[2] Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm (PDF).

[3] Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG].

[1]

[2]

[3]