Strona główna » Algorytmy » Artykuły » Współliniowość trzech punktów
 

Współliniowość trzech punktów

https://mattomatti.com/a58
Współliniowość trzech punktów można wykorzystać np. w grze

Współliniowość trzech punktów

Zakładamy, że mamy dane trzy punkty A = (xA, yA), B = (xB, yB), C = (xC, yC). Zadanie polega na sprawdzeniu czy istnieje prosta, która zawiera wszystkie podane punkty. Podany problem można rozwiązać na dwa sposoby.

Implementacja

Funkcja wspoliniowePunkty() wczyta od użytkownika trzy pary liczb x, y, a następnie zwróci wartość logiczną czy wczytane punkty należą do tej samej prostej.

Sprawdzanie ze wzoru funkcji liniowej

Załóżmy, że wszystkie punkty leżą na jednej prostej. Wtedy istnieją takie parametry a i b, że podłożone we wzorze f(x) = ax + b pozwolą na wyprowadzenie wszystkich współrzędnych x, y podanych trzech punktów.

Algorytm zbiega się do wyliczenia dwóch parametrów prostych. Jeden dotyczy prostej przechodzącej przez punkt A i B, a drugi prostej przechodzącej przez A i C. Jeśli obie wartości są identyczne to punkty leżą na tej samej prostej. W celu wyliczenia parametru a należy rozwiązać następujący układ:

Kod realizujący to zadanie:

  1. bool wspoliniowePunkty(){
  2.   double xa, ya, xb, yb, xc, yc;
  3.   cin >> xa >> ya >> xb >> yb >> xc >> yc;
  4.   return ((ya - yb) / (xa - xb)) == ((ya - yc) / (xa - xc));
  5. }

(2.) Przygotuj zmienne i (3.) wczytaj dane. (4.) Na podstawie wczytanych danych wyliczane są dwa parametry a dwóch prostych i sprawdza czy są identyczne.

Sprawdzanie z macierzy

Na podstawie rozwiązywanego układu można utworzyć macierz, której wyznacznik musi być równy 0, aby miała nieskończenie wiele rozwiązań, a co za tym idzie - współliniowość wszystkich trzech punktów.

Kod realizujący to zadanie wykorzystuje bibliotekę matrix.h, która jest rozwijana w ramach serwisu i zawiera podstawowe funkcje do między innymi tworzenia, wczytywania i usuwania macierzy.

  1. bool wspoliniowePunkty() {
  2.   Matrix* mat = createMatrix(3,3);
  3.   double x, y;
  4.   for (int i = 0; i < 3; i++) {
  5.     cin >> x >> y;
  6.     mat->data[i][0] = x;
  7.     mat->data[i][1] = y;
  8.     mat->data[i][2] = 1;
  9.   }
  10.   double w = wyznacznik(mat);
  11.   deleteMatrix(mat);
  12.   return (w == 0);
  13. }

(2.) Utwórz macierz i (3.) przygotuj zmienne do wczytywania danych. (4.) Rozpocznij wczytywanie trzech punktów: (5.) wczytaj pozycję i (6. - 8.) na tej podstawie uzupełnij kolejny pusty wiersz macierzy. Następnie (9.) wylicz wyznacznik macierzy i (10.) usuń macierz. (11.) Wynikiem zgodnie z teorią jest porównanie wyznacznika do 0.

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższej funkcji, która interpretuje zwrócony przez napisaną funkcję wynik. Należy pamiętać, że mogą pojawić się problemy z dokładnością obliczeń co oznacza, że program może zwracać nieprawidłowy wynik, ale kroki algorytmów są w pełni poprawne.

  1. int main () {
  2.   cout << ((wspoliniowePunkty()) ? "TAK" : "NIE") << endl;
  3.   system("pause");
  4.   return 0;
  5. }

Zadania

Zadanie 1

Na podstawie implementacji polegającej na parametrze a napisz funkcję podajRownanieProstej(), która pod warunkiem, że punkty leżą na jednej prostej, wypisze równanie tej prostej w postaci kierunkowej y = ax + b. Funkcja powinna wczytywać dane od użytkownika. Przykładowo dla danych:

  1. 1 10
  2. 0.5 3.5
  3. -1 -4

Program powinien wypisać na ekran:

  1. y = -x + 2

Zadanie 2

Na podstawie sprawdzania przy pomocy macierzy napisz funkcję wspoliniowePunkty, która wczyta liczbę n, a następnie n punktów i sprawdzi czy wszystkie punkty leżą na jednej prostej. Przykładowo dla wejścia:

  1. 4
  2. 1 10
  3. 10 73
  4. 0.5 3.5
  5. -1 -4

Program powinien wypisać na ekran:

  1. TAK