Wpisany przez Michał Knasiecki,
03 sierpnia 2005 22:51
Zrozumienie tego algorytmu wymaga zaznajomienia się ze wstępem do geometrii obliczeniowej
Wzajemne położenie trzech punktów a, b i c można bardzo łatwo określić korzystając z wyznacznika det(a,b,c) macierzy kwadratowej postaci:
det (a,b,c)=0 : punkty a, b, i c są współliniowe -
det (a,b,c)<0 : punkt c znajduje się po prawej stronie wektora AB -
dane są trzy punkty: a=(1,1), b=(9,1) oraz c=(4,4). Chcemy określić położenie punktu c względem wektora AB.
Budujemy macierz kwadratową i obliczamy jej wyznacznik (metodą Sarrusa):
Wzajemne położenie trzech punktów a, b i c można bardzo łatwo określić korzystając z wyznacznika det(a,b,c) macierzy kwadratowej postaci:
\begin{bmatrix}
x_1 & y_1 & 1\\
x_2 & y_2 & 1\\
x_3 & y_3 & 1
\end{bmatrix}
det (a,b,c)>0 : punkt c znajduje się po lewej stronie wektora AB - det (a,b,c)=0 : punkty a, b, i c są współliniowe -
det (a,b,c)<0 : punkt c znajduje się po prawej stronie wektora AB -
Przykład:
dane są trzy punkty: a=(1,1), b=(9,1) oraz c=(4,4). Chcemy określić położenie punktu c względem wektora AB.
Budujemy macierz kwadratową i obliczamy jej wyznacznik (metodą Sarrusa):
\det(a,b,c) =
\begin{bmatrix}
1 & 1 & 1\\
9 & 1 & 1\\
4 & 4 & 1
\end{bmatrix}
= 1 + 4*9 + 4 - 4 -4 -9 = 24
det(a,b,c)>0, więc punkt c leży po lewej stronie wektora AB. Czy tak jest faktycznie? Można to sprawdzić nanosząc współrzędne punktów na układ kartezjański.
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | Ada | .ada | .ada | ***** / 2 | |
| Michał Knasiecki | C/C++ | .cpp | .cpp | ***** / 8 | |
| Michał Knasiecki | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 2 |
| Tomasz Lubiński | Java | .java | .java | ***** / 2 | |
| Jakub Konieczny | Python | .py | .py | ***** / 3 |
Poprawiony: 27 sierpnia 2012 21:07