MOKIP 24.10.2012

Geometria Obliczeniowa (podstawy)

1. Reprezentacja obiektów
Warto pisać struktury do reprezentacji punktów, aby się nie pogubić!
Gdzie tylko się da unikać typów zmiennoprzecinkowych double i long double, a stosować int.
Wielokąt zwykle pamiętamy jako tablicę punktów (wierzchołków) w kolejności ich wystapieniana obwodzie (zgodnie lub przeciwnie do wskazówek).

2. Iloczyn skalarny
$[a,b]\circ[c,d]=ac+bd$
Nie aż taki ważny, ale pozwala na przyład poznać, kiedy wektory są prostopadłe (wtedy wynosi 0).
Iloczyn skalarny wektorów AB i CD realizuje funkcja:

int ps(point &a, point &b, point &c, point &d)
{
   return (b.x-a.x)*(d.x-c.x)+(b.y-a.y)*(d.y-c.y);
}

Mnemotecyhnika: mnożymy X z X i Y z Y i dodajemy.
Iloczyn skalarny wektora ze sobą to kwadrat jego długości ( czyli |AB|^2 = ps(A,B,A,B) ).

3. Iloczyn wektorowy
$[a,b]\times[c,d]=ac-bd$
Bardzo ważny - pojawi się jeszcze z n razy.
Cechą szczególną jest to, że rozpoznaje skierowanie kąta (jesli katy są przeciwnie skierowane - iloczyny wektorowe mają przeciwne znaki). Wartośc bezwzględna iloczynu wektorowego AB i BC jest dokładnie dwa razy większa od pola trójkąta ABC.
Poniższa funkcja oblicza iloczyn wektorowy AB i BC.

int pw(point &a, point &b, point &c)
{
   return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y);
}

Mnemotechnika: mnożymy X z Y i Y z X i odejmujemy - "odwrotnie jakw skalarnym".

4. Pole wielokąta
Aby obliczyć pole wielokąta, wyznaczamy najpierw dowolny punkt p (choćby 0,0) i ustalamy wynik na 0. Następnie dla wszystkich n wierzchołków w[i] wielokąta robimy tak:
wynik+=pw(w[i],p,w[(i+1)%n]);
(Liczymy iloczyn wektorowy dla AP i PB gdzie A i B to sąsiednie wierzchołki wielokąta i dodajemy do wyniku).
Po przejściu przez wszystkie wierzchołki (tak naprawdę krawędzie) wielokąta pole wynosi abs(wynik)/2.

5. Przecięcia odcinka z prostą lub drugim odcinkiem
Odcinek przecina prostą, kiedy jego końce leżą po przeciwnych stronach prostej. Sprawdzamy to iloczynem wektorowym. Jeśli prostą wyznaczają punkty A i B, to CD przecina prostą wtedy gdy (UWAGA! To nie działa dla odcinka leżącego na prostej, ale zawsze łatwo poprawić):
sgn(pw(A,B,C)) != sgn(pw(A,B,D))
Aby odcniki AB i CD się przecinały, każdy musi przecinać prostą wyznaczoną przez drugi odcinek,czyli muszą zajść oba warunki:
sgn(pw(A,B,C)) != sgn(pw(A,B,D)) && sgn(pw(C,D,A)) != sgn(pw(C,D,B))
Problem pojawia się, gdy A, B, C, D leżą na jednej prostej - wtedy wszystkie iloczyny są równe 0 i trzeba osobno rozpatrzyć czy uznajemy to za przeicęcie, czy nie.

6. Zawieranie punktu w wielokącie
Dla punktu P, którego zawieranie się w wielokącie chcemy sprawdzić, liczymy liczbę przecieć odcinka PX z bokami wielokąta (punkt X leży poza wielokątem. Po prostu zadabajmy, aby jedna ze współrzednych była wieksza niż zadanie przewiduje). Nieparzysta liczba przecięć z bokami oznacza, że punkt P leży wewnątrz wielokąta. Podobnie jak przy liczeniu pola iterujemy po wierzchołkach (krawędziach) i robimy testy jak w 5. Problem pojawia się, gdy PX zawiera bok wielokąta (można to wyifować i wtedy zmienić punkt X, ale jest to tak mało prawdopodobne że chyba nie warto). Jeśli używamy intów wystarczy dla P=(x,y) ustawić X=(30000,y+1) i nic się nie będzie zawierało.

7. Wypukłość wielokąta
Wielokąt jest wypukły wtedy i tylko wtedy, gdy dla każdego wierzchołka w[i] znak iloczynu wektorowego pw(w[i],w[(i+1)%n],w[(i+2)%n]) jest taki sam. Sprawdzamy po prostu, czy wszystkie kąty są jednakowo skierowane. Działa to w czasie liniowym od liczby wierzchołków - tak samo jak liczeni pola i sprawdzanie zawierania punktu.

8. Sortowaniu kątowe (bez udziwnień!!)
Tu tylko mały hint odnośnie znajdowania otoczki wypukłej. Sympatyczny algorytm rozwiązujący ten problem wymaga posortowania wierzchołków kątowo wokół najniżej położonego punktu. Normalnie, sortowanie kątowe wymaga albo rozbicia tablicy na dwie, albo wyifowania hardych przypadków szczególnych. Korzystając z faktu, że nasz punkt lezy najniżej, jako funkcję porównującą możemy użyć po prostu znak iloczynu wektorowego. Miara kąta nieskierowanego APB jest zawsze mnuejsza od 180. Przykładowa funkcja cmp powinna działać:

bool cmp(point A, point B)
{
   if (pw(A,P,B)==0)
      return ps(A,P,A,P)<ps(B,P,B,P); // Porównaj odległości (iloczynem skalarnym, albo dowolnie inaczej)
   else return pw(A,P,B)>0; // Jak sortuje w złą stronę, odwróćcie nierówność - to wszystko. 
}

Punkt P, wokół którego sortujemy powienien być oczywiście zmienną statyczną (globalną) i musi rzecz jasna spełniać założenie, że leży na otoczce wypukłej (np. ma najmniejszą współrzedną x).

Zadanie wielokąt (POL) z BOI 2011 i opracowanie można znaleźć w Archiwum.