Revizia anterioară Revizia următoare
Algoritmi de baleiere (sweeping)
(Categoria Geometrie, Autor Stefan Istrate)
- Continut
- Introducere
- Prezentarea metodei
- Baleiere verticala
- Baleiere rotationala
- Un alt algoritm pentru infasuratoarea convexa
- Aplicatii
- Bibliografie
Introducere
Sa presupunem ca vrem sa implementam un joc video in care personajul-jucator se poate plimba pe o harta planara cu obstacole (ziduri), iar in fiecare moment trebuie sa desenam pe ecran doar obstacolele pe care le vede acesta (chiar si partial). Mai precis, personajul reprezinta un punct, iar zidurile reprezinta segmente in plan. Ceea ce ne intereseaza sunt segmentele vizibile. Un punct este vizibil din alt punct daca segmentul ce le uneste nu intersecteaza niciun zid. Un zid este vizibil daca are cel putin un punct vizibil din pozitia jucatorului. Desigur, am putea alege cate 2 obstacole si trata toate cazurile care apar, dupa care sa pastram doar portiunile vizibile din cele 2 obstacole, dar aceasta abordare poate fi costisitoare uneori. Cel mai indicat ar fi sa gasim un mod eficient de "scanare" a planului prin care sa obtinem o lista de segmente vizibile.
Prezentarea metodei
Aceasta tehnica de "scanare" mentionata mai sus poarta numele de baleiere, sau sweeping (engl. sweeping = "maturare"). Exemplul de mai sus ilustreaza tocmai faptul ca tehnologiile si programele avansate din ziua de azi au la baza tehnici simple, dar nu lipsite de importanta. In majoritatea problemelor de geometrie vom intalni obiecte geometrice: puncte, drepte, segmente, figuri, corpuri. Avem nevoie sa stim sa le gestionam corect si sa extragem informatiile necesare in functie de situatia ivita.
Fie S o multime de obiecte in plan pentru care trebuie sa extragem anumite informatii si Q intrebarea la care trebuie sa raspundem. Abordarea intuitiva ar fi: alegem o dreapta (fie ea orizontala, verticala sau oblica) si o plimbam peste multimea de obiecte; in timpul baleierii ne asiguram ca sunt extrase toate informatiile referitoare la intrebarea Q; dupa ce am terminat scanarea, construim si afisam raspunsul pe baza informatiilor adunate. O descriere ceva mai explicita se poate vedea in imaginea de mai jos:
In timpul baleierii, la fiecare pas trebuie sa avem la dispozitie o structura de date continand toate obiectele intersectate de linia de baleiere. Pentru exemplul de mai sus, multimea de obiecte e traversata de sus in jos, iar la pasul curent sunt intersectate obiectele b, d, e, f. Continuand traversarea, vor urma, in ordine, eliminarea lui b din structura de date, eliminarea lui d, adaugarea lui g, etc. Dupa cum se observa, multimea obiectelor intersectate sufera destule modificari, ceea ce ne determina sa alegem o structura de date dinamica care sa ne confere eficienta. De cele mai multe ori, alegerea noastra va fi un arbore echilibrat.
