Geometria obliczeniowa
Struktury danych do pracy w przestrzeni k-d-drzewa (pozwala na znalezienie najbliższych punktów). Bounding box (sphere, ellipsoid etc) przydaje się do gier (wykrywanie kolizji).Maksymalnie z poniższych zadań można zdobyć 3 punkty.
ZADANIE 1 (na zachętę). (1p) Proszę zbudować algorytm do sprawdzania czy wielokąt jest wypukły.
ZADANIE 2. (1p) Proszę zaimplementować najprostszy algorytm, na przykład z wiki sprawdzający czy punkt jest w wielokącie (za 2 punkty jeżeli za pomocą winding number).
ZADANIE 3. (1p) Sprawdzić, czy wielomian bez samoprzecięć (polygon without self-intersections) - najprościej sprawdzić czy żadne dwa się nie przecinają, przykładowy pseudokod, patrz po dokładniejszą dyskusję. (3p) za implementację algorytmu Bentleya-Ottmann.