algorytm.org

Wprowadzenie do geometrii obliczeniowej



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Wprowadzenie do geometrii obliczeniowej
Ocena użytkowników:***** / 45
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 19:07

Geometria obliczeniowa jest działem informatyki zajmujący się algorytmami geometrycznymi. Jest ona bardzo szeroko stosowana np. w przeżywającej ostatnio błyskawiczny rozwój trójwymiarowej grafice komputerowej, także w automatyce i robotyce, w statystyce itd... Algorytmy geometryczne różnią się od arytmetycznych głównie rodzajem danych wejściowych. W geometrii obliczeniowej działamy nie na liczbach, łańcuchach znaków, lecz na obiektach geometrycznych: punktach, odcinkach, prostych, półprostych, wektorach, płaszczyznach, bryłach itd... Jeżeli mamy do czynienia ze zbiorem takich obiektów, należy je podawać w porządku przeciwnym do ruchu wskazówej zegara.
Prerzentowane na tej witrynie algorytmy geometryczne dotyczą głównie przestrzeni 2D, choć geometria obliczeniowa zajmuje się oczywiście także (a raczej przede wszystkim) przestrzenią 3D.
Do zrozumiania algorytmów geometrycznych niezbędna jest znajomość kilku podstawowych pojęć matematycznych. Ponieważ niektóre dotyczą tzw. matematyki wyższej postanowiłem streścić je na tej stronie.

Wektorem nazywamy uporządkowaną parę punktów.
Niech dane są 3 punkty: a=(x1,y1), b=(x2,y2), c=(x3,y3), wówczas det(a,b,c) jest wyznacznikiem macierzy:
Macierz kwadratowa

Przypominam, że wyznacznik macierzy kwadratowej trzeciego stopnia można łatwo obliczyć korzystając z metody Sarrusa:

Metoda Sarrusa = a11a22a33 + a21a32a13 + a31a12a23 - a13a22a31 - a23a32a11 - a33a12a21

Stosując ten schemat otrzymamy det(a,b,c) = x1y2 + x2y3 + x3y1 - x3y2 - x1y3 - x2y1
Ponad to znak det(a,b,c) jest równy znakowi sinusa kąta nachylenia wektora a->c do wektora a -> b

Poprawiony: 20 maja 2006 16:48
Komentarze
photo
+1 # anymous 2010-05-08 11:56
Czy ten sam schemat możemy stosować dla więcej niż 3 punktów?
A jak to jest w przypadku 3D? Czy wtedy nasza macierz będzie wyglądała tak:
[x1 y1 z1]
[x2 y2 z2]
[x3 y3 z3]
?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # kuba 2010-06-22 13:04
niestety nie można stosować tej metody jak jest wiecej niz 3 punkty bo wtedy macierz ma wymiary np 4x4 i to juz trzeba poczytac jak sie liczy wyznacznik macierzy ze wzoru polecam wikipedie do tego
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+12 # Nash 2010-11-02 00:31
"Do zrozumiania algorytmów geometrycznych niezbędna jest znajomość kilku podstawowych pojęć matematycznych. Ponieważ niektóre dotyczą tzw. matematyki wyższej postanowiłem streścić je na tej stronie."

To streszczenie to chyba jakiś żart. Bezsensowny mix 3 pojęć i nic więcej.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz