This book is an interactive introduction to some of the fundamental algorithms of computational geometry.
In a conventional paper-based textbook these algorithms are either presented as narrative, in pseudo code or in a language such as C or Java. Often (but not always) there is a separate code base that the reader can download and use. However, in this book, the code base, which is in the Wolfram Language, is integrated into the text, and is fully executable. We are no longer limited to a static description of algorithms; we present functioning, executing code that implements and demonstrates these algorithms.
We have found that a good interactive demonstration can replace an extraordinary amount of text. Furthermore, whereas a textual (and to a lesser extent, pseudo code) description of an algorithm may be subject to the ambiguity of natural language, the demonstration is unambiguous because it is the algorithm in action.
This book is delivered as an interactive CDF (Computable Document Format) file that you can view in the free CDF Player available from Wolfram, or, you can open it in Mathematica. All the code is executable and readers are encouraged to have a copy of Mathematica in order to get the most out of this text. Contents
Table of contents
Introduction: About this book, Interactivity, The code, The structure of the text, Who this book is for, The Wolfram Language, Conventions, Clearing the namespace, Some useful graphics functions, Calculate an offset from a point, Label vertexes v1, v2, ... , vn, Label points arbitrarily (defaults to 3 vertexes, a, b, c), Standard graphical style
Chapter 1 - points and lines: Points, Query functions, Indexes and vertexes, Random point sets, Extreme points of a point set, Lines and line segments, Approximating lines and rays
Chapter 2 - polygonal chains: Polygonal chains in 2D, Simple polygonal chains, Monotone polygonal chains
Chapter 3 - triangles and the relationship of points to lines: A triangle is a three sided polygon, Representing polygons in the Wolfram Language, Triangles, Signed area of a triangle, Triangles and the relationships of points to lines, The centroid, medians and circumcircle of a triangle, The internal angles of a triangle, Triangulating a triangle with an internal point, Random triangles
Chapter 4 - polygons: Polygon navigation, Polygon edges, Regular polygons, Regular star polygons, Monotone mountain polygons, Random polygons, Random simple star shaped polygons, Choosing an origin, Sorting anti-clockwise using trig functions (slow), Sorting anti-clockwise without using trig functions (fast), The randomSimpleStarShapedPoly function, Area of a polygon, Convex polygon triangulation, General polygon areas
Chapter 5 - intersections: The relationship of points to convex polygons, Point inside convex polygon, Intersection of lines with lines,edges and polygons, Proper intersection, Improper intersection, Intersection, Polygon intersection, Summary of types of intersection, Polygon extreme points, Monotone polygons, Tangent to a convex polygon from a point, Splitting a convex polygon into polygonal chains
Chapter 6 - convex hulls: Convex hull, Incremental convex hull algorithm, Graham scan convex hull algorithm, The performance of the convex hull algorithms
Chapter 7 - polygon triangulations: General polygon triangulation, Polygon diagonals, Finding polygon diagonals, Triangulation by ear tip removal
Chapter 8 - point set triangulation and dual graph: Point set triangulation, Incremental point set triangulation, Simple incremental triangulation with convex hull, Finding the triangles for an edge in a triangulation, The dual graph of a triangulation
Chapter 9 - Delaunay triangulation: Delaunay triangulation, Flipping diagonals, Convert a triangulation to a Delaunay triangulation, Delaunay triangulations and terrain
Chapter 10 - Voronoi diagrams Summary Bibliography Related Topics