Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Interactive Computational Geometry, A Taxonomic Approach

Jim Arlow
Book information

Publisher: Clear View Training
Copyright year: 2014
ISBN: 9780957292826
Medium: CDF
Includes: CDF
Out of print?: N
Buy this book
Book cover image

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

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.

*Mathematics > Geometry
*Mathematics > Geometry > Computational Geometry