Main

Geometria Obliczeniowa

Projekt

Tomasz Cudek Marcin Paśko

Temat:

Triangulacja 2D z wykorzystaniem metody QuadTree

Co należy zrobić:

Należy zaimplementować algorytm konstrukcji triangulacji wielokąta na płaszczyźnie (z wstawianiem dodatkowych punktów wewnątrz wielokąta) oparty na strukturze QuadTree. Dla zadanego wielokąta na płaszczyźnie i podanego rozmiaru krawędzi triangulacji program powinien najpierw podzielić boki wielokąta na odcinki o zadanym rozmiarze, a następnie podzielić sam wielokąt na trójkąty możliwie najbliższe równobocznym. Program powinien w sposób graficzny prezentować etapy konstrukcji triangulacji, w szczególności postać struktury QuadTree zaadaptowanej dla danego zbioru wierzchołków triangulacji.

Trochę teorii

Metoda QuadTree

Jest to drzewiasta struktura danych, odpowiadająca pewnemu fragmentowi przestrzeni i dzieląca go na cztery podfragmenty tego samego typu.

Metodą QuadTree możemy podzielić przestrzeń na kwadraty.

Podziału na trójkąty możemy dokonać poprzez powstawianie przekątnych.

Liście drzewa muszą odpowiadać co najwyżej jednej krawędzi triangulowanego wielokąta.

W jaki sposób to zostanie zaimplementowane

Podział boków wielokąta na odcinki o zadanej długości

v = (x,y) -wektor reprezentujący bok wielokąta

L = x^2+y^2 - długość boku

a - zadana długość

mamy zatem n = ceil(L/a) odcinków o długości L/n wyznaczonych przez wektory (x/n,y/n)

Jeśli zatem P1 -punkt początkowy to kolejne krańce odcinków:

P1+(kx/n,ky/n), gdzie k -dowolna liczba całkowita.

Triangulacja metodą QuadTree

Trójkąty możliwie najbliższe równobocznym można uzyskać dzięki:

• Odpowiednio zbalansowanej siatki czworokątów przed przystąpieniem do właściwej triangulacji. (Podział niektórych liści na mniejsze czworokaty)
• Dodanie dotatkowych tzw. punktów Steinera na środku czworokąta, co sprawi że kąty trójkąta będą miały miary nie mniejsze niż 45 stopni. (Stosowanie samych przekątnych grozi powstaniem kątów mniejszych od 45 stopni)

Kolejne etapy algorytmu

1. Podział boków wielokąta.
2. Konstrukcja siatki kwadratowej i budowa drzewa QuadTree.
3. Dodanie do zbioru punktów: przecięć krawędzi wielokąta z siatką, krawędzi siatki i ewentualnie punktów Steinera.
4. Użycie zbudowanej siatki do wyznaczenia właściwej triangulacji.
5. Usunięcie trójkątów zewnętrznych.

Struktury danych

• Struktura QuadTree poza wskaźnikami na poddrzewa zawierająca:

-położenie środka

-długość boku kwadratu

-współrzędne punktu środkowego

• Zbiory punktów:

-wielokąta

-krawędzi siatki, punktów Steinera