Jakub Wojtaszczyk

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.

Syndicate content