Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Sprawdzenie, czy dwa odcinki przecinają się

powrót

Artykuł przedstawia algorytm sprawdzający, czy dwa odcinki przecinają się. Żeby dwa odcinki przecinały się musi zachodzić jeden z dwóch przypadków:

  1. Odcinki przecinają się wtedy i tylko wtedy gdy pierwszy odcinek przecina prostą zawierającą drugi odcinek oraz drugi odcinek przecina prostą zawierającą pierwszy odcinek.
  2. Druga sytuacja to taka, w której jeden z końców odcinka leży na drugim odcinku.
dwa odcinki

Do rozwiązania problemu przedstawiającego pierwszy podpunkt wykorzystamy iloczyn wektorowy. Jak w czasie stałym sprawdzić, czy dwa odcinki się przecinają? 

Tworzymy wektor z odcinka AB, gdzie

{tex}A = (x_A, y_A), B = (x_B, y_B){/tex}

w następujący sposób:

{tex}\overrightarrow{AB}=[x_B-x_A, y_B-y_A]{/tex}

gdzie {tex}[x_B-x_A, y_B-y_A]{/tex} to współrzędne wektora {tex}\overrightarrow{AB}{/tex}. Następnie sprawdzamy, czy początek odcinka CD leży po jednej stronie prostej zawierającej odcinek AB a koniec po drugiej stronie. W tym celu wykorzystamy iloczyn wektorowy. Tworzymy dwa dodatkowe wektory {tex}\overrightarrow{AC}{/tex} oraz {tex}\overrightarrow{AD}{/tex}. Jeśli punkty C i D będą leżały po przeciwnych stronach prostej AB iloczyny wektorowe {tex}\overrightarrow{AB}x\overrightarrow{AC}{/tex} oraz {tex}\overrightarrow{AB}x\overrightarrow{AD}{/tex} muszą być przeciwnych znaków, a więc ich iloczyn musi być liczbą ujemną. Następnie sprawdzamy, czy zachodzi ta sama sytuacja dla wektora {tex}\overrightarrow{CD}{/tex} i końców odcinka AB.

Jak liczymy iloczyn wektorowy? Załóżmy, że mamy wektor {tex}\overrightarrow{u}=[x_u,y_u]{/tex} oraz {tex}\overrightarrow{v}=[x_v,y_v]{/tex}. Iloczyn wektorowy {tex}\overrightarrow{u}x\overrightarrow{v}{/tex} jest równy wyznacznikowi:

{tex}det \begin{vmatrix}x_u & x_v\\ y_u & y_v\end{vmatrix}=x_uy_v-x_vy_u{/tex}

Jeśli iloczyn wektorowy jest równy zero, oznacza to, że rozpatrywane trzy punkty są współliniowe. Jedyne co należy sprawdzić w takiej sytuacji, to czy koniec jednego odcinka leży na drugim.

Rozwiązanie w C++

#include<iostream>
#define pkt pair<int, int>
using namespace std;
 
int iloczyn_wektorowy(pkt X, pkt Y, pkt Z)
{
  int x1 = Z.first - X.first, y1 = Z.second - X.second,
    x2 = Y.first - X.first, y2 = Y.second - X.second;
  return x1*y2 - x2*y1;
}
//sprawdzenie, czy punkt Z(koniec odcinka pierwszego)
//leży na odcinku XY
bool sprawdz(pkt X, pkt Y, pkt Z)
{
  return min(X.first, Y.first) <= Z.first && Z.first <= max(X.first, Y.first) 
    && min(X.second, Y.second) <= Z.second && Z.second <= max(X.second, Y.second);
}
 
bool czy_przecinaja(pkt A, pkt B, pkt C, pkt D)
{
  int v1 = iloczyn_wektorowy(C, D, A),
    v2 = iloczyn_wektorowy(C, D, B),
    v3 = iloczyn_wektorowy(A, B, C),
    v4 = iloczyn_wektorowy(A, B, D);
 
  //sprawdzenie czy się przecinają - dla niedużych liczb
  //if(v1*v2 < 0 && v3*v4 < 0) return 1;
 
  //sprawdzenie czy się przecinają - dla większych liczb
  if((v1>0&&v2<0||v1<0&&v2>0)&&(v3>0&&v4<0||v3<0&&v4>0)) return 1;
 
  //sprawdzenie, czy koniec odcinka leży na drugim
  if(v1 == 0 && sprawdz(C, D, A)) return 1;
  if(v2 == 0 && sprawdz(C, D, B)) return 1;
  if(v3 == 0 && sprawdz(A, B, C)) return 1;
  if(v4 == 0 && sprawdz(A, B, D)) return 1;
 
  //odcinki nie mają punktów wspólnych
  return 0;
}
int main()
{
  pair<int, int> A, B, C, D;
 
  //definiujemy dwa odcinki skierowane A->B oraz C->D
  cout<<"Podaj wspólrzedne punktu A: ";
  cin>>A.first>>A.second;
 
  cout<<"Podaj wspólrzedne punktu B: ";
  cin>>B.first>>B.second;
 
  cout<<"Podaj wspólrzedne punktu C: ";
  cin>>C.first>>C.second;
 
  cout<<"Podaj wspólrzedne punktu D: ";
  cin>>D.first>>D.second;
 
  if(czy_przecinaja(A, B, C, D)) 
    cout<<"Odcinki sie przecinaja\n";
  else
    cout<<"Odcinki sie nie przecinaja\n";
 
  cin.ignore();
  cin.get();
 
  return 0;
}