GEOMETRIA OBLICZENIOWA

Triangulacja Delaunay'a
Diagram Voronoi

Wykonali:
Czekaj Wiesław
Idus Tomasz
Bogacz Marcin

Diagramy Voronoi.

Opis wejsciowy: Zbiór S punktów P1,...,Pn .

Opis problemu: Dekompozycja przestrzeni na obszary wokół każdego punktu w taki sposób , że wszystkie punkty z rejonu okalajacego Pi sa bliżej niego niż jakiegokolwiek innego punktu ze zbioru S .

Wprowadzenie : Diagram Voronoi reprezentuje rejon wpływów wokół każdego z danych zbiorów położeń. Jeżeli te położenia reprezentuja soba lokalizację np. stacji benzynowej , to diagram Voronoi dokonuje rozdziału przestrzeni na komórki wokół każdej ze stacji . Dla każdej z osób mieszkajacych w pojedynczej komórce pojęcie stacja benzynowa okresla najbliższe miejsce , gdzie można zatankowac.

Diagram Voronoi ma zaskakujace możliwosci zastosowań:

Wyszukiwanie najbliższego sasiedztwa:dla rozważanego punktu q znalezienie jego najbliższego sasiedztwa,ze stałego zbioru punktów S jest po prostu kwestia okreslenia , która komórka diagramu Voronoi zbioru S zawiera q.
Funkcja położenia: załóżmy, że koncern chce otworzyć kolejna stacje .
Aby zminimalizować ingerencję w obszar istniejacej stacji , powinna być ona umiejscowiona najdalej jak się da od najbliższej istniejacej stacji . Umiejscowienie to jest zawsze na wierzchołku diagramu Voronoi i może być znalezione przez wyszukiwanie liniowo-czasowe poprzez wszystkie wierzchołki Voronoi.
Największe puste koło:załóżmy , że potrzebujesz dużego, nie zagospodarowanego kawałka ziemi na którym zbudujesz fabrykę . Ten sam warunek użyty do lokalizacji stacji jest własciwy dla wszystkich niepożadanych lokalizacji nazwany tak , ponieważ jest możliwie jak najdalej od jakiegokolwiek istotnego położenia zainteresowań.Wierzchołek Voronoi okresla srodek największego pustego koła pomiędzy punktami.
Planowanie scieżek:jeżeli położenia S sa srodkami przeszkód , których chcemy uniknac , to krawędzie diagramu Voronoi definiuja możliwe kanały , które minimalizuja odległosci do tych przeszkód . W ten sposób w planowaniu scieżek między położeniami będzie bezpiecznie przykleić ja do krawędzi diagramu Voronoi.
Triangulacja własciwosci: w triangulacji zbioru punktów często wymagamy ładnych , pokaznych trójkatów, które wykluczaja małe katy i chude trójkaty. Triangulacja Delanuay maxymalizuje minimalny kat dla całej triangulacji i jest własnie tym czego potrzebujemy . W dalszym ciagu jest łatwo konstruowana jako dualizm diagramu Voronoi.

Triangulacja

Wejscie :
Zbiór punktów lub wielobok .

Opis problemu :
Podział obszaru wyznaczanego przez zbiór punktów
lub wnętrza wieloboku na trójkaty .

Wprowadzenie :
Triangulacja jest podstawowym zagadnieniem w geometrii obliczeniowej , ponieważ pierwszym krokiem przy badaniu skomplikowanych obiektów geometrycznych jest rozbicie ich na prostsze obiekty geometryczne . Najprostszymi obiektami sa trójkaty w przestrzeni dwuwymiarowej i czworosciany w przestrzeni trójwymiarowej . Klasyczne zastosowanie triangulacji dotyczy analizy skończonej liczby elementów i wyznacza zbiór nie przecinajacych się przekatnych , które dziela wielokat na trójkaty .

Minimalna waga triangulacji :
Waga triangulacji to suma długosci tworzacych ja przekatnych . Jak pokazano na poniższych rysunkach :

Pierwsza triangulacja ___________________Druga triangulacja

każdy wielokat może posiadać wiele różnych rozwiazań triangulacji , dlatego podstawowym zadaniem jest znalezienie minimalnej wagi triangulacji .
Aby zastosowac programowanie dynamiczne , musimy znalezc sposób na podzielenie wielokata na mniejsze kawałki . Nasuwajacym sie pomysłem jest , aby rozpatrzyc wszystkie możliwe przekatne wielokata i wybrac te , które dziela go na dwa mniejsze zbliżone do siebie wielkoscia . Procedure te powtarzamy dla każdego z uzyskanych wielokatów do momentu podzielenia ich na trójkaty . Waga triangulacji dla n-punktów wynosi n do potegi 3.
Programowanie dynamiczne nie ma zastosowania , gdy we wnetrzu wielokara znajduja sie punkty , które także chcemy rozparzyc .Może byc zastosowane , jesli podzielimy rozpatrywany zbiór punktów na wielokaty bez punktów we wnetrzu każdego z nich , jednak waga triangulacji rosnie wówczas wykładniczo .
Praktycznie nie istnieje optymalny algorytm wyznaczania triangulacji zbioru punktów , nie znany jest także stopien trudnosci wyznaczenia takiego algorytmu . Minimalna waga triangulacji jest jednym z niewielu dobrze zbadanych zagadnien algorytmow , w którym pozostaje jeszcze wiele do zrobienia .

Triangulacja Delaunay'a
(5kB)

Triangulacja Delanuay'a zbioru punktów jest jednym z rodzajów triangulacji i charakteryzuje sie tym , że żaden z punktów z tego zbioru nie trafia do wnętrza okręgu opisanego na trójkacie jakiegokolwiek innego trójkata powstałego podczas triangulacji.

Algorytm tworzenia triangulacji Delaunay'a dla zbioru n punktów :
1. Wybierz 3 punkty tworzace pierwszy trójkat .
2. Wyznacz losowa permutacje pozostałych punktów .
3. Dla pozostałej liczby r punktów :
- znajdz trójkat Pi,Pj,Pk należacy do triangulacji Delaunay'a nie zawierajacy Pr ,
- jeżeli Pr leży wewnatrz trójkata , dokonaj podziału tego trójkata na trzy trójkaty oraz przeprowadz legalizacje powstałych trójkatów zgodnie z warunkiem dla triangulacji Delaunay'a podanym powyżej ,
- jeżeli Pr leży na krawedzi , to dokonaj podziału na dwa trójkaty i dokonaj odpowiedniej legalizacji .
4. Zwróc jako rozwiazanie triangulacje Delaunay'a .

Programy wizualizacji problemów opisanych w projekcie

(3kB)

VoroGlide służy do wyznaczania diagramów Voronoi lub triangulacji Delaunay'a zbioru punktów wprowadzanych za pomoca myszy .

VoroGlide umożliwia dodatkowo wykonanie animacji w formie krok po kroku przy zwiekszeniu struktury , przy triangulacji Delaunay'a , o kolejny punkt . Przedstawiaja poszczególne etapy optymalizacji struktury , zgodnie z zasada tworzenia triangulacji. W celu wykonania animacji należy wybrac zmenu górnego polecenia Options|Delaunay|Step Mode . Aby wprowadzic nowy zbiór punktów , należy uprzednio wyczyscic okno poleceniem Clear w opcji Edit menu górnego . Zakończenie działania programu nastepuje po wybraniu polecenia Close w opcji File menu górnego .

Poczekaj , aż przycisk VoroGlide uaktywni sie , wtedy kliknij na nim lewym przyciskiem myszy :

Sorry, this WWW browser does not seem to understand Java applets.

Użytkowanie wywołanego okna VoroGlide .
- Lewy przycisk myszy - zaznaczenie punktu.
- Prawy przycisk myszy (lub <Alt>) - skasowanie punktu .
- Przytrzymanie lewego przycisku na punkcie - umożliwia przesuwanie punktu .
- W menu Show wybierz struktury , w które maja byc przekształcane zaznaczane przez ciebie punkty .

Dodatkowo w pliku projekt umieszczony został program Dirichle umożliwiajacy wyznaczenie diagramów Voronoi dla wprowadzonego lub wybranego losowo zbioru punktów w zdefiniowanym przez użytkownika obszarze przy podanych granicach minimalnej i maksymalnej odległosci punktów . Program napisany został dla DOS , może być jednak wywołany i obsługiwany z systemu Windows .

Lokacje w Internecie :
http://www.netlib.org/toms/index.html
Zawiera przykładowe programy i opis problemów zwiazanych z triangulacja i wyznaczeniem diagramów Voronoi - pliki 624, 751, 772
http://www.mirror.ac.uh/sites/netlib.bell-labs.com/netlib/toms
Zawiera przykładowe programy i opis problemów zwiazanych z triangulacja - plik 624
http://www.netlib.org/voronoi
ZAwiera:przykładowe programy i opis dla problemu diagramów Voronoi.
http://www.magic-software.com/Zip Files.html
Zawiera:przykładowe programy w C++ i dokumenty w formacie 'pdf' dotyczace triangulacji i diagramów Voronoi.
ftp://menaik.cs.ualberta.ca/pub/geompack
Zawiera:przykładowe programy dotyczace triangulacji Delaunay'a i diagramów Voronoi w przestrzeni 2 i 3-wymiarowej.
http://www.cs.cmu.edu/~quake/triangle.html
Zawartosc: program do wyznaczenia triangulacj Delaunay'a w przestrzeni 2-wymiarowej
http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/delaunay.html/
Zawiera:zastosowania programu Q-hull do wyznaczania triangulacji Delaunay'a
http://www.cs.uu.nl/CGAL/ Ogólna baza dla G.O.

Zródła:

Ksiażki:
- Strona oparta została głównie na ksiażce - S.Skiena "The algorithm design manual"
- T.Cormen,R.Rivest "Wprowadzenie do algorytmów"
Aplikacja:
VoroGlid wersja 2.0 zrealizowana przez:
Christian Icking,Rolf Klein,Peter Kollner,Lihong Ma
email:javagroup@fernuni-hagen.de