Platformă de e-learning și curriculă e-contentpentru învățământul superior tehnic

Geometrie computationala

2. Preliminarii geometrice

Preliminarii geometrice

Spatiu Euclidean: Ed

• Spatiu de d-tupluri, p = (x1,…,xd), de numere reale xi

inR numite puncte, unde d este dimensiunea spatiului.

• Metrica: o functie m: Ed × Ed R cu 3 proprietati:

1. m(p,p) = 0 identitate2. m(p1,p2) = m(p2,p1) simetrie3. m(p1,p3) ≤ m(p1,p2) + m(p2,p3) inegalitatea

triunghiurilor• Metrica distantei: functie in Ed × Ed

R astfel incat

2

2112121 ))()((||||),( pxpxppppd ii

d

i

Primitive geometrice

• Punct: tuplurile p = (x1,…,xd) sunt definite in raport cu un sistem de axe cu aceeasi origine. Pot fi interpretate si ca vectori.

• Linie: o combinatie liniara de doua puncte distincte.

• Segment: o linie marginita

• Plan: o combinatie liniara de d puncte

• Varietate liniara: o multime V pentru care orice combinatieliniara de doua puncte din V apartine multimii V.

Rpp 21 )1(

]1,0[)1( 21 pp

11

)...1(... 11112211

dj

pppp

j

dddd

Multimi

• O multime de puncte S este conexa daca nu este reuniunea a doua multimi disjuncte nenule.

• Granita unei multimi S este o submultime a punctelor pentru care exista un punct vecin la distanta ε 0 ce nu se afla in S.

• Teorema lui Jordan: orice curba simpla inchisa (nu se intersecteaza cu ea insasi) partitioneaza planul in doua regiuni disjuncte. Exteriorul este nemarginit, iar interiorul este marginit.

exterior

interiorp1

p2

Multime convexa

• O multime S a lui Ed este convexa daca si numai daca pentru toate p1, p2 din S toate punctele din segmentul p1p2 sunt in S.

(convexa) (nu este convexa)

• Teorema: intersectia a doua multimi convexe este convexa.

p1

p2

p1

p2

p1

p2

Infasuratoare convexa

• Infasuratoarea convexa CH(P) a unui set de puncteP in Ed este cea mai mica multime convexa ce contine P.

Echivalent: intersectia tuturor multimilor convexe ce contin P.

• In plan, infasuratoarea convexa este marginita de segmente liniare. In spatiu este marginita de planuri.

CH(P)

P

Poligoane

• Definitie: un poligon este o regiune a unui plan, marginita de o colectie finita de segmente liniare (muchii) ce formeaza curbe simple inchise unde fiecare punct final de segment (varf) este impartit de exact doua muchii.

muchii mij= (vi,vj)

varfuri vi = (xi,yi)

granite

Complexitatea poligonului: numarul de varfuri

Poligon simplu: o singura curba inchisa:1. Nici o pereche de muchii neconsecutive nu impart un varf.

2. Muchiile neadiacente nu se intersecteaza.

Poligon convex: Nici o linie intre oricare doua varfuri nu este inafara poligonului.

Tipuri de poligoane

P

diagonale

Tipuri de poligoane

Poligon stelat: un poligon simplu P astfel incat exista un punct p in interiorul sau astfel incat toate liniile din p catreorice punct q in P se afla in interiorul lui P.

Poligon monoton: un poligon P este monoton de-a lungul unei linii L daca si numai daca proiectia varfurilor sale pelinie pastreaza o ordine data a punctelor.

p

1

2

3

4

56

7

Poliedre

• Fetele neadiacente nu se intersecteaza

• Fetele adiacente impart un punct sau un segment

• Poligoanele definesc o suprafata inchisa

fete

muchii

varfuri

Definitie :

O multime finita de poligoane (numite fete) in

spatiu astfel incat fiecare muchie a unui poligon

este impartita de exact doua poligoane.

Exemple de non-poliedre

Posibile arii de dezvoltare proiect

• Procesarea structurilor poligonale

▫ Reducerea/Simplificarea Mesh-urilor

▫ Generarea si simplificarea terenurilor

Posibile arii de dezvoltare proiect

• Vizualizarea structurilor N-Dimensionale

▫ Proiectii N => N-1, Transformari N-Dimensionale

▫ Hiper-Primitive grafice

Posibile arii de dezvoltare proiect

• Sistem de detectie a coliziunilor

▫ Detectie a coliziunilor volumelor de incadrare

▫ Structuri de incadrare ierarhice

▫ Detectie a coliziunilor componentelor

Posibile arii de dezvoltare proiect

• Sistem de simulare interactiuni fizice

Posibile arii de dezvoltare proiect

• Triangularizari Delaunay

Posibile arii de dezvoltare proiect

• Diagrame Voronoi

Posibile arii de dezvoltare proiect

• Curbe/Volume de Incadrare/Aproximare

▫ Variatii Alpha-Shape parametrizabile

▫ Constrangeri de ocolire/excludere

▫ “Infrumusetari” ale volumelor rezultate

Posibile arii de dezvoltare proiect

• Caracteristici geometrice pentru clasificare

Posibile arii de dezvoltare proiect

• Regiuni/Segmentare “Watershed”

Posibile arii de dezvoltare proiect

• Morfologie matematica