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 SOFTWARE OBTAINED LEGITIMATELY FROM WWW.CLEARVIEWTRAINING.COM.
Note: if you are having trouble displaying the graphics, your display might not have a high enough resolution. You can fix this by commenting out the following line that you will find in the second cell at the top of each file:
# Comment out the line below if the graphics do not display
%config InlineBackend.figure_format = 'retina'
This book is an interactive introduction to some of the fundamental algorithms of computational geometry. We present functioning, executing code that implements and demonstrates computational geometry algorithms. The emphasis in this book is on three things:
Explanation
Implementation
Demonstration
We explain key concepts in computational geometry, implement them in Python, 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).
In a conventional paper-based textbook 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 codebase that the reader can download and use.
This book is different. It is supplied as several Jupyter notebooks in which the code is integrated with the text. These notebooks are executable. All you have to do is download a suitable Jupyter environment (more on this shortly!) and you can run the examples. Furthermore, there are a set of Python modules that you can include in your own programs if you want to use this code elsewhere.
There is nothing better than 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 running algorithm.
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. This is another reason why we think this book provides an excellent complement to other more problem and proof oriented texts. The taxonomic approach allows us to build up a computational geometry codebase in a step by step manner where each chapter builds on the next.
The taxonomic principle we use is that of constraint. For example, a line segment would be considered to be a type of line because it has two end points, whereas a line has no end points - the line segment is more constrained than the line. This principle allows us to organize many geometric objects in an intuitive way.
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.
Probably the primary audiences for this book are undergraduates or post-graduates doing a course that involves computational geometry. 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 expect that this book can also be 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 in Python. Because the algorithms are expressed in a concise style, they are easy to understand and port to other languages.
Although this book is not designed to be a tutorial on Python or Jupyter notebooks, we think that when combined with the excellent on-line documentation and tutorials that are readily available, it could be used as such by the experienced programmer. Because of the high readability of Python, most of the code in this book should be pretty obvious to anyone who has some background in programming.
Note that this is a copyrighted work, and may not be distributed freely without the prior consent of the publisher Clear View Training Limited. Contact us for details.
This book is distributed as a number of Jupyter notebooks, one for each chapter, called "ICGChapterXX.ipynb". You should read these chapters in order because each builds on the one before.
Jupyter is a way of combining Python (and other languages) and rich text, including mathematical equations, into objects called notebooks. The idea goes back quite a long way. Perhaps the earliest example is the Smalltalk workspace, in which code and text could be freely mixed. You can find an implementation of this for the Ruby programmer on our website here: Ruby Workspaces. Perhaps the most refined execution of the idea is the Mathematica notebook in which Wolfram Language code, rich text and interactive graphics may be freely combined.
In a Jupyter notebook, the output of executing Python code is embedded in the notebook itself. So when you run one of the many demonstration programs in this book, you will see the output right there, on the same page as the code. This is a very powerful idea. It is used very widely in data science, where live data can be embedded in scientific papers, but it also lends itself quite naturally to the production of interactive textbooks such as this one.
You don't need to know much about Jupyter to use this text, but we recommend that you work through the very short tutorial here:
Click on "Welcome to Python.ipynb" and follow the instructions.
The tutorial: What just happened? Jupyter is a client-server system and a temporary notebook server was launched for you on a Rackspace host. You were able to execute some Python code by selecting a code cell and typing "shift-Enter". The code was passed to the server, executed in a Jupyter kernel and the result passed back to the browser. Note that this particular host doesn't live very long - so don't think you can come back to it much later and execute the code again - you may need to start again at https://try.jupyter.org to get a new server instance.
In order to execute the notebooks on your own Jupyter environment, see Running the notebooks below.
The Jupyter notebook is a sequence of cells. Pressing "Shift-Enter" will execute a cell. As far as we are concerned, there are four types of cell:
Markdown cells - these allow you to create rich text using the Markdown language. You can find details of the Markdown language here: https://daringfireball.net/projects/markdown/syntax. Markdown cells can also contain HTML and mathematical equations written using LaTeX syntax: https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols. When Markdown cells are executed, they generate rich text.
Code cells - these cells usually contain Python. There is some support for other languages, but that doesn't concern us here. When these cells are executed, the Python code is run and the output appears in an output cell.
Output cells - in fact, these are appended to the bottom of code cells, and contain the result of running them.
Demo cells - a new type of cell that we have introduced.
For the purposes of this text, we have introduced the Demo cell. This is a code cell whose first line is "#Demo" and whose last line is also "#Demo". Cells can have a variety of metadata attached, and we give these cells the special tag DEMO. We use a preprocessor (itself a Jupyter notebook) to skip over these cells and generate the reusable Python code for each chapter. The Demo cells contain interactive demonstrations and illustrations that only make sense within the context of the chapters. They are not reusable and so we never need to export them to a Python file.
To run the chapter notebooks, you first need to install a Jupyter environment. We recommend Anaconda. We wrote this book entirely in the Anaconda environment and it works perfectly on Mac, Linux and Windows. In our experience, Anaconda is the easiest and best way to set up a Python environment for scientific and mathematical programming. Setting up a Python environment to run these notebooks without using Anaconda is a challenging proposition that is not to be undertaken lightly! Given the diversity of platforms and library versions involved, we can't even offer any help with this.
You can download the latest Anaconda distribution here:
https://www.anaconda.com/distribution/
You need the Python 3.6 version
Note: The specific version we developed on is Anaconda 5.0.1 but it should work with later versions as well. If it doesn't then you can download Anaconda 5.0.1 here:
Installation of Anaconda is generally very straightforward. On Mac and Linux and you can normally go ahead and just take the default options and everything will just work.
If you are on Windows, you should read this FAQ before installation:
https://docs.anaconda.com/anaconda/faq
In particular, read "In what folder should I install Anaconda on Windows?" and "Should I add Anaconda to the Windows PATH?".
If you accept the default option to install Anaconda on the “default path” Anaconda is installed in your user home directory:
| Platform | default path |
|---|---|
| Windows 10 | C:\Users\your-username |
| macOS | /Users/your-username |
| Linux | /home/your-username |
NOTE: If your-username includes spaces, as is common on Windows systems, you should not accept the default path and you must install Anaconda in another directory whose name contains only 7-bit ASCII characters and no spaces. See the FAQ, "In what folder should I install Anaconda on Windows?".
When you start the Jupyter server it will serve notebooks from the default path.
Take the book zip file and uncompress it into a subdirectory of the default path so that the Jupyter notebook server can find it easily.
Launch Anaconda Navigator.
You will see an Anaconda Navigator window with several tiles for different data science tools. Click the "Launch" button on the Jupyter tile. This will run a Jupyter notebook server and open a file selector in your browser on the default path (usually /Users/your-username).
Open one of the notebooks from the book.
When the notebook has launched go to the menu bar and click on "Help/User Interface Tour" for help on using the notebooks. You will find it is very straightforward.
Please note the following:
Be safe and examine all code before executing it.
The notebooks must be "Trusted" to work properly. There is an option to trust a notebook on the right hand side of the notebook menu bar.
The code cells in each notebook need to be executed in order from top to bottom because of dependencies in the Python code. Select "Cell/Run All" or "Shift-Enter" each code cell as you come to it.
"Shift-Enter" a code cell to re-run it.
If you have any difficulties, it might be necessary to restart the kernel. Select "Kernel/Restart & Run All".
You can start the Jupyter notebook server from any directory by opening a command prompt there and executing:
jupyter notebook
This works very well on Mac and Linux, and can be more convenient than having to launch Anaconda Navigator.
On Windows, Anaconda will not normally be on your path, and you will not be able to execute the jupyter command. However, all is not lost! Go into "Start Menu"/"All Programs"/"Anaconda3" and open "Anaconda Prompt". This will give you a command prompt with the paths set appropriately.
All the algorithms are implemented in Python 3. All sorce code, including that embedded in the Jupyter notebooks is provided under the GNU GPLv3 license.
Python is a multi-paradigm language, and we have used object-oriented and functional styles of programming where each adds most value. Generally speaking, the object-oriented style is used to make computational geometry objects such as Polygons integrate well into the Python language (this is called making them "Pythonic") and the functional style has been used to implement algorithms that are best expressed as a sequence of mathematical functions. Our goal is always to make the code as clear and concise as possible rather than enforce any particular programming paradigm.
We will generally adopt a functional programming style for computational geometry algorithms where the algorithms are implemented as functions that operate on simple entity classes. An entity class is simply a class that has very little behaviour - it is really just a data structure. A more object oriented approach would mean having complex classes with computational geometry algorithms as methods. This has some advantages, but we find that full object orientation doesn't work so well in this case for a couple of reasons:
The functional programming style lends itself very well to mathematical programming. After all, most mathematics is about functions in one form or another, and aggregating these functions into classes really adds very little value.
We need to present the material in this book in a logical, sequential fashion. This means, for example, that we can't create an all-singing-all-dancing Point class with a full set of computational geometry algorithms at the start of the book, because we haven't introduced those algorithms yet.
We are actually expert object-oriented programmers (see our books at www.clearviewtraining.com) but in this case, the functional style is a better fit. One of the joys of Python is that it is multi-paradigm language, so we can use whatever programming paradigm is best for a particular problem.
There are two types of Python code in this book. Reusable code, and code in "#Demo". Code in a "#Demo" block is either an interactive demonstration or an illustration for the text. It is not reusable outside of its notebook. Where possible, we divide demo code into two parts:
Geometry - this is where we do all the calculations we need.
Graphics - this is where we plot the results of the calculation on the canvas for display.
The idea is to separate the application of the algorithms from the presentation of the results as clearly as we can.
In order not to pollute the namespace of each notebook with non-reusable code we use underscores. Demo functions are prefixed by _demo... and non-reusable constants and variables are prefixed by an underscore. By convention names beginning in an underscore are considered to be private in Python, and in this case, underscore means "private to the notebook and not exported".
We have extracted the reusable code from each chapter into the following modules:
ICGChapter01.ipynb -> ICGChapter01.py
ICGChapter02.ipynb -> ICGChapter02.py
...
ICGChapter12.ipynb -> ICGChapter12.py
To use a function in one of these modules simply include it in your own source code as you would any other module.
These modules have complete documentation in the same format as the Python docs. It can be found in the following subdirectory of the book installation:
/docs/index.html
Open this file in your web browser, not in Anaconda. This is because Anaconda will treat it as source code and will not render it as HTML.
Tip: When you are reading the book, if you want to go back to see a previous function, it is generally easiest to find it in the fully searchable documentation. This will tell you what Notebook file it is in if you need to refer to the surrounding text.
If you are interested in how we extracted the code, take a look at the file Tools2.ipynb, and you can also see our SlideShare presentation, "Want to write a book in Jupyter - here's how".
The Python code is provided to you under the GNU GPLv3 license.
The Python SymPy library contains geometrical objects such as points, lines and polygons. However, for the purposes of this book, a black-box library simply does not meet our instructional needs. After careful consideration, we chose instead to implement all objects from scratch so you can see exactly how they work. We believe this is a very important part of the book. However, there is no reason why the algorithms presented here could not be recast in terms of SymPy if that is required.
Before we get into the book, we need to import the Python code we need. Apart from TocTools these modules are all part of Python distribution installed with Anaconda:
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import networkx as nx
from matplotlib.path import Path
from ipywidgets import *
import math
import random
from collections import OrderedDict
import copy
import functools
import itertools
from scipy.special import binom
from TocTools import *
In this section, we will use our displayTOC(...) utility from our TocTools module to generate the table of contents for the whole book. We have found that there are some limitations to automatic TOC generation in Jupyter, and we discuss these in detail here:
Want to write a book in Jupyter - here's how
Before we generate the TOC, we need to tell Jupyter to turn off scrolling in its output cells so that the generated output all appears in one block with no scroll bars:
%%javascript
IPython.OutputArea.prototype._should_scroll = function(lines) {return false;}
Now we can generate the TOC:
#Demo
_bookStructure = {"Introduction":"ICGChapter00.ipynb",
"Chapter 1: Points and lines":"ICGChapter01.ipynb",
"Chapter 2: Polygonal chains in two dimensions":"ICGChapter02.ipynb",
"Chapter 3: Triangles and the relationship of points to lines":"ICGChapter03.ipynb",
"Chapter 4: Triangle geometry":"ICGChapter04.ipynb",
"Chapter 5: Polygons":"ICGChapter05.ipynb",
"Chapter 6: Random polygons":"ICGChapter06.ipynb",
"Chapter 7: Intersections":"ICGChapter07.ipynb",
"Chapter 8: Polygon extreme points, tangents, monotonicity and splitting":"ICGChapter08.ipynb",
"Chapter 9: Convex hulls":"ICGChapter09.ipynb",
"Chapter 10: Polygon triangulations":"ICGChapter10.ipynb",
"Chapter 11: Point set triangulation and dual graph":"ICGChapter11.ipynb",
"Chapter 12: Optimal triangulation":"ICGChapter12.ipynb",
"Bibliography":"ICGChapter13.ipynb"}
for title, file in _bookStructure.items():
display(Markdown("## {}".format(title)))
displayTOC(file, title=False, hyperlink=False)
#Demo
Do not change anything here unless you really have to and know what you are doing!
You might need to customize some settings to make the notebooks look their best on your display. In particular, Apple and other systems with retina displays might need larger font sizes.
To customize all the notebooks first save a backup copy of the whole book distribution - you will need it if anything goes wrong! Now you can experiment with optimizing fonts and graphics for your display:
Make any changes you want in the next cell.
Uncomment the indicated lines of the next cell.
Execute the cell.
Replace the comments.
Restart your Anaconda-Navigator environment to see the changes.
Repeat until everything looks as you want it to.
# Customize font sizes in pts
SMALL_SIZE = 14
MEDIUM_SIZE = 16
LARGE_SIZE = 18
plt.rc('font', size=SMALL_SIZE) # controls default text sizes
plt.rc('axes', titlesize=SMALL_SIZE) # fontsize of the axes title
plt.rc('axes', labelsize=MEDIUM_SIZE) # fontsize of the x and y labels
plt.rc('xtick', labelsize=SMALL_SIZE) # fontsize of the x tick labels
plt.rc('ytick', labelsize=SMALL_SIZE) # fontsize of the y tick labels
plt.rc('legend', fontsize=SMALL_SIZE) # fontsize of the legend
plt.rc('figure', titlesize=LARGE_SIZE) # fontsize of the figure title
# Customize the canvas size in inches (for best results, keep it square)
CANVAS_WIDTH = 8
CANVAS_HEIGHT = 8
# Uncomment the next lines and execute this cell to apply your changes:
#!jupyter nbconvert --to python \
#--TemplateExporter.exclude_input_prompt=True \
#--TemplateExporter.exclude_output_prompt=True \
#--TemplateExporter.exclude_output=True \
#--TemplateExporter.exclude_markdown=True \
#--TagRemovePreprocessor.remove_cell_tags={\"DEMO\"} \
#ICGChapter00
# Put the comments back when you are finished
If anything goes wrong, simply restore the book distribution from its backup.
These notebooks are set up to work with modern, high resolution retina displays to give the best possible graphics. Jupyter works very nicely indeed with retina displays, and gives very high quality output. If the graphics do not display correctly, you might not have a retina display. In this case, look at the second cell in each notebook. It should look like this:
# Comment out the line below if the graphics do not display
%config InlineBackend.figure_format = 'retina'
If you follow the instruction to comment out the line and then run the notebook, your graphics should now work.
If you see no graphics, or garbage, undo the change you made above, and re-run the notebook. Everything should now be back to normal.
Again, if anything goes wrong, simply restore the book distribution from its backup!
We always like to hear from our readers, and you can contact the author, Jim Arlow, at Clear View Training Limited. Jim is often available for consultancy and training.