RAČUNSKA GEOMETRIJA

1 KAJ JE RAČUNSKA GEOMETRIJA

1.1 Determinističen in naključen pristop
1.2 Obravnavane teme
1.2.1 Mnogokotniki
1.2.2 Lupine
1.2.3 Vornoi diagrami
1.2.4 Ureditve
1.2.5 Iskanje točk in presečišč
1.2.6 Načrtovanje gibanja

2.1 Definicija mnogokotnika
2.2 Triangulacija
2.2.1 Obstoj izbočenega temena
2.2.2 Obstoj diagonale
2.2.3 Obstoj triangulacije in njene lastnosti
2.2.4 Dualnost triangulacije
2.3 Površina mnogokotnika
2.3.1 Vektorski produkt
2.3.2 Površina konveksnega mnogokotnika
2.3.3 Površina štiristranega konveksnega mnogokotnika
2.3.4 Površina štiristranega nekonveksnega mnogokotnika
2.3.5 Površina iz poljubnega centra
2.4 Izvedba triangulacije
2.4.1 Diagonala, notranja ali zunanja
2.4.2 Triangulacija z odstranjevanjem ušes
2.5 Razdeljevanje na trapeze
2.5.1 Razdeljevanje na trapeze s pregledovanjem ravnine
2.5.2 Inkrementalni algoritem razdeljevanja na trapeze
2.6 Razdeljevanje na konveksne površinske elemente
2.6.1 Optimalna konveksna razdelitev

3.1 Konveksne lupine v 2D
3.1.1 Algoritem za konstrukcijo lupine v 2D
3.1.2 Deterministični algoritem za konstrukcijo konveksne lupine v 2D
3.1.3 Naključni algoritem za konstrukcijo konveksne lupine v 2D
3.2 Konveksne lupine v 3D
3.2.1 Polieder
3.2.2 Inkrementalni algoritem za konstrukcijo konveksne lupine v 3D
3.2.3 Višje dimenzije

4.1 Definicija Vornoi diagrama
4.2 Delaunay-eva triangulacija
4.2.1 Odnos med Delaunay-evo triangulacijo in Vornoi diagramom
4.3 Konstrukcija Vornoi diagrama
4.3.1 Determinističen algoritem za konstrukcijo Vornoi diagrama
4.3.2 Inkrementalni algoritem za konstrukcijo Vornoi diagrama
4.4 Aplikacije povezane z Vornoi diagrami
4.4.1 Najbližji sosed
4.4.2 Maksimiziranje najmanjših kotov triangulacije
4.4.3 Največji prazen krog
4.4.4 Najmanjše razvejišče
4.4.5 Problem trgovskega potnika
4.5 Posplošitve Vornoi diagrama

5.1 Inkrementalni algoritem
5.2 Dualnost
5.3 Odstranjevanje nevidnih površin

6.1 Točka in mnogokotnik
6.1.1 Štetje presečišč
6.1.2 Metoda zavojnega števila
6.2 Skrajne točke konveksnega mnogokotnika
6.3 Iskanje presečišč dveh konveksnih mnogokotnikov
6.4 Skrajne točke konveksnega poliedra

7.1 Najkrajša pot
7.2 Premikanje konveksnega mnogokotnika
7.3 Gibanje veččlenkaste roke robota