Note de curs, clasele 9-12, 21 decembrie 2012
From Algopedia
Jump to navigationJump to search
Toate clasele au venit la aceeași oră, căci a fost ultima zi de școală și s-a făcut dirigenție etc.
Geometrie computațională - generalități
- cazuri particulare
- coliniaritate
- intersecții exact la un capăt al segmentului
- pante infinite
- erori de calcul
- uneori testul de egalitate nu se face cu ==
- împărțirea la zero
- operații tot mai costisitoare (+/-, *, /, sqrt, sin...)
Geometrie analitică
- ecuația dreptei, diverse forme:
- două puncte
- x-intercept și y-intercept
- pantă și y-intercept
- ax + by + c = 0
- cazuri limită, erori de precizie
- definiția pantei
Problemuțe
- test dacă două drepte sunt paralele, perpendiculare
- intersecția a două drepte
- test de apartenență în triunghi
- test de apartenență în poligon
- intersecția a două segmente
- aria unui poligon - împărțire în trapeze
- rezultă ceva neevident: un poligon cu coordonate întregi are arie întreagă sau cu partea fracțională 0,5.
Algoritmi
- closest pair 2D - algoritm divide et impera O(n log n)
- demonstrație de optimalitate: reducere la distinctness, reducere la sortare
- înfășurătoarea convexă
- naiv (pentru toate segmentele, vedem dacă toate celelalte n-2 puncte sunt de aceeași parte) O(n3)
- gift wrapping O(n * h) - compararea polară
- Graham scan O(n log n) (chiar O(n) dacă punctele sunt sortate).
- demonstrație că O(n log n) este optim prin reducere la sortare
- pentru un vector V[n], fiecărui element îi asociem punctul x -> P(x, x2)
- definiții: poligon monoton, triangulare
Teme de gândire pentru vacanță
- triangularea unui poligon monoton
- triangularea unui poligon oarecare
