Algorytmy » Geometria obliczeniowa

Współliniowość trzech punktów

  • 2010-10-31 18:27
  • 1 komentarz
  • 1458 odsłon
  • Oceń ten tekst jako pierwszy

Strona w budowie
Ktoś pracuje nad tą stroną, jej zawartość może się wkrótce zmienić. Prosimy o cierpliwość!



Wejście: trzy punkty a, b i c
Wyjście: określić po której stronie prostej ab leży punkt c.
Złożoność: O(1)

Określenie strony, po której leży jest równoznaczne z określeniem kąta zawartego pomiędzy wektorem ab i ac. Jeżeli kąt ten jest z zakresu (0, pi) to punkt leży po lewej stronie. Jeżeli (pi, 2pi) to po prawej. Jeżeli kąt jest równy 0 to punkt leży na prostej - punkty a, b i c są współliniowe.
//TODO: umieścić rysunki.

Aby wyznaczyć kąt pomiędzy wektorami należy obliczyć wyznacznik macierzy det(a, b, c):
|a0 a1 1|
|b0 b1 1|=sin kąta pomiędzy ab i ac
|c0 c1 1|

Wyznacznik mniejszy od 0 oznacza, że punkt leży po lewej stronie. Większy, że leży po prawej.
class vector(tuple):
    def __add__(self, other):
        ''' Dodawanie wektorow. '''
        return vector([i+j for i, j in zip(self, other)])
    def __mul__(self, other):
        ''' Mnozenie przez stala. '''
        return vector([i*other for i in self])
    def __sub__(self, other):
        ''' Odejmowanie wektorow. '''
        return vector([i-j for i, j in zip(self, other)])
    def dot(self, other):
        ''' Iloczyn skalarny wektorow. '''
        return sum((i*j for i, j in zip(self, other)))
 
def det(a, b, c):
    ''' Wyznacznik macierzy. '''
    a0, a1 = a
    b0, b1 = b
    c0, c1 = c
    return a0*b1+a1*c0+b0*c1-a0*c1-a1*b0-c0*b1
 
a = vector((a0, a1))
b = vector((b0, b1))
c = vector((c0, c1))
result = det(a, b, c)
if result < 0:
    print 'punkt lezy po lewej stronie prostej'
elif result > 0:
    print 'punkt lezy po prawej stronie prostej'
else:
    print 'punkt lezy na prostej'

1 komentarz

Xitami 2007-03-26 02:48

oj, tyle kodu a ważny jest tylko jeden wiersz liczący iloczyn wektorowy

operujemy liczbami o skończonej precyzji, badając kolinearność z czym w zasadzie należałoby to porównywać, czyli jaki jest moduł zera?