Algoritmica geometrica

CAPITOLUL I. INTRODUCERE ÎN ALGORITMICAGEOMETRICĂ ...................................................................................... 91.1 CE ESTE ALGORITMICA GEOMETRICĂ? .............................................. 91.2 LIMITELE GEOMETRIEI COMPUTAŢIONALE ...................................... 111.3 EXEMPLE TIPICE DE PROBLEME ALE GEOMETRIEI COMPUTAŢIONALE 131.4 TEME LABORATOR/SEMINAR ......................................................... 15CAPITOLUL II. GRAFICA ÎN LIMBAJULUI C ............................... 162.1 CONFIGURAREA MODULUI GRAFIC ÎN DEV C++ ............................... 162.2 FUNCŢIILE MODULUI GRAFIC ÎN DEV C++ ....................................... 222.2.1. Iniţializarea ecranului grafic în Dev C++ ............................. 222.2.2. Culorile modului grafic în Dev C++ ..................................... 232.2.3. Coordonate-ecran ale pixelilor în Dev C++ ......................... 252.2.4. Funcţiile elementare de desenare .......................................... 272.2.5. Ecran virtual si ecran grafic ................................................. 302.3 TEME LABORATOR/SEMINAR ......................................................... 33CAPITOLUL III. NOŢIUNI GEOMETRICE ELEMENTARE ......... 343.1 PUNCTE ŞI VECTORI ....................................................................... 343.2 GEOMETRIE AFINĂ ŞI EUCLIDIANĂ .................................................. 373.2.1 Operaţii afine cu puncte, vectori şi scalari ............................. 373.2.2. Produsul scalar .................................................................... 393.3 DREPTE ŞI CERCURI ÎN PLAN ........................................................... 403.4 REPREZENTAREA SPAŢIULUI 3D ..................................................... 423.4.1 Sistemul obiect şi observator ................................................. 423.4.2 Sisteme de coordonate 3D ..................................................... 433.5 DREPTE, PLANURI ŞI SFERE ÎN SPAŢIU ............................................. 45 3.6. REPREZENTAREA SPAŢIULUI 3D PE ECRAN ..................................... 463.7. TEME DE LABORATOR ................................................................... 49CAPITOLUL IV. TRANSFORMĂRI GEOMETRICE....................... 514.1 TRANSFORMĂRI GEOMETRICE ELEMENTARE ÎN PLAN ....................... 514.1.1 Translaţia.............................................................................. 524.1.2 Scalarea ................................................................................ 524.1.3 Simetria ................................................................................ 534.1.4 Rotaţia .................................................................................. 54 4.2 TRANSFORMĂRI GEOMETRICE ELEMENTARE ÎN SPAŢIU .................... 554.2.1 Translaţia.............................................................................. 554.2.2 Scalarea ................................................................................ 564.2.3 Rotaţia .................................................................................. 574.2.4 Concatenarea şi transformarea inversă ................................. 584.3. TRANSFORMAREA DE PERSPECTIVĂ ............................................... 603.7. MODELUL CAMEREI DE LUAT VEDERI............................................. 644.4. TEME DE LABORATOR ................................................................... 66CAPITOLUL V. ALGORITMI ELEMENTARI DE GEOMETRIECOMPUTAŢIONALĂ .......................................................................... 715.1 PUNCTE, LINII ŞI POLIGOANE .......................................................... 715.2 ORIENTAREA TRIUNGIURILOR ŞI TESTUL DE COLINIARITATE ............ 745.2.1 Orientarea punctelor ............................................................. 745.2.2 Suprafeţe şi unghiuri ............................................................. 765.3 INTERSECŢII PROPRII ŞI IMPROPRII DE SEGMENTE ............................. 775.4 PROBLEMA DRUMULUI SIMPLU ÎNCHIS ............................................ 805.5 APARTENENŢA LA INTERIORUL UNUI POLIGON ................................ 825.6. TEME DE LABORATOR ................................................................... 86CAPITOLUL VI. PROBLEME DE INTERSECŢII ............................ 936.1. INTERSECŢII GEOMETRICE ............................................................. 936.2. INTERSECŢII DE SEGMENTE DE DREAPTĂ ........................................ 946.2.1 Intersecţia brută a segmentelor de dreaptǎ ............................ 956.2.2 Linii orizontale si verticale .................................................... 966.2.3 Intersecţii de segmente arbitrare............................................ 996.3. TEME DE LABORATOR ................................................................. 100 CAPITOLUL VII. ÎNFĂŞURĂTOAREA CONVEXĂ ...................... 1057.1 PROBLEMA DETERMINĂRII ACOPERIRII CONVEXE ŞI ALGORITMUL NAIV........................................................................................................ 1057.2 METODA ÎMPACHETĂRII (WRAPPING) ........................................... 1087.3 SCANAREA GRAHAM ................................................................... 1137.4 METODA RAPIDĂ PRIN SELECŢIE (QUICKHULL) ............................. 1197.5. TEME DE LABORATOR ................................................................. 121CAPITOLUL VII. SUBDOMENII ALE UNUI POLIGON ............... 1278.1. PROBLEMA NUCLEULUI ............................................................... 1278.2. TRIANGULAREA POLIGOANELOR.................................................. 1308.2.1 Triangularea poligoanelor convexe ..................................... 1328.2.2 Triangularea poligoanelor simple arbitrare ......................... 135 8.3. TEME DE LABORATOR ................................................................. 140CAPITOLUL IX. DIAGRAME VORONOI ŞI TRIANGULĂRIDELAUNAY ....................................................................................... 1419.1. PROBLEMA DIAGRAMELOR VORONOI........................................... 1419.2. CONSTRUCŢIA ALGORITMICĂ A DIAGRAMELOR VORONOI ............. 1439.3. TRIANGULAREA DELAUNAY A UNUI ANSAMBLU DE PUNCTE ......... 1449.4. ALGORITM DE DETERMINARE A TRIANGULĂRII DELAUNAY ŞI ADIAGRAMEI VORONOI ........................................................................ 1469.6. TEME DE LABORATOR ................................................................. 152CAPITOLUL X. PROBLEMA CELUI MAI SCURT DRUM ÎNTR-UNCÂMP CU OBSTACOLE ŞI GRAFUL DE VIZIBILITATE ........... 15410.1. PROBLEMA CELUI MAI SCURT DRUM ÎNTR-UN CÂMP CU OBSTACOLE........................................................................................................ 15410.2. GRAFUL DE VIZIBILITATE .......................................................... 15510.3. TEMĂ DE LABORATOR ............................................................... 159