Punkt w figurze: Metoda Kątów

Wstęp

Podczas tworzenia np. programów graficznych oraz gier bardzo często przydaje się informacja czy dany punkt znajduje się w pewnym obszarze. Jedna z metod sprawdzania tego wykorzystuje kąty.

Metoda

Przypuśćmy, że mamy pewien obszar ograniczony przez kilka punktów. Chcemy, aby napisana funkcja odpowiedziała na pytanie czy dany punkt leży wewnątrz obszaru. W tym celu należy dla każdej kolejnej pary punktów obszaru tworzymy trójkąt tak, aby zawierał zaznaczony punkt. Następnie sprawdzamy jaki kąt rozwarcia mają dorysowane ramiona. Wszystkie takie kąty sumujemy. Jeśli punkt leży wewnątrz to suma kątów wyniesie 360°. W przypadku innego wyniku punkt na pewno leży poza figurą.

Przykład

Weźmy obszar, który zostanie ograniczony przez 6 punktów. Przykładowo niech to będzie:

Kolejny etap polega na zaznaczeniu wybranego punktu na rysunku (zaznaczony kolorem czerwonym). Dodatkowo z zaznaczonego punktu zostaną poprawodzone odcinki do każdego z wierzchołków oraz zaznaczone zostaną kąty pomiędzy ramionami.

Człowiek jest w stanie w sposób wizualny potwierdzić, że punkt znajduje się w określonym obszarze. Komputer jednak musi wyliczyć wszystkie wartości zaznaczonych kątów, zsumować je i sprawdzić wynik.

Komputer po zsumowaniu wszystkich kątów otrzyma 6,283185307 ≈ 2π. Po zamianie miary łukowej na kątową otrzymujemy 360°. Oznacza to, że punkt znajduje się wewnątrz obszaru. Warto tutaj zauważyć, że błąd przybliżenia przechowywania zmiennych rzeczywistych może spowodować drobne odchylenie od poprawnego wyniku.

Sprawdźmy jeszcze jaka może być miara kąta jeśli punkt znajdzie się poza obszarem tak jak na poniższym rysunku:

Wyliczając ponownie całą tabelkę danych tj. odpowiednich odległości i na ich podstawie kąt otrzymujemy:

Po zsumowaniu wszystkich kątów wynik wychodzi 3,141592654 ≈ π = 180°. Oznacza to, że zaznaczony punkt znajduje się poza obszarem.

Matematyka

Poniżej został przedstawiony schemat dla wybranych dwóch kolejnych wierzchołków obszaru oraz zaznaczony wybrany punkt.

Na powyższym rysunku wszystkie wartości można wyliczyć z następujących wzorów:

\(odl(x_1, y_1, x_2, y_2):=\sqrt{(x_1 - x_2)^2+(y_1 - y_2)^2} \\a = d_l = odl(x_p, y_p, x_i, y_i)\\b = d_p = odl(x_p, y_p, x_{i+1}, y_{i+1})\\c = d_k = odl(x_i, y_i, x_{i+1}, y_{i+1}) \\2abcos(\alpha) = a^2+b^2-c^2 \Rightarrow cos(\alpha) = \frac{1}{2}\left ( \frac{a}{b} + \frac{b}{a} - \frac{c^2}{ab} \right ) \\\alpha=arcos\left ( \frac{1}{2}\left ( \frac{a}{b} + \frac{b}{a} - \frac{c^2}{ab} \right ) \right )\)

Implementacja

Przygotowanie

Przed rozpoczęciem pisania właściwego kodu należy przygotować wartość π, strukturę do przechowywania punktów oraz funkcję do obliczania odległości pomiędzy dwoma punktami.

1. const double PI = 3.1415926;
3. struct Point {
4.   double x, y;
6.   Point(double _x, double _y) {
7.     x = _x;
8.     y = _y;
9.   }
10. };
12. double odleglosc(Point punkt1, Point punkt2) {
13.   return sqrt(pow(punkt1.x - punkt2.x, 2) + pow(punkt1.y - punkt2.y, 2));
14. }

W strukturze Point dostęp jest bezpośredni dla wygody. Nie spełnia to hermetyzacji programu.

Czy w obszarze

Funkcja czyPunktwObszarze() będzie przyjmować 2 argumenty: obszar - lista wierzchołków obszaru, punkt - oznaczony punkt do sprawdzenia czy leży wewnątrz obszaru. Dodatkowo jest opcjonalny argument error. Ze względu na to, że obliczenia mogą w przybliżeniu zwracać 2π to istnieje potrzeba wprowadzenia o ile suma wyliczonych kątów może się różnić od 2π.

1. bool czyPunktwObszarze(vector<Point> obszar, Point punkt, double error = 0.0001) {
2.   double suma = 0;
3.   int n = obszar.size();
4.   for (int i = 0; i < obszar.size(); i++) {
5.     double c = odleglosc(obszar[i], obszar[(i + 1) % n]);
6.     double a = odleglosc(punkt, obszar[i]);
7.     double b = odleglosc(punkt, obszar[(i + 1) % n]);
8.     double kat = acos(0.5*(a / b + b / a - c*c / (a*b)));
9.     suma += kat;
10.   }
11.   return (abs(suma - 2 * PI) <= error);
12. }

(1.) Początkowo suma kątów wynosi 0. Następnie (2.) sprawdzana jest liczba wierzchołków. (3.) Dla każdej pary wierzchołków: (4. - 6.) obliczane są odpowiednio odległości, aby (7.) obliczyć kąt, który następnie jest (8.) dodany do sumy. Na koniec (10.) należy sprawdzić czy absolutna różnica pomiędzy 2π a sumą jest mniejsza, równa ustalonemu błędowi.

Testowanie funkcji

Działanie kodu można sprawdzić przy pomocy poniższego fragmentu kodu:

1. int main() {
2.   int n;
3.   cout << "Podaj ile punktow ma obszar\n n = ";
4.   cin >> n;
5.   vector<Point> obszar;
6.   double a, b;
7.   cout << "Podaj parami kolejne wspolrzedne punktow:\n";
8.   for (int i = 0; i < n; i++) {
9.     cin >> a >> b;
10.     obszar.push_back(Point(a, b));
11.   }
12.   cout << "Podaj punkt do sprawdzenia:\n";
13.   cin >> a >> b;
14.   bool w = czyPunktwObszarze(obszar, Point(a, b));
15.   cout << "Punkt " << (w ? "" : "nie ") << "jest w obszarze";
16.   system("pause");
17.   return 0;
18. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję czyPunktwObszarze(), która może zwrócić trzy stany: 0 - punkt poza obszarem, 1 - punkt na krawędzi obszaru oraz 2 - punkt w obszarze. Przetestuj działanie napisanej funkcji.

Przykładowo na poniższym rysunku

Punkt (0, 0) zwróci wartość 2, punkt (1, 1) zwróci 1, a punkt (2, 2) zwróci 0.

• Kod źródłowy Zadanie 1