TOC for Geometry Algorithm Archive

This is the detailed Table of Contents (TOC) for the softSurfer Algorithm Archive.
There is also a condensed List of Algorithm Titles.

Note that these algorithms can be updated after their original posting to make enhancements, correct errors, or just to refactor them. If a particular algorithm is useful to you, check occasionally for updates.


Math
	Basic Linear Algebra (PDF document)	page
	Coordinate Systems	1
	Points and Vectors	2
	Basic Definitions	2
	Vector Addition	2
	Scalar Multiplication	3
	Affine Addition	3
	Vector Length	4
	Vector Products	5
	The Dot Product	5
	The 2D Perp Product	7
	The 3D Cross Product	9
	The 3D Triple Product	11
	Geometric Applications	13
	Lines	13
	Distance of a Point to a Line	13
	Summary	15
	Exercises	16

Algorithms
1.	Area of Triangles and Polygons (2D & 3D)
	Area of Triangles
	Area of Quadrilaterals
	Area of Polygons
	2D Polygons
	3D Planar Polygons
2.	About Lines and Distance of a Point to a Line (2D & 3D)
	About Lines
	Line Equations
	Distance of a Point to an Infinite Line
	Distance of a Point to a Ray or Segment
3.	Fast Winding Number Inclusion of a Point in a Polygon (2D)
	The Crossing Number
	The Winding Number
4.	About Planes and Distance of a Point to a Plane (3D)
	About Planes
	Plane Equations
	Computing Parametric Coordinates
	Distance of a Point to a Plane
5.	Intersections of Lines, Segments and Planes (2D & 3D)
	Line and Segment Intersections
	Plane Intersections
	Line-Plane
	2 Planes
	3 Planes
6.	Intersections of Rays, Segments, Planes and Triangles in 3D
	Ray/Segment-Plane Intersection
	Ray/Segment-Triangle Intersection
	Triangle-Plane Intersection
	Triangle-Triangle Intersection
7.	Distance between Lines, Segments and the Closest Point of Approach (2D & 3D)
	Distance between Lines
	Distance between Segments and Rays
	Closest Point of Approach (CPA)
8.	Bounding Containers for Polygons, Polyhedra and Point Sets (2D & 3D)
	Linear Containers
	The Bounding Box (and Diamond)
	The Convex Hull
	The Minimal Rectangle
	Quadratic Containers
	The Bounding Ball (and a Fast Approximation)
	The Bounding Ellipsoid
9.	The Intersections for a Set of 2D Segments, and Testing Simple Polygons
	The Bentley-Ottmann Algorithm
	The Shamos-Hoey Algorithm
	Testing Simple Polygons
	Polygon Set and Planar Subdivision Operations
10.	The Convex Hull of a 2D Planar Point Set or Polygon
	The "Graham Scan" Algorithm
	Andrew's Monotone Chain Algorithm
11.	A Fast Approximate 2D Convex Hull Algorithm
	The BFP Approximate Hull Algorithm
12.	Intersection of a Segment with a Convex 2D Polygon or 3D Polyhedron
	Intersect Segment and 2D Polygon
	Intersect Segment and 3D Polyhedron
13.	Extreme Points of Convex Polygons and Distance of a Polygon to a Line (2D)
	Polygon Extreme Point Algorithms
	Binary Search of a Convex Polygon
	Distance of a Polygon to a Line
14.	Tangents to and between Polygons
	Tangents from a Point to a Polygon
	Tangents between Two Polygons
15.	Convex Hull of a 2D Simple Polyline
	Background
	The Basic Incremental Strategy
	The Melkman Algorithm
16.	Polyline Simplification
	The Vertex Reduction Algorithm
	The Douglas-Peucker Algorithm
17.	C++ Point and Vector Class (includes DOWNLOAD)
	Point Class API
	Parameters
	Constructors
	Operators
	Methods
	Vector Class API
	Parameters
	Constructors
	Operators
	Methods