Autor Wątek: Okreslanie wspoliniowosci trzech punktow.  (Przeczytany 2304 razy)

Offline _user

  • Użytkownik

# Sierpień 20, 2015, 23:49:42
Hej, witam ponownie :)

Znowu trafilem na trudniejsze zagadnienie i musze przyjsc po porade, otoz daje do programu wspolrzedne trzech punktow i program ma stwierdzic czy sa one wspoliniowe czy nie.Nie wiem jak to wgl zrobic, nawet nie wiem jak sie to okresla, czytalem troche w internecie ale nie ogarniam tematu zupelnie, ktos moglby mi z tym pomoc ?
wpadlem na trop ze:
Warunek konieczny i wystarczający współliniowości:Punkty A, B i C są współliniowe wtedy i tylko wtedy, gdy |AC|=|AB|+|BC| lub |AC|=||AB|-|BC||.
Tylko czym jest AC,AB i BC ? AC=A*C ?
Znalazlem w internecie przyklady ludzi jak okreslaja te AC,AB i BC i napisalem cos ale nie dziala poprawnie potrzeba mi z tym pomocy, a to kod:
Kod: (c) [Zaznacz]
#include<stdio.h>

int main(void){
  int *tab,ab,ac,bc,x,y;

  for(int i=0;i<6;++i)
    scanf("%i",&tab[i]);

  ab=(tab[2]-tab[0])+(tab[3]-tab[1]);
  ac=(tab[4]-tab[0])+(tab[5]-tab[1]);
  bc=(tab[4]-tab[2])+(tab[5]-tab[3]);

  x=ab+bc;
  y=ab-bc;
 
  if(ac==x || ac==y)
    printf("TAK");
  else
    printf("NIE");

  return 0;
}
« Ostatnia zmiana: Sierpień 21, 2015, 00:05:32 wysłana przez _user »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 21, 2015, 00:09:02
Cytuj
ab=(tab[2]-tab[0])+(tab[3]-tab[1]);
  ac=(tab[4]-tab[0])+(tab[5]-tab[1]);
  bc=(tab[4]-tab[2])+(tab[5]-tab[3]);
Przede wszystkim wypadało by pozamieniać tu plusy na mnożenie.

Offline _user

  • Użytkownik

# Sierpień 21, 2015, 00:11:49
Zamienione ale program dalej nie dziala poprawnie

Offline bartekm

  • Użytkownik
    • Wordpress Blog

  • +4
# Sierpień 21, 2015, 00:18:41
I po co tak kombinować? Dwa punkty zawsze są współliniowe i tworzą pewną prostą o równaniu y = ax+b. Trzeci punkt jest współliniowy jeśli leży na tej prostej. Współczynniki a, b można znaleźć podstawiając współrzędne dwóch pierwszych punktów.

Offline _user

  • Użytkownik

# Sierpień 21, 2015, 00:23:18
beem nie rozumiem twojej wypowiedzi, ale ominalem jeden plus wczesniej i teraz jak zamienilem wszystkie obecne w kodzie plusy na mnozenie to program dziala do wszystkiego co wpisalem, chyba jest okej, dzieki :)

Offline bartekm

  • Użytkownik
    • Wordpress Blog

  • +2
# Sierpień 21, 2015, 00:35:07
Mamy trzy punky: P1 = (x1,y1), P2 = (x2,y2) i P3 = (x3, y3). Przez dwa punkty zawsze można poprowadzić prostą (mówią o tym dwa pierwsze aksjomaty Euklidesa). Równanie tej prostej można zapisać w postaci y = ax+b, gdzie a i b można znaleźć podstawiając współrzędne dwóch pierwszych punktów. Wtedy otrzymamy układ równań: y1 = a*x1 + b i y2 = a*x2 + b. Znając a i b można sprawdzić czy trzeci punkt leży na tej prostej jeśli spełniona jest równość: y3 = a*x3 + b. Można też spróbować sprawdzić czy te trzy punkty tworzą trójkąt. Jeśli tak to nie leżą na prostej i vice versa.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +5
# Sierpień 21, 2015, 11:23:41
Cytuj
Dwa punkty zawsze są współliniowe i tworzą pewną prostą o równaniu y = ax+b.
Nie zawsze. Jeśli mają tą samą współrzędną X to nijak Ci równanie w tej postaci nie wyjdzie. Poza tym współrzędne na wejściu są całkowite, a przechodząc do tej postaci 'a' musi być rzeczywiste, więc zapraszasz tu błędy precyzji.

Cytuj
Równanie tej prostej można zapisać w postaci y = ax+b
Niestety nie każdej prostej, jak powyżej.

Polecam zapomnieć o równaniu y=ax+b (chyba że masz gwarancję że X'y będą różne, a błędy precyzji cię nie obchodzą) i jeśli już, to zastosować bardziej ogólne Ax+By+C=0.
Mając punkty (x1,y1) i (x2,y2) współczynniki wyznacza się trywialnie:
    A = y1 - y2        (różnica Y, w dowolnej kolejności)
    B = x2 - x1        (różnica X, w innej kolejności niż różnica Y)
    C = -Ax1 - By1   (trywialnie ze wzoru na prostą)

Plus tego jest taki, że jeżeli współrzędne są całkowite, to współczynniki też będą. Jedyna na co trzeba uważać to zakresy obliczeń jeśli punkty mają mieć współrzędne większe niż ~32 000.

Offline bartekm

  • Użytkownik
    • Wordpress Blog

  • +1
# Sierpień 21, 2015, 11:48:45
Nie zawsze. Jeśli mają tą samą współrzędną X to nijak Ci równanie w tej postaci nie wyjdzie. Poza tym współrzędne na wejściu są całkowite, a przechodząc do tej postaci 'a' musi być rzeczywiste, więc zapraszasz tu błędy precyzji.
Niestety nie każdej prostej, jak powyżej.

Fakt trzeba by policzyć wcześniej czy te punkty mają różne współrzędne x x1 =/= x2 =/= x3 i dopiero wtedy liczyć równanie prostej.

Prościej byłoby policzyć pole powierzchni trójkąta S, którego wierzchołkami są te punkty. Jeśli S = 0 to są one współliniowe. S można wyliczyć z:
            | x1 y1 1 |
S = det| x2 y2 1 |
            | x3 y3 1 |

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 21, 2015, 13:31:25
Cytuj
Fakt trzeba by policzyć wcześniej czy te punkty mają różne współrzędne x x1 =/= x2 =/= x3 i dopiero wtedy liczyć równanie prostej.
Nie rozwiązuje to jednak problemu z precyzją obliczeń i w efekcie tą metodą nie jesteś w stanie ustalić, czy punkty są na pewno na jednej prostej, czy tylko tak mniej więcej.

Offline lukasz1985

  • Użytkownik

# Sierpień 21, 2015, 17:58:07
Zerknij tu, kompletny program w Pythonie który robi to właśnie co chcesz.

http://pastebin.com/JU5m8SY2

Offline bartekm

  • Użytkownik
    • Wordpress Blog

# Sierpień 21, 2015, 23:52:57
Nie rozwiązuje to jednak problemu z precyzją obliczeń i w efekcie tą metodą nie jesteś w stanie ustalić, czy punkty są na pewno na jednej prostej, czy tylko tak mniej więcej.
Metoda z prostą pod postacią Ax+By+C = 0 też jest obarczona błędem precyzji, jak w zasadzie każda gdzie stoi znak równości.

Jeszcze inny sposób, który mi przyszedł do głowy to zbudowanie dwóch wektorów z trzech punktów zaczepionych w jednym i wyznaczenie kąta między nimi. Jeśli kąt wyjdzie 180 stopni to punkty są współliniowe.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 22, 2015, 00:46:33
Cytuj
Metoda z prostą pod postacią Ax+By+C = 0 też jest obarczona błędem precyzji, jak w zasadzie każda gdzie stoi znak równości.
Nie jest, bo w tym przykładzie współrzędne są całkowite, jak wynika z przykładowego kodu w pierwszym poście.