Interactive Computational Geometry Second Edition
Author
Dr. Jim Arlow
Title
Interactive Computational Geometry Second Edition
Description
Interactive Computational Geometry Second Edition collection: 0 notebooks
Category
Books & Supplements
Keywords
geometry, computational geometry, Delaunay, Voronoi, dual graph, graph, polygon, triangulation
URL
http://www.notebookarchive.org/2019-01-8aukd4r/
DOI
https://notebookarchive.org/2019-01-8aukd4r
Date Added
2019-01-18
Date Last Modified
2019-01-18
File Size
2.25 megabytes
Supplements
Rights
Redistribution rights reserved
This notebook is optimized for desktop only.
Download
Open in Wolfram Cloud
Interactive Computational Geometry
Interactive Computational Geometry
A Taxonomic Approach
Second Edition
(Wolfram Language)
(Wolfram Language)
Dr. Jim Arlow
THIS BOOK CONTAINS SOFTWARE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
THIS BOOK CONTAINS LIVE CODE. BE SAFE AND EXAMINE ALL CODE BEFORE EXECUTING IT. ONLY USE COPIES OF THIS BOOK OBTAINED LEGITIMATELY FROM WWW.CLEARVIEWTRAINING.COM OR THE WOLFRAM NOTEBOOK ARCHIVE.
THIS BOOK CONTAINS LIVE CODE. BE SAFE AND EXAMINE ALL CODE BEFORE EXECUTING IT. ONLY USE COPIES OF THIS BOOK OBTAINED LEGITIMATELY FROM WWW.CLEARVIEWTRAINING.COM OR THE WOLFRAM NOTEBOOK ARCHIVE.
Table of contents
◼
Table of contents
◼
Introduction
◼
About this edition
◼
Our approach to computational geometry
◼
Audience
◼
About the code
◼
This book and the Wolfram Language
◼
Conventions
◼
Using the online documentation
◼
Getting started - clearing the namespace
◼
Essential utility functions
◼
Chapter 1: Points and lines
◼
Points
◼
Query functions for points
◼
Point list indexes and vertexes
◼
Random point sets
◼
Extreme points of a point set
◼
Lines and line segments
◼
Approximating lines and rays
◼
Summary
◼
Chapter 2: Polygonal chains
◼
Polygonal chains in 2D
◼
Simple polygonal chains
◼
Monotone polygonal chains
◼
Summary
◼
Chapter 3: Triangles, and the relationship of points to lines
◼
Defining a triangle
◼
Representing polygons in the Wolfram Language
◼
Triangles
◼
Signed area of a triangle
◼
2D triangle area by determinants
◼
Triangles and the relationships of points to lines
◼
Collinearity and general position
◼
Between
◼
Testing the point/line relationship functions
◼
Relationship between a list of points and a line
◼
Points on the same side of a line
◼
Summary
◼
Chapter 4: Triangle geometry
◼
The centroid, medians and circumcircle of a triangle
◼
The internal angles of a triangle
◼
Triangulating a triangle on an internal point
◼
Random triangles
◼
Summary
◼
Chapter 5: Polygons
◼
Polygon vertex navigation
◼
Polygon edges
◼
Regular polygons
◼
Regular polygons with integer vertexes
◼
Regular star polygons
◼
Monotone mountain polygons
◼
Area of a polygon
◼
Convex polygon area by triangulation
◼
General polygon areas
◼
Number of triangulations of a convex polygon
◼
Summary
◼
Chapter 6: Random polygons
◼
Random polygons
◼
Random simple star shaped polygons
◼
The randomStarShapedPoly[...] function
◼
Summary
◼
Chapter 7: Intersections
◼
Testing for polygon convexity
◼
Point inside convex polygon
◼
Intersection of line segments with line segments and polygons
◼
Proper intersection of line segments
◼
Improper intersection of line segments
◼
Intersection of line segments
◼
Polygon intersection with line segments
◼
Polygon self-intersection
◼
Demonstration of line segment intersection types
◼
Summary
◼
Chapter 8: Polygon extreme points, tangents, monotonicity and splitting
◼
Polygon extreme points
◼
Monotone polygons
◼
Tangent to a convex polygon from a point
◼
Splitting a convex polygon into polygonal chains
◼
Summary
◼
Chapter 9: Convex hulls
◼
Incremental convex hull algorithm
◼
Graham scan convex hull algorithm
◼
Comparison of incremental and Graham scan convex hull functions
◼
Summary
◼
Chapter 10: General polygon triangulation
◼
Polygon diagonals
◼
Finding polygon diagonals
◼
Polygon triangulation by ear tip removal
◼
Plotting triangulations
◼
Summary
◼
Chapter 11: Point set triangulation and the dual graph
◼
Incremental point set triangulation algorithm
◼
Simple incremental point set triangulation with convex hull
◼
Finding the triangles for an edge in a triangulation
◼
The dual graph of a triangulation
◼
Analysing a triangulation using graph theory
◼
Visibility graph of a polygon
◼
Summary
◼
Chapter 12: Delaunay triangulation
◼
Assessing triangulations
◼
The angle vector of a triangulation
◼
The Delaunay triangulation
◼
Flipping diagonals
◼
Converting a triangulation to a Delaunay triangulation
◼
Delaunay triangulation example
◼
Delaunay triangulations and terrain
◼
Summary
◼
Chapter 13: Voronoi diagrams
◼
A Voronoi diagram algorithm
◼
Summary
◼
Chapter 14: Summary
◼
Resources
◼
Bibliography
Introduction
This book is an introduction to some of the fundamental algorithms of computational geometry. The emphasis in this book is on three things:
◼
Explanation
◼
Implementation
◼
Demonstration
We explain key concepts in computational geometry, implement them in the Wolfram Language, then provide demonstration programs that illustrate how they work. Our aim is that this book should act as a complement to existing books on computational geometry. This means that we generally don't cover mathematical proofs because these are already covered very satisfactorily elsewhere (see the Bibliography). A key inspiration for this book are the two computational geometry textbooks by Joseph O’Rourke (listed in the bibliography), and we recommend you study these in conjunction with this text.
We hope you find this text valuable and that it helps you in your work, whatever that may be. Visit us at www.cleraviewtraining.com to see the other books we have available.
About this edition (important - don’t skip!)
About this edition (important - don’t skip!)
This ebook book comes in two physical parts. The first part is a PDF available from Amazon (n.b. if you have Kindle Unlimited, you can get it for free). The PDF is not interactive due to technical limitations of the PDF platform. However, it can be read on any device that supports PDF, and is a very useful reference-only version of the book for those occasions when you don’t have Mathematica or the Wolfram Player available. It makes the book available to a wider audience.
The second part is a free Mathematica Notebook available from the Wolfram Notebook Archive (search on “Arlow”). This is more or less identical to the PDF, except that it is fully executable. This Notebook provides functioning, executing code that implements and demonstrates computational geometry algorithms directly. There is nothing better than seeing an algorithm in action, and a good, interactive, demonstration can replace an extraordinary amount of text. Also, whilst a textual (and to a lesser extent, pseudo code) description of an algorithm may be subject to the ambiguity of natural language, live code is the algorithm executing.
In terms of running the Notebook, you will need either Mathematica or the free Wolfram Player. The notebook currently won’t run in the Wolfram Cloud because of some technical limitations on Cloud graphics that we are working with Wolfram Research to resolve. This also means that when you view the Notebook on the Wolfram Archive, you will see only a static image, and it will not execute there. Running the book in Mathematica allows you to play about with the code in any way you want, whereas the free Wolfram Player gives you the full interactive experience, but without the ability to change the code.
If you are reading the book as a static PDF, please note that we have maintained the same layout as the Mathematica Notebook. This means that we have been very generous with space when laying out the pages. In particular, we arrange pages to always try to keep code blocks together, and keep them with their output if possible. This means that there is quite a lot of whitespace on some pages. This is intentional, and as there is no printed version of this text, no trees are harmed by this extravagance.
If you are a Python programmer, you are in luck! You can get a version of this text written entirely in Python using Jupyter Notebooks. The Python version is written in idiomatic Python, so it uses object orientation to advantage to simplify some of the geometric objects and algorithms. If you wish to port the algorithms to another object oriented language such as Java, then the Python version of the text will be the one you want. Note that we do our best to keep the content of the Python and Mathematica versions in synchronisation, but because they are developed separately, there may be some small differences.
Our approach to computational geometry
Our approach to computational geometry
Computational geometry is most commonly approached from a problem based perspective, where geometric problems are presented and algorithms are developed to solve them. This is a very appropriate strategy and we list several excellent texts in the bibliography that already do this very well.
Because these resources exist, it has allowed us to take a different approach, which complements them. We have structured the text according to taxonomic principles: we examine the key geometrical objects that one is concerned with in computational geometry, and then we look at the key algorithms that apply to them. This has the advantage that the objects and algorithms become organized in a way that is easy to reference, understand and learn. It also fits nicely with developing a codebase because the simplest objects occur first, and the more complex objects build on them. Using this approach, we can build up quite an extensive code base in a systematic way as we go along.
Every taxonomy requires a clearly stated organizational principle or principles. The taxonomic principle we use is that of constraints. For example, a line segment would be considered to be a more constrained type of line because it has two end points, whereas a line is infinite and has no end points. As you will see, this simple principle allows us to group geometric objects in a very meaningful way.
Audience
Audience
The book is (obviously) for anyone interested in computational geometry. Probably the primary audiences for this book are undergraduates or post-graduates doing a course that involves computational geometry in some form. Given that the field of computational geometry covers such a wide area (graphics, robotics, geographical information systems, etc.) this is potentially quite a broad range of readers.
We also expect that this book can be very useful to lecturers in computational geometry as a source of demonstrations for their students. We naturally hope that in return, they might recommend this book as a course book, or at least attribute the demonstrations to this text.
Apart from educational uses, the book provides a very useful catalog of key computational geometry algorithm implementations for programmers. Because the algorithms are expressed in a concise, functional, style, they are easy to understand and port to other languages, especially functional ones.
Although this book is not designed as a tutorial on the Wolfram Language, we feel that when combined with the excellent on-line Wolfram Language documentation and tutorials, it could be used as such by the experienced programmer.
About the code
About the code
There are three distinct types of code in this text:
◼
Code which supports the text - this is code that creates a diagram or illustrates a feature of the Wolfram Language. It is not part of a computational geometry algorithm.
◼
Code that implements a computational geometry algorithm - this code is developed in a logical way and is embedded in a narrative description of the algorithm and its implementation details. This is a Literate Programming approach that lends itself very well to an interactive text such as this.
◼
Interactive demonstrations - this code provides graphical demonstrations of the algorithms. The aim is to demonstrate what an algorithm does or how an algorithm works in an interactive, visual way that is easy to understand. By playing with these demonstrations directly you will gain a better understanding of the algorithms.
We have found that it is not necessary to distinguish these three types of code typographically - as you read the book, you will find that it is always completely clear from the context what kind of code you are looking at.
This book and the Wolfram Language
This book and the Wolfram Language
If you are reading this book, you may already have some familiarity with the Wolfram Language. If you are new to the language, then you are in for a mind-expanding treat!
The first edition of this book was written in 2014, and would not have been possible without the Wolfram Language and the Computational Document Format (CDF). CDF was a format for executable documents that comprise text, graphics and executable code that has (sadly) now been deprecated. To develop an interactive book such as this in Java, C, Python etc. would have involved creating a publishing platform for executable books similar to CDF and would have been prohibitively difficult, time consuming and expensive at that point in time.
In 2020, the world has moved on quite a lot, and other languages have begun to catch up with the Wolfram Language - at least in some areas! In particular, there is an excellent facility for Python called Jupyter Notebooks, that provides an executable document platform, similar in some respects to CDF, that is more than adequate for a book such as this, and as we mentioned earlier, this has allowed us to rewrite this book entirely in Python. The book is called “Interactive Computational Geometry in Python”, and you can find it at www.clearviewtraining.com. (Note: If you want to know how to write a whole book in Jupyter, take a look at our SlideShare presentation.)
Getting back to the Wolfram Language, it is a very high-level symbolic language that allows the same focus on algorithmic structure as pseudo code, and yet is as executable as C. In the past, it has been primarily known as the language of Mathematica, but it actually goes much further than this, and Mathematica is really only one particular use case for this uniquely powerful and elegant language. For example, the Wolfram Language has also made possible innovations such as Wolfram Alpha and Siri. In fact, it is such a powerful language that our use of it here is trivial.
The very high-level of the Wolfram Language, drastically reduces the amount of boilerplate code and allows you to focus on what the algorithm actually needs to do, whilst leaving how it actually does it to the implementation details of the language. As such, we can have the best of both worlds - the readability of pseudo code and the executability of C, Java, Python, etc. Python is also a very powerful and flexible language, and if you compare the code in this book with the Python code in Interactive Computational Geometry in Python, you will see that we have achieved a similar effect, but by using the object-oriented features of Python to build a high level language in which to express the algorithms.
The Wolfram language is a multi-paradigm language. This means that you can program it in procedural, object-oriented (with some difficulty), functional, rules-based and other programming styles. We believe that the most natural style for the majority of computational geometry algorithms is functional, and this is hardly surprising because so much of mathematics is about functions. The functional style we have adopted here is clean, easy to read, very concise and very expressive. We hope you agree with us after working through this text! Although the functional programming style allows us to express most algorithms very simply, sometimes other paradigms, such as procedural, are clearer or more appropriate, and the language allows us to mix and match to best advantage.
What do we mean when we say that the Wolfram Language is a “symbolic” language? This means that we are not restricted to working only with entities such as ints, floats, structs, objects, etc. - we can work with pure symbols that have no assigned value or meaning. For example we can add three emoji symbols together and get a sensible answer:
In[]:=
☺+☺+☹
Out[]=
2☺+☹
We take advantage of symbol processing at several points in the text where we let the Wolfram Language perform algebraic manipulations for us.
Another powerful feature of the language is advanced pattern matching. We use this facility to identify geometric objects and apply a kind of “type safety” to our functions by specifying patterns that the function parameters have to match. You will see plenty of examples of this shortly.
Conventions
Conventions
We have very few conventions in this book:
◼
Mathematica Notebooks have different types of cell. All code will be inside a code cell, and these cells are executable. For example:
In[]:=
1+2
Out[]=
3
◼
New function and variable names introduced in this text will be in lowerCamelCase and look like this:
In[]:=
someNewFunctionInTheGlobalNamespace[]:="Hello World"
In[]:=
someNewFunctionInTheGlobalNamespace[]
Out[]=
Hello World
◼
Wolfram Language built-in function and variable names are in UpperCamelCase (e.g. TrueQ below). Functions that return a Boolean value (True or False) are post fixed by Q (this is a standard naming convention in Lisp-like languages) e.g.
In[]:=
isTrueExampleQ[x_]:=TrueQ[x]
In[]:=
isTrueExampleQ[True]
Out[]=
True
In[]:=
isTrueExampleQ[False]
Out[]=
False
◼
Equations are:
inthisfont
y=
2
x
◼
Definitions may be indented to indicate taxonomic relationships and look like this:
Line: a straight one-dimensional figure having no thickness and extending infinitely in both directions.
Ray: a straight one-dimensional figure having no thickness, beginning at a point and extending infinitely in one direction.
◼
Indexes vs. points - most functions return lists of points, but some return lists of indexes into a pre-existing list of points. The name of any function that returns indexes will be post fixed by Index.
Using the online documentation
Using the online documentation
The Wolfram Language comes with extensive online documentation in the Wolfram Language & System Documentation Center. When you see a built-in function, and you don’t know what it does, you can look it up online. Remember that all function names that begin with a capital letter are built-in Wolfram Language functions, and you can find complete descriptions of these Wolfram Language & System Documentation Center. You might want to check it out now, before you get into the book.
Getting started - clearing the namespace
Getting started - clearing the namespace
The first thing we have to do is to set up the Wolfram Language to execute the examples in the rest of this text. When we define a symbol in the global namespace of the Wolfram Language, that symbol is there for the whole session. This can lead to unexpected results, so it is a good idea to begin with a call to ClearAll[...] in order to purge the namespace of unwanted values:
In[]:=
ClearAll["Global`*"]
Essential utility functions
Essential utility functions
We are going to be making heavy use of graphics, so it makes sense to define some useful graphics functions up front. These functions must be used within the Wolfram Language Graphics[...] function as we will see shortly. Just take these functions as read for now - they operate on data structures that we have yet to define, and you will soon see examples of them in action. So if you don’t understand these functions now, don’t worry, just proceed with the rest of the text and come back to them later.
Calculate an offset from a point for a label:
Calculate an offset from a point for a label:
In[]:=
offsetLabel[{x_,y_},offset_]:={x,y}+{If[Sign[x]0,1,Sign[x]],If[Sign[y]0,1,Sign[y]]}*offset
Label polygon vertexes v1, v2, ... vn:
Label polygon vertexes v1, v2, ... vn:
In[]:=
polyVertexLabels[poly_List,offset_List:{0.4,0.4}]:=MapIndexed[Text[Style[Row[{"v",#2[[1]]}],14],offsetLabel[#1,offset]]&,poly]
Label points arbitrarily (defaults to 3 vertexes, a,b,c):
Label points arbitrarily (defaults to 3 vertexes, ):
a,b,c
In[]:=
pointLabels[points_List,labels_List:{"a","b","c"},offset_List:{0.4,0.4}]:=MapIndexed[Text[Style[labels[[#2[[1]]]],14],offsetLabel[#1,offset]]&,points]
Label points with their coordinates:
Label points with their coordinates:
In[]:=
pointCoordLabels[poly_List,offset_List:{0.4,0.4}]:=MapIndexed[Text[Style[#1,14],offsetLabel[#1,offset]]&,poly]
Standard graphical style:
Standard graphical style:
Throughout this text, we will be making a lot of plots. We will generally do so on a 10x10 grid, because that is just about the size right for the interactive demonstrations. Here is a standardPlotStyle defined as a List of key value pairs that gives us a consistent look and feel for the plots:
In[]:=
standardPlotStyle:={AspectRatio1,AxesTrue,FrameTrue,AxesOrigin{0,0},GridLines{Range[-6,6],Range[-6,6]},PlotRange{{-6,6},{-6,6}}}
Printing out examples:
Printing out examples:
This utility function takes a Wolfram Language expression, and returns a List where the first element is the unevaluated expression (in Wolfram Language terminology, the form of the expression), and the second element is the result of evaluating the expression. This is useful for constructing tables of examples that show a particular form and then the result of evaluating it.
In[]:=
formValue[exp_]:={HoldForm[exp],exp}formValue[comment_,exp_]:={comment,HoldForm[exp],exp}SetAttributes[formValue,{HoldAll,Listable}]
In the Wolfram Language, functions can have attributes that specify their properties. In this case, we give the formValue[...] function the attribute HoldAll, which means that it does not immediately evaluate its arguments, and Listable, which means that the function will be automatically applied to each element when given a List of arguments. In that case it will return a List of results.
We will almost always use formValue[...] to create a table of results, so here is a convenience function to encapsulate that:
In[]:=
gridFormValue[exp_]:=Grid[formValue[exp],FrameAll,AlignmentLeft]SetAttributes[gridFormValue,{HoldAll}]
For example:
In[]:=
gridFormValue[{1+1+2,2+2+3,3+3+4,++}]
Out[]=
1+1+2 | 4 |
2+2+3 | 7 |
3+3+4 | 10 |
++ | 2+ |
Chapter 1: Points and lines
Chapter 2: Polygonal chains
Chapter 3: Triangles, and the relationship of points to lines
Chapter 4: Triangle geometry
Chapter 5: Polygons
Chapter 6: Random polygons
Chapter 7: Intersections
Chapter 8: Polygon extreme points, tangents, monotonicity and splitting
Chapter 9: Convex hulls
Chapter 10: General polygon triangulation
Chapter 11: Point set triangulation and the dual graph
Chapter 12: Delaunay triangulation
Chapter 13: Voronoi diagrams
Chapter 14: Summary
Resources
Bibliography
Cite this as: Dr. Jim Arlow, "Interactive Computational Geometry Second Edition" from the Notebook Archive (2018), https://notebookarchive.org/2019-01-8aukd4r
Download
