Geometric algorithms

algorithms.md

• Barycentric subdivision
• Newton–Raphson division
• Closest pair problem: find the pair of points (from a set of points) with the smallest distance between them
• Collision detection algorithms: check for the collision or intersection of two given solids
• Cone algorithm: identify surface points
• Convex hull algorithms: determining the convex hull of a set of points
  • Graham scan
  • QuickHull
  • Gift wrapping algorithm or Jarvis march
  • Chan's algorithm
  • Kirkpatrick–Seidel algorithm
• Euclidean Distance Transform - Computes the distance between every point in a grid and a discrete collection of points.
• Geometric hashing: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation
• Gilbert–Johnson–Keerthi distance algorithm: determining the smallest distance between two convex shapes.
• Jump-and-Walk algorithm: an algorithm for point location in triangulations
• Laplacian smoothing: an algorithm to smooth a polygonal mesh
• Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm
  • Bentley–Ottmann algorithm
  • Shamos–Hoey algorithm
• Minimum bounding box algorithms: find the oriented minimum bounding box enclosing a set of points
• Nearest neighbor search: find the nearest point or points to a query point
• Point in polygon algorithms: tests whether a given point lies within a given polygon
• Point set registration algorithms: finds the transformation between two point sets to optimally align them.
• Rotating calipers: determine all antipodal pairs of points and vertices on a convex polygon or convex hull.
• Shoelace algorithm: determine the area of a polygon whose vertices are described by ordered pairs in the plane
• Triangulation
  • Delaunay triangulation
    • Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations
    • Chew's second algorithm: create quality constrained Delaunay triangulations
  • Marching triangles: reconstruct two-dimensional surface geometry from an unstructured point cloud
  • Polygon triangulation algorithms: decompose a polygon into a set of triangles
  • Voronoi diagrams, geometric dual of Delaunay triangulation
    • Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions
    • Fortune's Algorithm: create voronoi diagram
  • Quasitriangulation
• Stochastic ray tracing (motion blur, depth of field)