14. YSC2229 Lecture Notes, Week 14

• 14.1. Basics of Computational Geometry
  • 14.1.1. Working with graphics in OCaml
• 14.2. Points, Segments and their Properties
  • 14.2.1. On precision and epsilon-equality
  • 14.2.2. Points on a two-dimensional plane
  • 14.2.3. Points as vectors
  • 14.2.4. Scalar product of vectors
  • 14.2.5. Polar coordinate system
  • 14.2.6. Vector product and its properties
  • 14.2.7. Segments on a plane
  • 14.2.8. Generating random points on a segment
  • 14.2.9. Collinearity of segments
  • 14.2.10. Checking for intersections
  • 14.2.11. Finding intersections
• 14.3. Working with Polygons
  • 14.3.1. Encoding and rendering polygons
  • 14.3.2. Some useful polygons
  • 14.3.3. Basic polygon manipulations
  • 14.3.4. Queries about polygons
  • 14.3.5. Intermezzo: rays and intersections
  • 14.3.6. Point within an polygon
• 14.4. Convex Hulls
  • 14.4.1. Plane-sweeping algorithm
  • 14.4.2. Graham scan invariant

Supplementary materials

• Working with graphics in OCaml
• Points and Segments
• Polygons and operations on them
• Convex Hulls
• Automated Tests