Introducere în Geometria computationalã
si Graficã pe calculator
FISA DISCIPLINEI

Anul universitar 2008- 2009



  Departament Home

Cod: I1205
Titular curs: conf. univ. dr.  Boldea Costin
Forma de invatamant: lunga
Ciclul: 1; Anul I, semestrul 2 , Curs: 2x14h, Laborator: 2x14h
Nr. credite: 5
Profil: informatica
Specializare: informatica
Tip disciplina: obligatorie
Categoria formativa: de specialitate
Obiective:

Curs: Însusirea de catre studenti a principalelor notiuni de baza de geometrie utilizate pentru reprezentarile grafive, precum si si tehnici specifice geometriei computationale . Se urmareste ca studentii sa poata aplica cele învatate la cursuri speciale de grafica pe calculator, în aplicatii practice din domeniul graficii pe calculator, geodezie, robotica.


Laborator: Implementarea algoritmilor prezentati la curs, realizarea unor biblioteci de functii pentru rezolvarea problemelor de geometrie computationala, pentru calcul matriceal necesare transformarilor geometrice.

 

Descrierea temelor de curs, laborator si proiect.

Curs 1: Introducere în geometria computationala
• Ce este geometria comutationala.
• Tipuri de probleme în geometria comutationala.
• Domenii de aplicare.
Laborator
• Biblioteca grafica în C (I) . Reprezentari grafice de puncte, segmente de dreapta, cercuri

Curs 2: Fundamente geometrice ale geometriei computationale
• Spatiu afin.
• Spatiu euclidian.
• Repere ortonormate
• Transformari geometrice 2D si 3D
Laborator
• Biblioteca grafica în C (II). Reprezentari de puncte si segmente într-un reper 2D si 3D

Curs 3: Primitive grafice
• Esantionarea si cuantizarea
• Relatii de baza între pixeli.
• Vecini, conectivitate si masurarea distantei între pixeli
• Generarea primitivelor grafice in spatiul discret
Laborator
• Transformari geometrice în plan si spatiu
• Aria unui poligon.

Curs 4: Reprezentari grafice I
• Reprezentari grafice de curbe 2D explicite si parametrice.
Laborator
• Aplicatii de la curs, reprezentari grafice de curbe.

Curs 5: Reprezentari grafice II
• Reprezentari grafice de curbe 3D parametrice.
Laborator
• Aplicatii de la curs, reprezentari grafice de curbe.


Curs 6: Reprezentari grafice III
• Reprezentari grafice de suprafete date prin ecuatii explicite sau parametrice .
Laborator
• Aplicatii de la curs, reprezentari grafice de suprafete.

Curs 7: Algoritmi elementari de geometrie computationala I
• Puncte, linii si poligoane
• Orientarea triungiurilor si testul de coliniaritate
• Orientarea punctelor
• Suprafete si unghiuri
• Intersectii de segmente
Laborator
• Test de locatie a unui punct în interiorul unui triunghi
• Test de verificare a convexitatii unui poligon.
• Intersectia a doua segmente.

Curs 8: Algoritmi elementari de geometrie computationala II. Înfasuratoarea convexa
• Problema drumului simplu închis
• Incluziune într-un poligon
• Definitii acoperiri convexe si înfasuratoare. Proprietati. Puncte extreme.
• Algoritmul “naiv” de determinare a înfasuratorii convexe
Laborator
• Problema drumului simplu închis
• Incluziune într-un poligon
• Algoritmul “naiv” de determinarea a înfasuratorii convexe

Curs 9: Înfasuratori convexe în plan II
• Algoritmul lui Jarvis de împachetare
• Algoritmul lui Graham..
• Algoritmul Quick Hull.
Laborator
• Algoritmul lui Jarvis
• Algoritmul Quick Hull.
• Algoritmul lui Graham.

Curs 10: Problema celor mai apropiate puncte si a diametrului unei multimi de puncte
• Algoritmul Divide et impera de determinare a celei mai apropiate perechi de puncte.
Laborator
• Algoritmul Divide et impera de determinare a celei mai apropiate perechi de puncte.
• Diametrul unei multimi de puncte. Proiect 5-8 puncte.

Curs 11: Intersectii de segmente
• Intersectii de segmente. Algoritmul de numarare al intersectiilor
• Geometria Manhattan
Laborator
• Implementarea algoritmilor de la curs

Curs12: Triangularea unui poligon
• Triagulare prin metoda eliminarii urechilor.
• Problema galeriei de arta.
Laborator
• Triagulare prin metoda eliminarii urechilor. Proiect 8 puncte.
• Colorarea grafului asociat unei triangulari. Proiect 10 puncte.
• Problema galeriei de arta. Proiect 12 puncte.

Curs 13: Diagrame Voronoi
• Definitii si proprietati.
• Algoritmul lui Fortune.
• Aplicatii ale diagramelor Voronoi.
Laborator
• Algoritmul lui Fortune.

Curs 14: Triangulari Delaunay
• Definitii si proprietati.
• Dualitatea diagrama Voronoi - triangulare Delaunay.
• Aplicatii.
Laborator
• Test de laborator

Alte teme de proiecte:
• Graf de vizibilitate. Algoritmul lui Dijkstra.
• Deplasarea unui robot printre obtacole in plan.
• Adunarea Minkowski.
• Aplicatii ale diagramelor Voronoi.
• Triangularea Delaunay a unei multimi finite de puncte.
• Aplicatii ale triangularii Delaunay.
• Intersectii de poligoane convexe

Discipline anterioare obligatorii:
  • Programare Procedurală (I1104)
Discipline anterioare recomandate:
  • Tehnologii Java (I2402)
     
Forma de evaluare: examen.
  • Evaluarea finala se va efectua printr-o proba scrisa (examen), si o proba de laborator sau un proiect depus la sfârsitul semestrului, la alegere.

 

Bibliografie:

1. D. M. Mount - CMSC 754 Computational Geometry, Spring 2002, http://www.cs.umd.edu/class/fall2005/cmsc754/lectures.shtml.
2. Costin Boldea - Elemente de geometrie computationala si grafica pe calculator, Editura Universiatria 2007
3. R. Sedgewick – Algorithms, Addison-Wesley Longman Publishing Co.,
4. D. Dogaru, Grafica pe calculator, EDP, Bucuresti, 1995.


Ultima actualizare: 15 decembrie 2002