Algorithms

 

NEW   This site is now a book, available at Amazon as a
Paperback ($14.95)
Kindle eBook ($9.95)

Book_Cover

Table of Contents (TOC)

  • Linear Algebra
    • Coordinate Systems
    • Points and Vectors
      • Basic Definitions
      • Vector Addition
      • Scalar Multiplication
      • Affine Addition
      • Vector Length
    • Vector Products
      • Dot Product
      • 2D Perp Operator
      • 2D Perp Product
      • 3D Cross Product
      • 3D Triple Product
  • Area
    • Triangles
      • Ancient Triangles
      • Modern Triangles
    • Quadrilaterals
    • Polygons
      • 2D Polygons
      • 3D Planar Polygons
  • Lines
    • Lines
      • Line Equations
    • Distance from a Point to an Line
      • 2-Point Line
      • 2D Implicit Line
      • Parametric Line (any Dimension)
    • Distance from a Point to a Ray or Segment
  • Point in Polygon
    • The Crossing Number
      • Edge Crossing Rules
    • The Winding Number
    • Enhancements
      • Bounding Box or Ball
      • 3D Planar Polygons
      • Convex or Monotone Polygons
  • Planes
    • Planes
    • Plane Equations
      • Implicit Equation
      • Normal Implicit Equation
      • Parametric Equation
      • Barycentric Coordinates
      • Represention Conversions
      • Barycentric Coordinate Computation
    • Distance of a Point to a Plane
  • Line, Segment and Plane Intersections
    • Line and Segment Intersections
    • Plane Intersections
      • Intersection of a Line/Segment with a Plane
      • Intersection of 2 Planes
      • Intersection of 3 Planes
  • Ray, Plane and Triangle Intersections
    • Intersection of a Ray/Segment with a Plane
      • Intersection of a Ray/Segment with a Triangle
    • Intersection of a Triangle with a Plane
      • Intersection of a Triangle with a Triangle
  • Distance between Lines
    • Distance between Lines
      • Distance between Segments and Rays
    • Closest Point of Approach (CPA)
  • Set of Segments Intersections
    • A Short Survey
    • The Bentley-Ottmann Algorithm
    • The Shamos-Hoey Algorithm
    • Applications
      • Simple Polygons
        • Test if Simple
        • Decompose into Simple Pieces
      • Polygon Set Operations
      • Planar Subdivisions
  • Bounding Containers
    • Linear Containers
      • The Bounding Box
      • The Bounding Diamond
      • The Convex Hull
      • The Minimal Rectangle and Cuboid
    • Quadratic Containers
      • The Bounding Ball
        • A Fast Approximate Ball
      • The Bounding Ellipsoid
  • Convex Hull of a Planar Point Set
    • Convex Hulls
    • 2D Hull Algorithms
      • The "Graham Scan"
      • Andrew's Monotone Chain
  • Convex Hull Approximation
    • The BFP Approximate Hull
  • Convex Hull of a Simple Polyline
    • Background
    • Simple Polyline Hull Algorithms
      • The Basic Incremental Strategy
      • The Melkman Algorithm
  • Segment and Convex Polytope Intersection
    • Segment and Convex Polygon Intersection
    • Segment and Convex Polytope Intersection
  • Convex Polygon Extreme Points
    • Extreme Point Algorithms
      • Brute Force
      • Binary Search
    • Distance from a Polygon to a Line
  • Polygon Tangents
    • Tangents from a Point to a Polygon
      • Brute Force
      • Binary Search
    • Tangents between Two Polygons
      • Brute Force
      • Linear Search
      • Binary Search
  • Polyline Decimation
    • Vertex Cluster Reduction
    • The Douglas-Peucker Algorithm
      • Convex Hull Speed-Up

© Copyright 2001, 2021 Dan Sunday