Skip to the content ForoHackers
Log inJoin

Computational geometry: start here

Computational geometry
#905 · Ophuscado · · Report

Computational geometry designs algorithms for geometric objects: points, segments, polygons, circles and higher-dimensional shapes. It answers questions such as which points lie inside a region, what is the nearest neighbour, or how to mesh a surface. Maps, graphics, robotics, CAD and games all depend on it.

Key concepts

  • Orientation test: the sign of a cross product says whether three points turn left or right; most algorithms are built on it.
  • Convex hull: the smallest convex shape containing a set of points, found in O(n log n) by Graham scan or similar.
  • Sweep line: move an imaginary line across the plane and keep only the objects it touches; it finds segment intersections.
  • Triangulation and Voronoi diagrams: Delaunay triangulation and its dual divide space by proximity.
  • Spatial indexes: k-d trees, quadtrees and R-trees speed up range and nearest-neighbour queries.

Vocabulary

  • Degeneracy: a special case, such as three collinear points, that breaks naive code.
  • Robust predicates: tests that give the right answer even with rounding error, using exact or adaptive arithmetic.
  • Polygon: a closed chain of segments; simple means it does not cross itself.
  • Duality: a transformation that turns points into lines and back, making some problems easier.

What to study, in order

  1. Vectors, dot and cross products, and the orientation test.
  2. Implement the convex hull of random points and plot it.
  3. Test whether a point lies inside a polygon and whether two segments intersect.
  4. Learn the sweep line and build a Delaunay triangulation, then draw its Voronoi dual.
  5. Add a k-d tree for nearest-neighbour search and check it against brute force.

Related tags

#algorithms #computer-graphics #data-structures #spatial-data #linear-algebra

Log in or join to reply.