Introducere in CG

Report
Introducere in geometria
computationala
Universitatea “Politehnica” Bucuresti
Catedra de Calculatoare
conf. dr. ing. Costin-Anton BOIANGIU
[email protected]
Notare (1)
• [60%] Activitate in timpul semestrului
(laborator/proiect)
▫
▫
▫
▫
▫
[05%] Faza documentare si raport preliminar
[10%] Documentatie proiect
[50%] Implementare, optimizari, paralelizari
[05%] Validarea rezultatelor obtinute (scenarii de test)
[30%] Raport final, articol revista
• [10%] Activitate in timpul semestrului (curs)
▫ [50%] Prezenta
▫ [50%] Grad de participare la discutii in cadrul
prezentarilor colegilor
Notare (2)
• [10%] Prezentare in cadrul cursului
▫ [60%] Calitatea prezentarii si claritatea expunerii
▫ [40%] Calitatea cercetarii depuse in domeniul
prezentat si abilitatea de a raspunde intrebarilor
conexe
• [20%] Examen Final (cu orice fel de documentatie
scrisa pe masa) – o idee/abordare originala plus
algoritmul aferent pentru rezolvarea unei probleme
practice din cadrul ariilor definite de curs
▫ [50%] Descriere idee/abordare
▫ [25%] Demonstratie matematica
▫ [25%] Algoritm (pseudocod apropiat de un limbaj de
programare)
Criterii Promovare
Pentru promovare trebuie sa:
• Obtineti:
▫ 50% din punctajul din timpul anului
▫ 50% din punctajul final
• Sustineti o prezentare in fata colegilor, in cadrul
cursului, pe baza unei programari preliminare
Precizari Importante (1)
• Alegerea prezentarii:
▫ Deadline: 16 octombrie, ora 22:00, cerere pozitii pe site-ul
cursului si alocare in ordinea sosirii cererilor
▫ Se pot alege teme din cadrul articolelor upload-ate pe site sau
altceva in domeniul cursului, de comun acord
▫ Prezentarea va fi trimisa in fiecare luni de dinaintea cursului
pana la ora 22:00, pe e-mail-ul [email protected],ro,
urmand a fi postata pe site-ul de curs pentru a putea fi vizualizata
de toti cei interesati.
▫ Prezentarile din prima saptamana vor beneficia de un bonus de 1
punct, iar in cea de a doua de 0.5 puncte
• Alegerea proiectului
▫ Deadline: 16 octombrie, ora 22:00
▫ Pentru fiecare saptamana intarziere se scade 1 punct din nota de
proiect
Precizari Importante (2)
• Predarea proiectului (implementare)
▫ Pentru cei care nu echivaleaza examen: ultimul laborator
▫ Pentru cei care echivaleaza examen: preziua examenului
• Predarea proiectului (raport cercetare, articol
conferinta/revista)
▫ Pentru cei care nu echivaleaza examen: ultimul laborator
▫ Pentru cei care echivaleaza examen: preziua examenului
▫ Pentru predare inainte de termen se acorda bonus de 0.5
puncte pe saptamana in cadrul activitatii de
laborator/proiect
• Cei care sunt acceptati cu un articol la o
conferinta/revista importanta (necesita validare)
primesc 10 la aceasta materie!
Cuprins
•
•
•
•
Ce este geometria computationala (GC)?
Exemple de probleme in GC
GC in perspectiva
Preliminarii
▫ Concepte de baza in geometrie
▫ Poligoane: definitie si reprezentari
▫ Poliedre: definitie si reprezentari
Ce este geometria computationala?
Studiul algoritmilor ce servesc la rezolvarea problemelor
geometrice.
• Geometrie:
• O multime de primitive geometrice (puncte, linii,
curbe, plane, suprafete) definite in spatiul metric, de
obicei in plan (2D) sau in spatiu (3D).
• O multime de operatii geometrice (intersectie,
reuniune, descompunere) pe entitati geometrice.
• Algoritmi:
• Proceduri constructive ce calculeaza proprietati,
raspund la interogari sau construiesc entitati
geometrice.
Ce este geometria computationala?
• Complexitate:
• Analiza in scopul intelegerii a ce poate fi obtinut si cu
ce grad de dificultate.
• Tipuri de algoritmi:
• Combinatorici (topologici) – obiectele geometrice
sunt entitati discrete formate din puncte, linii,
poligoane etc.
• Numerici (modelare geometrica) – modelarea si
reprezentarea curbelor si suprafetelor
De ce geometria computationala?
Stiinta si teorie
▫ O continuare naturala a geometriei constructive si a
geometriei combinatorice din matematica
▫ Pastreaza o relatie cu probleme fundamentale in
matematica: programare liniara, geometrie analitica
Tehnologie si aplicatii
▫ Multe probleme cheie in Inginerie si Grafica
▫ Dezvoltarea de biblioteci ce contin algoritmi eficienti si
robusti
▫ Intelegerea problemelor specifice
▫ Mare importanta economica: Grafica, CAD/CAM, …
Exemple de probleme in GC
•
•
•
•
•
•
•
•
•
Cel mai apropiat vecin
Diagrame Voronoi
Triangularizari Delaunay
Localizarea unui punct
Punct in poligon
Cautari in spatii ortogonale
Cel mai scurt drum
Vizibilitate
…
Cel mai apropiat vecin
Definirea problemei
• Intrare: o multime de puncte (situri)
P in plan si un punct de interogare q.
• Iesire: Punctul pP cel mai apropiat
de q dintre toate punctele din P.
Variatii:
• Un set de puncte, interogari multiple
• Punct dinamic, set dinamic de puncte
• In 3D in loc de 2D
Aplicatii: telefonie mobila, localizare
p
q
P
Diagrame Voronoi
Definirea problemei
• Intrare: o multime de puncte (situri) P
in plan.
• Iesire: O subdiviziune planara S in
celule per sit. Celula ce corespunde lui
pP contine toate punctele de care p
este cel mai apropiat.
Variatii
• Set dinamic de puncte
Aplicatii: acoperirea unui sit, gasirea
celei mai bune locatii pentru un nou sit
S
P
Localizarea unui punct
Definirea problemei
• Intrare: O partitionare S a planului
in celule si un punct de interogare
p.
• Iesire: Celula C  S continand p.
Variatii
• O partitionare, interogari
multiple
Aplicatii: localizare
S
p
C
Punct in poligon
Definirea problemei
• Intrare: un poligon P in plan si un punct
de interogare p.
• Iesire: adevarat daca pP, fals in caz
contrar
Variatii
• Un poligon, interogari multiple
Aplicatii: localizarea unei regiuni
P
p
Cautari in spatii ortogonale
Definirea problemei
• Intrare: Un set de puncte P in plan si un
dreptunghi de interogare R
• Iesire:
 (raport) Submultimea Q  P continuta
in R.
 (masuratoare) Dimensiunea lui Q.
Variatii
• Un set de puncte, interogari multiple
• Spatial
Aplicatii: cautari geografice, baze de date
P
Q
R
Cel mai scurt drum
Definirea problemei
• Intrare: Locatii ale obstacolelor si
punctele de interogare s si t. (initial
si final)
• Iesire: cel mai scurt drum intre s si t
ce evita toate obstacolele.
s
Variatii
• Un set de obstacole, interogari multiple
• Puncte finale multiple, obstacole in
miscare
Aplicatii: rutare, robotica
t
Vizibilitate
Definirea problemei
• Intrare: un poligon P in plan si un
punct de interogare p.
• Iesire: Poligonul Q  P, vizibil lui p.
Variatii
• Un poligon, interogari multiple
• Poligoane multiple, 3D
Aplicatii: randare, securitate
P
Q
p
Alte aplicatii
Detectarea coliziunilor
Reprezentarea suprafetelor
Alte aplicatii
Planificarea miscarii
Invatarea automata
Alte aplicatii
Sisteme informatice
geografice
Dinamica computationala a
fluidelor
Preliminarii geometrice
Spatiu Euclidean: Ed
• Spatiu de d-tupluri, p = (x1,…,xd), de numere reale xi
in R numite puncte, unde d este dimensiunea
spatiului.
• Metrica: o functie m: Ed × Ed  R cu 3 proprietati:
1. m(p,p) = 0
identitate
2. m(p1,p2) = m(p2,p1)
simetrie
3. m(p1,p3) ≤ m(p1,p2) + m(p2,p3) inegalitatea
triunghiurilor
• Metrica distantei: functie in Ed × Ed  R astfel incat
d ( p1 , p2 ) || p1  p2 ||

d
i 1
( xi ( p1 )  xi ( p2 ))
2
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.
 p1  (1   ) p2
 R
 p1  (1   ) p2
  [0,1]
• Segment: o linie marginita
• Plan: o combinatie liniara de d puncte
1 p1   2 p2  ...   d 1 pd 1  (1  1 ...   d 1 ) pd
 j  1 j  d 1
• Varietate liniara: o multime V pentru care orice combinatie
liniara de doua puncte din V apartine multimii V.
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.
p1
p2
exterior
interior
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.
p1
p1
p2
p2
(convexa)
(nu este convexa)
• Teorema: intersectia a doua multimi convexe
este convexa.
p1
p2
Infasuratoare convexa
• Infasuratoarea convexa CH(P) a unui set de puncte
P in Ed este cea mai mica multime convexa ce
contine P.
P
CH(P)
Echivalent: intersectia tuturor multimilor convexe ce contin P.
• In plan, infasuratoarea convexa este marginita de
segmente liniare. In spatiu este marginita de
planuri.
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.
varfuri vi = (xi,yi)
muchii mij= (vi,vj)
granite
Complexitatea poligonului: numarul de varfuri
Tipuri de poligoane
Poligon simplu: o singura curba inchisa:
1.
2.
Nici o pereche de muchii neconsecutive nu impart un varf.
Muchiile neadiacente nu se intersecteaza.
P
Poligon convex: Nici o linie intre oricare doua
varfuri nu este inafara poligonului.
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 catre
orice punct q in P se afla in interiorul lui P.
p
Poligon monoton: un poligon P este monoton de-a lungul
unei linii L daca si numai daca proiectia varfurilor sale pe
linie pastreaza o ordine data a punctelor.
3
2
1
5
4
6
7
Poliedre
Definitie :
O multime finita de poligoane (numite fete) in
spatiu astfel incat fiecare muchie a unui poligon
este impartita de exact doua poligoane.
varfuri
• Fetele neadiacente nu se
intersecteaza
• Fetele adiacente impart un
punct sau un segment
• Poligoanele definesc o
suprafata inchisa
fete
muchii
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

similar documents