Strona główna » Algorytmy » Przecięcie Figur
 

Przecięcie Figur

https://mattomatti.com/a0279

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 = (Px-Ax)(By-Ay) - (Py-Ay)(Bx-Ax). 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:

C++C#
Python
  1. def Obliczd(A, B, P):
  2. return (P.X - A.X) * (B.Y - A.Y) - (P.Y - A.Y) * (B.X - A.X)

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.

C++C#
Python
  1. def CzyCzescWspolna(wielokat1, wielokat2):
  2. n1 = len(wielokat1)
  3. x_sr, y_sr = 0, 0
  4. for punkt in wielokat1:
  5. x_sr += punkt.X
  6. y_sr += punkt.Y
  7. srodek = Punkt(x_sr / n1, y_sr / n1)
  8. wyniki = [0 for i in range(n1)]
  9. for i in range(n1):
  10. wyniki[i] = Obliczd(wielokat1[i], wielokat1[(i + 1) % n1], srodek)
  11. for p in wielokat2:
  12. wewnatrz = True
  13. for i in range(n1):
  14. d = Obliczd(wielokat1[i], wielokat1[(i + 1) % n1], p)
  15. if (d * wyniki[i] < 0):
  16. wewnatrz = False
  17. break
  18. if (wewnatrz):
  19. return True
  20. return False

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:

C++C#
Python
  1. def WczytajWielokat(k = 1):
  2. n = int(input("Ile bokow ma wielokat " + str(k) + "?\n k = "))
  3. print("Podaj punkty:")
  4. punkty = []
  5. for i in range(n):
  6. data = [float(x) for x in input().split()]
  7. punkty.append(Punkt(data[0], data[1]))
  8. return punkty
  10. wielokat1 = WczytajWielokat(1)
  11. wielokat2 = WczytajWielokat(2)
  12. wspolna_czesc = CzyCzescWspolna(wielokat1, wielokat2)
  13. print("Istnieje" if wspolna_czesc else "Nie istnieje")