Algoritmul liniei de măturare

Algoritmul liniei de măturare sau algoritmul de măturare plană  este o paradigmă algoritmică care utilizează o linie de măturare speculativă sau o suprafață de măturare pentru a rezolva diverse probleme din spațiul euclidian . Aceasta este una dintre tehnicile cheie în geometria computațională.

Ideea algoritmilor de acest tip este de a imagina o linie dreaptă imaginară (de obicei verticală) care se mișcă de-a lungul planului, oprindu-se în anumite puncte. Operațiile geometrice sunt limitate la obiecte geometrice care fie se intersectează, fie se învecinează cu linia de măturare, iar soluția completă este disponibilă atunci când linia trece prin toate obiectele.

Istorie

Această abordare poate fi urmărită până la algoritmii de scanare a liniilor în grafica computerizată , apoi această abordare a fost utilizată în algoritmii timpurii de aranjare a circuitelor integrate , în care descrierea geometrică a unui circuit integrat a fost realizată sub formă de paralele. benzi, deoarece descrierea completă nu încapea în memorie.

Aplicații

Aplicarea acestei abordări a condus la o descoperire în complexitatea computațională a algoritmilor geometrici atunci când Shamos și Howey au prezentat algoritmi pentru intersectarea segmentelor de linii în plan și, în special, au descris cum să combine abordarea liniei de scanare cu structuri eficiente de date ( arbori binari echilibrați ) face posibilă detectarea dacă există intersecții a N segmente în plan, cu complexitatea O [1] . Algoritmul Bentley-Ottmann strâns înrudit folosește tehnica liniei de măturare pentru a obține toate K intersecțiile dintre orice N segmente de linie dintr-un plan cu complexitate de timp și memorie [2] .

Din acel moment, această abordare a fost folosită pentru a dezvolta algoritmi eficienți pentru o serie de probleme, cum ar fi construcția unei diagrame Voronoi ( algoritmul Fortune ) și triangularea Delaunay sau operații booleene pe poligoane .

Generalizări și extensii

Balayage topologic este un tip de balayage plan care relaxează cerințele pentru ordinea punctelor procesate, ceea ce evită o sortare completă a punctelor și permite algoritmului liniei de măturare să funcționeze mai eficient.

Tehnica calibrelor rotativi pentru construirea algoritmilor geometrici poate fi interpretată și ca un fel de balayage în planul dual proiectiv — dualitatea proiectivă convertește panta unei linii din plan în coordonata x a unui punct din planul dual, astfel încât trecerea liniei să fie sortată după panta ei. Astfel, procesul algoritmului șubler rotativ este procesul dual de trecere prin puncte sortate după coordonatele lor x în algoritmul balayage plan.

Abordarea de măturare poate fi generalizată la dimensiuni mai mari.

Note

  1. ↑ Shamos și Hoey 1976 , p. 208–215.
  2. ↑ Souvaine, 2008 .

Literatură