Part X · Computational Geometry and Advanced Algorithms
58. Computational Geometry Essentials
8 lessons•36 topics•Advanced / Expert
0 of 8 lessons published
58.01Outline
Coordinate geometry
- Points
- Vectors
- Distance
- Dot product
- Cross product
- Orientation
- Clockwise/counterclockwise
58.02Outline
Lines and segments
- Line equations
- Parallel/perpendicular
- Segment intersection
- Projection
- Point-to-line distance
58.03Outline
Polygon basics
- Simple polygon
- Area via shoelace
- Orientation
- Winding
- Point-in-polygon ray casting
58.04Outline
Convex hull
- Graham scan
- Monotone chain
- Collinear handling
- O(n log n) analysis
58.05Outline
Closest pair of points
- Brute force
- Divide-and-conquer O(n log n)
- Plane sweep variant
58.06Outline
Rotating calipers
- Diameter of convex polygon
- Antipodal pairs
- Width
- Bounding rectangle overview
58.07Outline
Circle geometry
- Circle-line intersections
- Circle-circle intersections
- Circumcircle
- Geometry tolerances
58.08Outline
Robust computation
- Integer coordinates
- Overflow in cross products
- Floating epsilon
- Exact predicates introduction