|
|
Description
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 Geometry |
|
|
