geometria

Wykład 19. Algorytmy geometryczne

Na wykładzie omówiłem następujące zagadnienia:

  • Podstawowe struktury (punkt, prosta) i operacje (dodawanie, mnożenie, odejmowanie)
  • Operacje na prostych (przecięcie)
  • Operacje na okręgach (przecięcia, styczne) - dwie technologie (binarka i obroty)
  • Dobór epsilona - szacowania górne i dolne
  • Kilka sztuczek - wyszukiwania binarne, wypukłość, środek ciężkości, zliczanie

Uwagi:
Podczas wykładu kilkakrotnie zdarzyło mi się nie podać porządnego wzoru na coś, albo podać wzór niepoprawny (choć rozumowania wszystkie były poprawne). Niniejszym to nadrabiam:
Kod liczący przecięcie dwóch prostych (prostej AC i prostej BD):
s = cp(A-B,D-B) / cp(A-C,D-B); O = A + s * (C-A);
(jeśli wychodzi dzielenie przez zero, to proste są równoległe)
Przecięcie odcinków robimy jako przecięcie prostych i potem sprawdzenie funkcją between czy O leży między A i C i czy leży między B i D. Funkcja between to na przykład dp(O-A,C-A) * dp(O-C,A-C) >= -EPS;
Tak dokładnie to to sprawdza, czy rzut O na prostą AC leży na odcinku AC, jeśli jeszcze chcemy mieć, że punkt O leży na prostej AC to sprawdzamy abs(cp(O-A,C-A)) < EPS;.
Przy pisaniu "uczciwego" (tj. bez binarki) przecięcia okręgu i prostej oszukałem w odpowiedzi na pytanie "w którą stronę obracać" - niestety trzeba o tym myśleć. Konkretnie, to zależy od tego, w którą stronę jest skierowana "odległość od prostej", którą stosujemy. Jeżeli na_prawo(A,L) implikuje, że dist(A,L) > 0, to trzeba obracać w prawo. Jeśli na_prawo(A,L) implikuje dist(A,L) < 0, to trzeba obracać w lewo.
 
Wykład poprowadził Jakub Wojtaszczyk. Lokalizacja: 3130. Termin: 19.05.2009, 16:15-18:00.
Dostępne materiały: Nagrania, Biblioteczka.

Wykład 16. Zamiatanie w geometrii

Na wykładzie omówiłem następujące zagadnienia:

  • Zadanie Poziomice z PA 2006.
  • Problem najbliższej pary punktów za pomocą zamiatania.
  • Sprawdzanie przynależności wielu punktów do wielokąta (dowolnego).
  • Pole i obwód sumy prostokątów.
  • Zadanie Łyżwy z II etapu XVI OI (może nie ma związku z zamiataniem, ale z drzewami przedziałowymi już tak).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: 17.03.2009, 16:15-18:00.

Dostępne materiały: Nagrania.

Wykład 4. Geometria obliczeniowa

 Zagadnienia, które były poruszone na wykładzie:

  • Typy zmiennoprzecinkowe. Jak to dziala. double vs long double.
  • Typy zmiennoprzecinkowe vs operowanie na liczbach całkowitych.
  • Podstawowe operacje. Iloczyn skalarny i wektorowy.
  • Podstawowe operacje, c.d. Rzuty, symetrie, przecięcia.
  • Zadania na przetnij wszystko ze wszystkim i zobacz, czy wyszło.
  • Kilka nietrywialnych algorytmów. Wypukła otoczka. Najdalsza para punktów. Przecięcie półpłaszczyzn.
  • Miotły. To kompletnie inny temat. Kilka przykładów zadań.
  • Kilka podstawowych sztuczek w przestrzeni.

Wykład poprowadził Marcin Pilipczuk. Lokalizacja: 3150. Termin: 17.03.2008, 16:15-17:45.

Dostępne materiały: Nagrania, Prezentacja z wykładu (w formacie ppt), Prezentacja z wykładu (w formacie pptx), Zadania.

Syndicate content