[4] geom comp1

Geometrie computationala I

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

PA 2014/2015

D. Lucanu (FII - UAIC) Geometrie computationala PA 2014/2015 1 / 46

Outline

1 IntroducereMotivatieCunoasterea domeniului problemeiOperatii primitive

2 Structura DCEL

3 Localizarea unui punct


Introducere

Plan


2 Structura DCEL



Introducere Motivatie

Plan


2 Structura DCEL




Ce este geometria computationala

Obiectele geometrice - punctele, liniile, poligoanele, etc. - constituie bazamultor aplicatii si conduc la multe probleme si algoritmi interesanti.Disciplina a fost numita n jurul anului 1975, cand teza de doctorat a luiShamos a atras atentia multor cercetatori.In centrul acestei discipline sta o serie de tehnici de proiectare si de analizaa algoritmilor. Acesti algoritmi opereaza cu sau sunt ghidati de o serie destructuri de date caracteristice geometriei computationale. Acestea includaranjamente de obiecte geometrice, localizari, nfasuratoarea convexa,diagrame Voronoi, triangularizari.Scopul urmatoarelor doua lectii este de a face o scurta introducere nalgoritmica din acest domeniu.Putem vedea aceste lectii ca un studiu de caz de algoritmica specifica unuidomeniu (Domain Specific Algorithms).Vom considera numai obiecte din geometria plana.



Aplicatii

grafica (computer vision, reconstruirea de imagini)

robotica (miscare n plan, vizibilitate)

proiectare aistata de calculator (CAD)

siteme informatice geografice (GIS)

statistica


Introducere Cunoasterea domeniului problemei

Plan


2 Structura DCEL




Puncte

Un punct p poate fi reprezentat prin coordonate carteziene, P = (x , y), saucoordonate polare, P = (, ).

p=(x,y) y

x

p=(, )

Conversii (partial):(x , y) 7 (

x2 + y2, atan(y/x)) (x 6= 0)

(, ) 7 ( cos(), sin())


TeaHighlight


Tipuri de date pentru puncte

structuri

Coordonate carteziene:

P |-> {x |-> 4, y |-> 3}

P 7 vP , vP CPointCPoint = Strx : Float, y : Float = {{x 7 vx y 7 vy} | vx , vy Float}}

Coordonate polare:

P |-> {rho |-> 5, theta |-> 0.643501109}

P 7 vP , vP PPointPPoint = Strrho : Float, theta : Float = {{rho 7 theta 7 } |, Float}}



Segmente

Un segment este reprezentat de o pereche de puncte:{A |-> {x |-> 1, y |-> 2} B |-> {x |-> 4, y |-> 3}}

Accesarea coordonatelor: A.x A.y B.x B.y . . .

1 4

2 3

Nu considera (nca) o structura de date distincta pentru segmente.



Linii poligonale

Structura de date: lista liniare de punctePot fi:

simple

nchise/deschise

linie poligonala simpla

linie poligonala simpla inchisa

linie poligonala inchisa

linie poligonala



Structuri de date pentru linii poligonale

liste liniare

PoligLine = LLinCPoint sau PoligLine = LLinPPointCrearea unei liste cu punctele:

A = { x |-> 3 y |-> 5 };

B = { x |-> 2 y |-> 1 };

C = { x |-> 0 y |-> 0 };

se poate face prinL = empty();

L.insert(0, A);

L.insert(1, B);

L.insert(2, C);

sau

L = empty();

L[0] = A;

L[1] = B;

L[2] = C;

Reamintim ca pentru listele liniare L[i] este aceeasi cu L.lookup(i) si

L[i] = x este aceeasi cu L.insert(i , x)



Dreapta

O dreapta este reprezentata printr-o ecuatie liniara: a x + b y + c = 0

Structura de date: structuraLine = Stra : Float, b : Float, c : Float

Exemplu: dreapta 3x + 4y + 2 = 0 este reprezentata de structurad |-> {a |-> 3 b |-> 4 c |-> 2}



Dreapta care trece prin doua puncte distincte P si Q

Se rezolva sistemul:

{d.a P.x + d.b P.y + d.c = 0d.a Q.x + d.b Q.y + d.c = 0

Exercitiu: Sa se scrie un algoritm care determina dreapta ce trece prindoua puncte distincte P si Q. Dovediti corectitudinea algoritmului.


Introducere Operatii primitive

Plan


2 Structura DCEL




Pozitionarea unui punct fata de o dreapta

Fie P un punct si d o dreapta. Relativ la d , P se poate afla:

ntr-un semiplan: d.a * P.x + d.b * P.y + c > 0

pe dreapta: d.a * P.x + d.b * P.y + c = 0

pe celalalt semiplan: d.a * P.x + d.b * P.y + c < 0

Notam cu (d ,P) semiplanul determinat de dreapta d si punctul P.

Pozitionarea fata de un segment AB:

se determina dreapta suport

daca se afla pe dreapta, se verifica daca este ntre A si B

Se poate testa si n ordine inversa.

Timp uniform: O(1)



Intersectia a doua drepte (cand exista){a1 x + b1 y + c1 = 0a2 x + b2 y + c2 = 0

d =

a1 b1a2 b2 dx = c1 b1c2 b2

dy = a1 c1a2 c2

d = 0, drepte paralele

d 6= 0, sistemul are solutie unica: x = dxd, y =

dyd

In notatia structurilor de date pentru drepte:

d =

d1.a d1.bd2.a d2.b = d1.a d2.b d1.b d2.a

Timp uniform: O(1)

Exercitiu: Sa se scrie n Alk un algoritm care are la intrare doua drepte sifurnizeaza la iesire punctul de interesectie al dreptelor (cand exista).



Intersectia a doua segmente (cand exista)

Solutia 1:

se determina punctul P de intersectie a dreptelor suport

se verifica daca P apartine segmentelor

Solutia 2 (sweep line):

se baleiaza (matura) planul cu o dreapta orizontala (sau verticala) sise analizeaza pozitiile punctelor eveniment (detalii pe tabla)

un punct eveniment este dat de intersectia dintre dreapta care maturaplanul si un capat al unui segment

Timp uniform: O(1)Exercitiu: Sa se scrie algoritmi care stermina interesectia a doua segmente(cand exista) prin cele doua metode. Sa se arate corectitudinea fiecaruialgoritm.



Orientarea a trei puncte (primitiva ccw)

CCW = Counter-Clock-Wise (sensul invers arcelor de ceasornic)

Fie A,B,C trei puncte.

ccw(A, B, C) =

A.x A.y 1B.x B.y 1C.x C.y 1

ccw(A, B, C) > 0 : A, B, C formeaza un ciclu n sens invers arcelor deceasornic

ccw(A, B, C) < 0 : A, B, C formeaza un ciclu n sensul arcelor deceasornic

ccw(A, B, C) = 0 : A, B, C sunt coliniare

Timp uniform: O(1)

Exercitiu: Sa se scrie un algoritm n Alk care calculeaza ccw(A, B, C).



Localizarea unui punct fata de un triunghi

C

A B P

ccw(A, P, B), ccw(B, P, C) si ccw(C, P, A) au toate acelasi semn.

C

A B

P

ccw(A, P, B), ccw(B, P, C) si ccw(C, P, A) NU au toate acelasisemn.

Timp uniform: O(1)D. Lucanu (FII - UAIC) Geometrie computationala PA 2014/2015 20 / 46


Unghiul format de trei puncte

C

A B

- distanta dintre doua puncte:dist(P, Q) =

(Q.x P.x) (Q.x P.x) + (Q.y P.y) (Q.y P.y)

- se aplica teorema cosinusului

a = dist(C, B);

b = dist(C, A);

c = dist(A,B);

theta = acos((a*a + b*b - c*c)/ 2*a*b);

Timp uniform: O(1) (Care e timpul pentru operatiile si acos()?)



Localizarea unui punct fata de o linie poligonala simplanchisa

Theorem (Jordan)

Orice curba simpla nchisa mparte planul n doua regini distincte:interiorul liniei (marginita) si exteriorul (nemarginita).

Instance: O linie poligonala simpla nchisa L si un punct P.Question: Apartine P interiorului lui L?

P



Localizarea unui punct fata de o linie poligonala simplanchisa

Theorem (Jordan)

Orice curba simpla nchisa mparte planul n doua regini distincte:interiorul liniei (marginita) si exteriorul (nemarginita).

Instance: O linie poligonala simpla nchisa L si un punct P.Question: Apartine P interiorului lui L?

P

numar de intesectii impar interior,numar de intesectii parexterior



Localizarea unui punct fata de o linie poligonala simplanchisaNumaratul intersectiilor trebuie facut cu atentie deoarece sunt cazuri deexceptie:

P nu se numara

nu se numara

se numara o singura data

Calculul unei intersectii: O(1)Determinarea numarului de intersectii: O(n), n numarul de segmente aleliniei LExercitiu: Sa se scrie n Alk algoritmul care determina localizarea unui punct fatade o linie poligonala simpla nchisa. Sa se arate ca algoritmul este corect si sa severifice ca timpul de executie este O(n).


Structura DCEL

Plan


2 Structura DCEL



Structura DCEL

Planar Straight Line Graph (PSLG)

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5


Structura DCEL

Planar Straight Line Graph (PSLG)

un graf planar este un graf care poate fi scufundat n plan astfel ncatvarfurile sunt puncte din plan iar muchiile sun curbe n plan care nuse intersecteaza

orice graf planar admite o scufundare n plan n care muchiile suntsegmente (Fary, 1948)

un PSLG este graf conex planar scufundat n plan, n care muchiilesunt segmente


Structura DCEL

Structura DCEL: ideea

P4

P3

P2

F4

F3

P0

G = o lista de structuri; fiecare element a tabloului descrie o muchie

G[i1] == { V1 |-> 2 V2 |-> 4 F1 |-> 3 F2 |-> 4 Ptr1 |-> i2 Ptr2 |-> i3 }...G[i2] == { V1 |-> 3 V2 |-> 2 F1 |-> 3 F2 |-> ... Ptr1 |-> ... Ptr2 |-> ... }...G[i3] == { V1 |-> 4 V2 |-> 0 F1 |-> ... F2 |-> 4 Ptr1 |-> ... Ptr2 |-> ... }

Echivalent: G[i1].V1 == 2, G[i1].V2 == 4, G[i1].F1 == 3, G[i1].F2 == 4 . . .


Structura DCEL

Structura DCEL: descriere

DCEL = Double Connected Edge List

fiecare nod al structurii DCEL este memorat ntr-o componenta atabloului

exista o corespondenta 1-1 ntre muchiile PSLGului si elementele listei

V1 - primul varf al muchiei, V2 al doilea varf al muchiei

F1 - regiunea din stanga muchiei, F2 regiunea din dreapta muchiei

Ptr1 - adresa primului nod (muchie) ntalnit mergand n sensul CCWdin V1,

Ptr2 - adresa primului nod (muchie) ntalnit mergand n sensul CCWdin V2 (n ambele cazuri se pleaca de pe muchia curenta V1 V2 de laV1 la V2)


Structura DCEL

Structura DCEL: parcurgerea frontierei unei regiuni

Data o regiune F , sa se descrie care parcurge muchiile care marginesc F .

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5


Structura DCEL

Structura DCEL: parcurgerea frontierei unei regiuni (cont.)

Cazul particular pentru F = F5:

1 se determina o muchie i1 care este pe frontiera lui F5, sa zicem P5P6(G [i1].V 1 == 5,G [i1].V 2 == 6,G [i1].F1 == 5)

2 urmatoarea muchie i2 a lui F5 este va gasita parcurgand muchiile din P5CCW, plecand de pe P5P6, adica i2 = G [i1].Ptr1

3 avem G [i2].V 1 == 5,G [i2].V 2 == 0,G [i2].F1 == 5 (P5P0)

4 procedam n acelasi modi3 = G [i2].Ptr1; avem G [i3].V 1 == 0,G [i3].V 2 == 8,G [i3].F1 == 5 (P0P8)i4 = G [i3].Ptr1; avem G [i4].V 1 == 8,G [i4].V 2 == 6,G [i1].F1 == 5 (P8P6)

5 pana cand ntalnim din nou i1, adica G [i4].Ptr1 == i1

6 cele 4 muchii sunt date de elementele de pe pozitiile i1, i2, i3, i4


Structura DCEL


Gasirea unei muchii de pe frontiera regiunii Ff :

i = 0;

while (G[i].F1 != f and G[i].F2 != f)

i = i + 1;

Daca f este valida, atunci bucla while se termina. Dupa executia luiwhile, are loc G[i].F1 == f sau G[i].F2 == f.Are importanta pe ce parte se afla regunea f ?Raspuns: Da. (De ce?)


Structura DCEL


f

f

stanga dreapta

Tot timpul trebuie ramas n regiunea f .


Structura DCEL


Gasirea clorlalte muchii de pe frontiera regiunii Ff (le memoram n tablouledgesOf [f ]):

j = -1; i1 = i;

do {

j = j + 1;

edgesOf[f][j] = i;

if (G[i].F1 == f) // stanga

i = G[i].Ptr1;

else // dreapta

i = G[i].Ptr2

} until (terminat )

// j == numarul de muchii de pe frontiera lui f

Care e conditia de terminare?


Structura DCEL


Un posibil candidat pentru terminare: i == i1 (s-a ajuns n muchia dincare s-a plecat)

E corect? Exista cazuri cand prima muchie poate fi vizitata de doua ori?


Structura DCEL


f

f i1

f este regiunea exterioara.

Conditia de terminare corecta: s-a ajuns n muchia din care s-a plecat princapatul opus.leaveI1 = capatul prin care se pleaca din i1reachI = capatul prin care se ajunge n iConditia de terminare: i == i1 and reachI != leaveI1


Structura DCEL


j = -1; i1 = i;

do {

j = j + 1;

edgesOf[f][j] = i;

iprec = i;

if (G[i].F1 == f) { // stanga

i = G[i].Ptr1;

if (iprec == i1) leaveI1 = 1; // nu e foarte efficient!

}

else { // dreapta

i = G[i].Ptr2

if (iprec == i1) leaveI1 = 2;

}

if (G[i].V1 == G[iprec].V1 || G[i].V1 == G[iprec].V2) reachI = 1;

else reachI = 2;

} until (i == i1 and reachI != leaveI1)

Timpul n cazul cel mai nefavorabil: O(n), unde n este numarul de muchii.D. Lucanu (FII - UAIC) Geometrie computationala PA 2014/2015 36 / 46

Structura DCEL

Structura DCEL: parcurgerea tuturor regiunilor

Se utilizeaza o coada toBeVisisted, initial vida.Se pleaca dintr-o muchie de pe frontiera PSGului (una din fete esteregiunea nemarginita). Presupunem ca aceasta este P7P8. Se viziteazafata marginita, F6 si se parcurge frontiera sa pentru a adauga fetele vecineneprocesate n toBeVisisted (care devine egala cu [F5]).

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5

in coada

vizitat

F6

F5


Structura DCEL

Structura DCEL: parcurgerea tuturor regiunilor (cont.)

Se continua pe frontiera regiunii nemarginite pana se ntalneste o regiunenevizitata sau care nu e n toBeVisisted, F0. Se viziteaza fata marginita,F0, apoi se parcurge frontiera sa pentru a adauga fetele vecine neprocesaten toBeVisisted (care devine egala cu [F5,F4]).

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5

in coada

vizitat

F6

F5

F0

F4


Structura DCEL


Se continua pe frontiera regiunii nemarginite pana se ntalneste o regiunenevizitata sau care nu e n toBeVisisted, F3. Se viziteaza fata marginita,F3, apoi se parcurge frontiera sa pentru a adauga fetele vecine neprocesaten toBeVisisted (deoarece nu exista astfel de rgiuni, toBeVisistedramane neschimbata, [F5,F4]).

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5

in coada

vizitat

F6

F5

F0

F4

F3


Structura DCEL


Se continua pe frontiera regiunii nemarginite pana se ntalneste o regiunenevizitata sau care nu e n toBeVisisted, F2. Se viziteaza fata marginita,F0 si se parcurge frontiera sa pentru a adauga fetele vecine neprocesate ntoBeVisisted (care devine egala cu [F5,F4,F2]).

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5

in coada

vizitat

F6

F5

F0

F4

F3 F2

F1


Structura DCEL


Se continua pe frontiera regiunii nemarginite pana se ntalneste o regiunenevizitata sau care nu e n toBeVisisted. Deoarece nu mai exista, seconitinua cu vizitarea fetelor din toBeVisisted (egala cu [F5,F4,F2]).Pentru fiecare fata vizitata, se parcurge frontiera sa pentru a adauga fetelevecine neprocesate n toBeVisisted (daca e cazul).

P1

P0

P8

P7

P6 P5 P4

P3

P2

F1

F2 F4

F3

F0 F6

F5

in coada

vizitat

F6

F5

F0

F4

F3 F2

F1


Structura DCEL


Sa se descrie algoritmul de parcurgere a tuturor regiunilor n limbajalgoritmic. Sa se arate ca este corect si ca are timpul de executie O(n),unde n este timpul de executie.


Localizarea unui punct

Plan


2 Structura DCEL




Localizarea unui punct fata de un PSLG

Input: Un PSLG G si un punct P.Output: Regiunea la care apartine P.

P




banda (slab) P




1 Preprocesare1 sorteaza benzile n ordine crescatoare dupa y2 sorteaza segmentele de pe o banda n ordine crescatoare dupa x

Observatie: trapezele de pe o banda pot degenera si n triunghiuri

2 Procesare1 cauta binar banda pe care apare P2 cauta binar trapezul la care partine P pe banda gasita la punctul

anterior.

Timp:preprocesare: O(n2 log n) (pot fi n2 segmente pe o banda n cazul cel mainefavorabil - exemplu pe tabla)procesare: O(log n)Preprocesarea se poate reduce la O(n2) printr-o tehnica de sweep plane.Exercitiu: scrierea n limbajul Alk al algoritmului


IntroducereMotivatieCunoasterea domeniului problemeiOperatii primitive

Structura DCELLocalizarea unui punct

[4] geom comp1

Documents