Note: As of 22 August 2014, we are in a transitional period between Mathematica 9 and Mathematica 10. The book is written for Mathematica 10, but I have tested it with both Mathematica 9 and Player 9. There are three self-contained Mathematica 10 specific demonstrations, and these will not work in version 9. They do not detract from the rest of the text in any way.
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.
There is nothing quite like seeing an algorithm in action. 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, if you have access to Mathematica, we encourage you to play about with it, either by working on a copy of this text, or by cutting and pasting snippets into a new Mathematica Notebook. In fact, to get the most from this text, you really should have a copy of Mathematica!
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