Skip to the content ForoHackers
Log inJoin

Computational geometry: start here

Computational geometry
#3411 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply