h2(#baleiere_verticala). Baleiere verticala

Sa vedem acum o situatie mai concreta. Sa presupunem ca avem $N$ dreptunghiuri in primul cadran al unui plan, cu laturile paralele cu axele de coordonate, iar latura de jos fixata pe axa $OX$. Cum am putea afla aria reuniunii tuturor dreptunghiurilor? De data aceasta, nici macar o solutie naiva nu este multumitoare. Cel mai simplu lucru la care ma gandesc ar fi calcularea ariei folosind principiul includerii si excluderii: se aduna ariile tuturor dreptunghiurilor, se scad ariile comune cator 2 dreptunghiuri, se aduna ariile comune cator 3 dreptunghiuri, etc. Este evident ca aceasta abordare este total nerecomandata din cauza timpului de rulare exponential. Ei bine, solutia la aceasta problema se bazeaza pe o baleiere verticala in care linia de baleiere este plimbata de la stanga la dreapta peste obiecte.
Sa observam mai intai ca laturile verticale ale dreptunghiurilor, precum si latura de jos pot fi ignorate, pastrand doar latura de sus pentru fiecare dreptunghi. Aria figurii initiale este compusa din fasii verticale, fiecare fasie fiind delimitata in partea superioara de un segment (latura de sus a unui dreptunghi initial). Nu ne ramane de facut decat o parcurgere a fiecarei fasii si calcularea ariei acesteia.
 
!algoritmi-de-baleiere?fig2.jpg!
 
Sa analizam acum problema din perspectiva tehnicii pe care dorim sa o folosim. Evenimentele sunt, in acest caz, capetele stangi si cele drepte ale segmentelor orizontale. O alta observatie importanta este aceea ca, parcurgand o fasie cu linia de baleiere verticala, niciun segment nu este adaugat sau eliminat din multimea obiectelor intersectate.
Inainte de a parcurge lista de evenimente, o vom sorta crescator in functie de abscisele capetelor segmentelor orizontale. Apoi, la fiecare pas, vom procesa toate evenimentele cu aceeasi abscisa. In ce consta acest lucru? Mai intai interogam structura de date continand obiectele deja intersectate si il alegem pe cel cu ordonata maxima $Y$. Aria ultimei fasii din stanga liniei de baleiere poate fi calculata usor cu formula $Y * D$, unde $D$ este distanta pana la pozitia precedenta a liniei de baleiere. Apoi vom insera sau, dupa caz, vom sterge din structura de date evenimentele de la abscisa curenta. Asadar, vom avea nevoie de inserari, stergeri si interogari rapide. Putem alege un 'arbore de intervale':arbori-de-intervale (fiind necesara, inainte de toate, o normalizare a tuturor ordonatelor) sau un arbore binar de cautare in care ordonarea cheilor sa se faca dupa ordonata. Aveti, totusi, grija la duplicate: pot exista mai multe segmente orizontale cu aceeasi ordonata $Y$, ceea ce inseamna ca structura noastra de date trebuie sa gestioneze corect inserarea unei ordonate deja existente sau stergerea acesteia.
Sa vedem acum analiza complexitatii. Avem nevoie de un timp $O(N * log N)$ pentru sortarea listei de evenimente dupa abscisa, $O(log N)$ (sau chiar $O(1)$ la $set$-urile din STL) pentru alegerea obiectului cu ordonata maxima, $O(log N)$ pentru inserare si stergere in structura de date aleasa. Intrucat sunt $2*N$ evenimente (cate 2 capete pentru fiecare segment), complexitatea finala va fi $O(N * log N) + O(N) * (O(log N) + O(log N)) = O(N * log N)$.
Problema de fata poate fi generalizata pentru cazul in care dreptunghiurile nu au o latura fixata, ci sunt oarecare in plan. Pentru acest lucru, la fiecare eveniment va fi necesara o parcurgere integrala a multimii de obiecte intersectate de linia de baleiere, ceea ce conduce la un timp de executie patratic $O(N^2^)$. Lasam aceasta aplicatie ca un exercitiu pentru cititor.
 

h2(#baleiere_rotationala). Baleiere rotationala
h2(#infasuratoare_convexa). Un alt algoritm pentru infasuratoarea convexa