Wiem, że mało ludzi to interesuje lecz chciałbym dzisiaj przedstawić dalszą część moich dygresji na temat triangulacji Delaunay. Po co właściwie zajmować się takim rodzajem triangulacji? Otóż sprawa jest dość prosta – jeżeli zamierzamy napisać własną grę 3D, w której postacie będą poruszały się po scenie, w jakiś sposób musimy wygenerować naszą scenę. Triangulacja Delaunay jest jednym ze sposobów generowania takiej przestrzennej siatki. Jak na razie, zajmijmy się jednak aspektami triangulacji w 2D.
Oczywiście jeżeli zamierzamy pisać grę najlepiej będzie nam zaimplementować ten algorytm w C, C++ lub innym języku obiektowym wysokiego poziomu. By zrozumieć ideę implementacja w C czy C++ nie będzie konieczna, dlatego też wykorzystałem do tego celu Matlaba w wersji 7.3.
Jak pisałem w jednym z poprzednich postów by dokonać triangulacji Delaunay w Matlabie wystarczy skorzystać z jednej z gotowych funkcji oferowanych przez ten program. Przykładowa implementacja mogłaby wyglądać mniej więcej tak:
d=change_kote1;
T=delaunay(d(:,1),d(:,2));
triplot(T,d(:,1),d(:,2),'red');
‘change_kote1′ jest tablicą dwuwymiarową zawierającą współrzędne punktów (x,y).
Co jednak zrobić by sprawdzić czy triangulacja jest prawidłowa? Musimy zbudować okręgi opisane na każdym z trójkątów. Jeżeli w środku każdego z nich nie będzie znajdował się ani jeden wierzchołek triangulacji będzie to oznaczać, że nasza triangulacja działa prawidłowo. Jak się do tego zabrać? Najlepiej do tego celu stworzyć oddzielną funkcję, która dla każdych trzech wierzchołków będzie zwracała promień oraz środek okręgu opisanego na trójkącie utworzonym z tych wierzchołków.
function [kola] = circle(x1,y1,x2,y2,x3,y3)
%obliczenie promienia
a=sqrt((x1-x2)^2+(y1-y2)^2);
b=sqrt((x2-x3)^2+(y2-y3)^2);
c=sqrt((x3-x1)^2+(y3-y1)^2);
promien=a*b*c/sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c));
%obliczenie srodka okregu opisanego na trojkacie
A_x=x1;
A_y=y1;
B_x=x2;
B_y=y2;
C_x=x3;
C_y=y3;
D=2*(A_y*C_x+B_y*A_x-B_y*C_x-A_y*B_x-C_y*A_x+C_y*B_x);
sx=(B_y*A_x^2-C_y*A_x^2-B_y^2*A_y+C_y^2*A_y+B_x^2*C_y+A_y^2*B_y+C_x^2*A_y-C_y^2*B_y-C_x^2*B_y-B_x^2*A_y+B_y^2*C_y-A_y^2*C_y)/D;
sy=(A_x^2*C_x+A_y^2*C_x+B_x^2*A_x-B_x^2*C_x+B_y^2*A_x-B_y^2*C_x-A_x^2*B_x-A_y^2*B_x-C_x^2*A_x+C_x^2*B_x-C_y^2*A_x+C_y^2*B_x)/D;
%zwraca promien oraz wspolrzedne x,y srodka okregu opisanego na trojkacie
kola=[promien, sx, sy];
Z ciekawszych rzeczy, na które warto zwrócić uwagę jest wzór na wyrażenie D, sx oraz sy. (sx, sy) – to współrzędne środka okręgu opisanego na trójkącie (w wolnej chwili warto by poszukać lepszego wzoru na ten punkt jeżeli do dyspozycji mamy jedynie wierzchołki trójkąta :P mi lepszego znaleźć się nie udało…).
Ostatnią rzeczą, która została nam do zaimplementowania jest wyświetlanie wszystkich okręgów opisanych:
hold on;
for i=1:1:(max(size(T))-2)
M=circle(d(T(i,1),1),d(T(i,1),2),d(T(i,2),1),d(T(i,2),2),d(T(i,3),1),d(T(i,3),2));
% okrąg o środku (a,b) i promieniu r we wsp. biegunowych
r=M(1); a=M(2); b=M(3); t = linspace(0,2*pi,200); x = a+r*cos(t); y = b+r*sin(t);
plot(x,y,'-','LineWidth',0.1);
axis auto; %axis equal
end
Teraz możemy cieszyć się efektami naszej pracy:
delaunay empty circle
Jeżeli kogoś zainteresował temat triangulacji Delaunay więcej interesujących materiałów można znaleźć na stronach:
