Practical Geometry Algorithms: With C++ Code

COVER
TITLE PAGE
COPYRIGHT PAGE
TABLE OF CONTENTS
PREFACE
INTRODUCTION
LINEAR ALGEBRA
	NOTATION
	COORDINATE SYSTEMS
	POINTS AND VECTORS
		Basic Definitions
		Vector Addition
		Scalar Multiplication
		Affine Addition
		Vector Length
	VECTOR OPERATIONS
		Determinants
		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
			Standard Formula
			Quadrilateral Decomposition
			Projection to 2D
	IMPLEMENTATIONS
	REFERENCES
LINES
	LINE EQUATIONS
	DISTANCE FROM A POINT TO A LINE
		The 2-Point Line
		The 2D Implicit Line
		The Parametric Line
	DISTANCE FROM A POINT TO A RAY OR SEGMENT
	IMPLEMENTATIONS
	REFERENCES
POINT IN POLYGON
	THE CROSSING NUMBER
		Edge Crossing Rules
	THE WINDING NUMBER
	ENHANCEMENTS
		Bounding Box or Ball
		3D Planar Polygons
		Convex or Monotone Polygons
	IMPLEMENTATIONS
	REFERENCES
PLANES
	PLANE EQUATIONS
		Implicit Equation
			Normal Implicit Equation
		Parametric Equation
		Barycentric Coordinates
		Representation Conversions
			Barycentric Coordinate Computation
	DISTANCE OF A POINT TO A PLANE
	IMPLEMENTATIONS
	REFERENCES
LINE, SEGMENT, AND PLANE  INTERSECTIONS
	LINE AND SEGMENT INTERSECTIONS
		Parallel Lines
		Non-Parallel Lines
	PLANE INTERSECTIONS
		Intersection of a Line and a Plane
		Intersection of 2 Planes
		Direct Linear Equation
		Line Intersect Point
		3 Plane Intersect Point
		Intersection of 3 Planes
	IMPLEMENTATIONS
	REFERENCES
RAY 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
	IMPLEMENTATIONS
	REFERENCES
DISTANCE BETWEEN LINES
	DISTANCE BETWEEN LINES
		Distance between Segments and Rays
	CLOSEST POINT OF APPROACH (CPA)
	IMPLEMENTATIONS
	REFERENCES
INTERSECTIONS FOR  A SET OF SEGMENTS
	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
	IMPLEMENTATIONS
	REFERENCES
BOUNDING CONTAINERS
	LINEAR CONTAINERS
		The Bounding Box
		The Bounding Diamond
		The Convex Hull
		The Minimal Rectangle
	QUADRATIC CONTAINERS
		The Bounding Ball
			A Fast Approximate Ball
		The Bounding Ellipsoid
	IMPLEMENTATIONS
	REFERENCES
CONVEX HULL OF  A PLANAR POINT SET
	CONVEX HULLS
	2D HULL ALGORITHMS
		The \"Graham Scan\" Algorithm
		Andrews Monotone Chain Algorithm
	IMPLEMENTATIONS
	REFERENCES
CONVEX HULL APPROXIMATION
	THE BFP APPROXIMATE HULL ALGORITHM
		Error Analysis
	IMPLEMENTATIONS
	REFERENCES
CONVEX HULL OF  A SIMPLE POLYLINE
	BACKGROUND
	SIMPLE POLYLINE HULL ALGORITHMS
		The Basic Incremental Strategy
		The Melkman Algorithm
	IMPLEMENTATIONS
	REFERENCES
LINE AND CONVEX POLYTOPE INTERSECTION
	INTERSECT A SEGMENT AND A 2D CONVEX POLYGON
	INTERSECT A SEGMENT AND A 3DCONVEX POLYHEDRON
	IMPLEMENTATIONS
	REFERENCES
EXTREME POINTS OF  CONVEX POLYGONS
	POLYGON EXTREME POINT ALGORITHMS
		Brute Force Search
		Binary Search
	DISTANCE OF A POLYGON TO A LINE
	IMPLEMENTATIONS
	REFERENCES
POLYGON TANGENTS
	TANGENTS: POINT TO POLYGON
		Brute Force
		Binary Search
	TANGENTS: POLYGON TO POLYGON
		Brute Force
		Linear Search
		Binary Search
	IMPLEMENTATIONS
	REFERENCES
POLYLINE DECIMATION
	OVERVIEW
	VERTEX CLUSTER REDUCTION
	THE DOUGLAS-PEUCKER ALGORITHM
		Convex Hull Speed-Up
	IMPLEMENTATIONS
	REFERENCES
C++ CODE INDEX
	PRIMITIVE FUNCTIONS
	APPLICATION FUNCTIONS