Przecięcie Figur

Cel

Spoglądając na dwie figury na kartce bezproblemowo można określić czy się przecinają. Jednak jak można nauczyć komputer do sprawdzenia czy figury mają wspólną część? Zakładamy, że figury są wypukłe. W tym artykule zostanie przedstawione próba wykrycia kolizji poprzez sprawdzenie czy chociaż jeden punkt jednej z figur leży wewnątrz drugiej.

Analiza Zadania

Teoria

W rozwiązaniu problemu zostanie wykorzystana metoda, która pozwala określić po której stronie prostej leży punkt. Rozpatrzmy następujący układ:

Układ punktów

Dla dowolnego punktu P oraz dwóch punktów końcowych A i B pewnego odcinka można obliczyć wartość d = (P_x-A_x)(B_y-A_y) - (P_y-A_y)(B_x-A_x). O położeniu punktu decyduje obliczone d. Dla d = 0 punkty leżą na tej samej prostej, dla d < 0 po jednej stronie, a dla d > 0 po drugiej stronie.

Zastosowanie

Dla danej figury wyznaczamy punkt środkowy. Figury wprowadzone do programu będą wielokątami wypukłymi, więc wystarczy użyć średniej arytmetycznej.

Przykładowa figura

Pierwszy krok polega na obliczeniu dla punktu środkowego współczynników dla każdego boku. Następnie wybieramy inny punkt i powtarzamy ten proces. Jeśli wszystkie obliczone wartości mają ten sam znak to znaczy, że punkt znajduje się wewnątrz figury. W przeciwnym razie na zewnątrz. W przypadku dwóch figur cały ten proces porównywania robimy dla każdego punktu drugiej figury i jeśli choć jeden znajduje się wewnątrz pierwszej to figury się przecinają.

Implementacja

Do obliczania wartości d wystarczy poniższa funkcja:

1. double Obliczd(Punkt A, Punkt B, Punkt P) {
2.   return (P.first - A.first) * (B.second - A.second)
3.     - (P.second - A.second) * (B.first - A.first);
4. }

Wykorzysta ją funkcja CzyCzescWspolna(), która dla podanych dwóch wielokątów poda czy mają część wspólną. Przyjmujemy, że wielokąt jest opisany przez listę punktów i są one posortowane względem kąta obrotu wokół środka figury.

1. bool CzyCzescWspolna(vector<Punkt> wielokat1, vector<Punkt> wielokat2) {
2.   int n1 = wielokat1.size();
3.   double x_sr = 0, y_sr = 0;
4.   for (int i = 0; i < n1; i++) {
5.     x_sr += wielokat1[i].first;
6.     y_sr += wielokat1[i].second;
7.   }
8.   Punkt srodek = make_pair(x_sr / n1, y_sr / n1);
9.   double * wyniki = new double[n1];
10.   for (int i = 0; i < n1; i++) {
11.     wyniki[i] = Obliczd(wielokat1[i], wielokat1[(i + 1) % n1], srodek);
12.   }
13.   double d; Punkt p;
14.   for (int j = 0; j < wielokat2.size(); j++) {
15.     bool wewnatrz = true;
16.     p = wielokat2[j];
17.     for (int i = 0; i < wielokat1.size(); i++) {
18.       d = Obliczd(wielokat1[i], wielokat1[(i + 1) % n1], p);
19.       if (d * wyniki[i] < 0) {
20.         wewnatrz = false;
21.         break;
22.       }
23.     }
24.     if (wewnatrz) {
25.       return true;
26.     }
27.   }
28.   return false;
29. }

Algorytm początkowo wyznacza punkt środkowy i wartości d dla każdego z boków figury. Następnie dla każdego punktu z drugiej figury sprawdzamy czy leży wewnątrz pierwszej. Jeśli żaden punkt nie zostanie wykryty to zwracamy fałsz.

Testowanie funkcji

Do przetestowania napisanego kodu można skorzystać z poniższego fragmentu kodu:

1. vector<Punkt> WczytajWielokat(int k = 1) {
2.   int n;
3.   cout << "Ile bokow ma wielokat " << k << "?\n k = ";
4.   cin >> n;
5.   cout << "Podaj punkty:" << endl;
6.   vector<Punkt> punkty;
7.   double x, y;
8.   for (int i = 0; i < n; i++) {
9.     cin >> x >> y;
10.     punkty.push_back(make_pair(x, y));
11.   }
12.   return punkty;
13. }
15. int main() {
16.   vector<Punkt> wielokat1 = WczytajWielokat(1);
17.   vector<Punkt> wielokat2 = WczytajWielokat(2);
18.   bool wspolna_czesc = CzyCzescWspolna(wielokat1, wielokat2);
19.   cout << (wspolna_czesc ? "Istnieje" : "Nie istnieje");
20.   system("pause");
21.   return 0;
22. }

• Kod źródłowy Implementacja