Interactive Computational Geometry in Python

by Jim Arlow

Copyright © 2018 by Clear View Training Limited
All rights reserved. This book or any portion thereof may not be reproduced or used in any manner whatsoever without the express written permission of the publisher except for the use of brief quotations in a book review.
First Edition, 2018
Published in England by [Clear View Training Limited](https://www.clearviewtraining.com)

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.

Introduction

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:

  1. Explanation

  2. Implementation

  3. 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.

Audience

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, 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 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 most programmers.

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.

Jupyter Notebooks

This book is distributed as a number of Jupyter notebooks, one for each chapter, called "ICGChapterXX.ipynb". You should read these chapters in order.

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 and rich text are 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:

https://try.jupyter.org

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.

Jupyter cells

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:

  1. 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.

  2. 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.

  3. Output cells - in fact, these are appended to the bottom of code cells, and contain the result of running them.

  4. Demo cells - a new type of cell that we have added.

For the purposes of this text, we have introduced another type of cell, the Demo cell. This is a code cell whose first line is "#Demo" and whose last line is also "#Demo". They are also given the special tag DEMO. We use a preprocessor (itself a Jupyter notebook) to skip over these cells and generate the Python code for each chapter. These 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.

Instructions for running the notebooks

Having downloaded the distribution for this book, unzip it into a subdirectory on your disk. It doesn't matter where it is.

To run the chapter notebooks, you first need to install a Jupyter environment. We recommend Anaconda-Navigator. We wrote this book entirely in the Anaconda-Navigator environment and it works perfectly. You can download the latest Anaconda 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.

Install the application and run it. 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. Navigate to the notebook you want to run and click on it. The notebook should launch in your browser.

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:

  • The notebooks must be "Trusted" to work properly. There will be 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 because of dependencies. Select "Cell/Run All" or "Shft-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".

Everything should work OK.

About the Python 3 code

All the algorithms are implemented in Python 3. All sorce code, including that embedded in the Jupyter notebooks is provided under the

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 would like to reiterate that code in "#Demo" blocks is either an interactive demonstration or an illustration for the text and is not reusable outside of its notebook.

Each interactive demonstration is some code or a function that is divided into two parts:

  1. Geometry - this is where we do all the calculations we need.

  2. 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. In order not to pollute the namespace of each notebook, demo functions are prefixed by _demo... and non-reusable constants and variables are prefixed by an underscore.

Reusing the code

We have extracted the reusable Python code from each chapter into the following modules:

ICGChapter01.ipynb -> ICGChapter01.py
ICGChapter02.ipynb -> ICGChapter02.py
...
ICGChapter13.ipynb -> ICGChapter13.py

To use a function in one of these modules simply include it in your own source code.

These modules have complete documentation (in the same format as the Python docs) that 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 becasue Anaconda will treat it as source code and will not display it.

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 SymPy library

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.

Imports

Before we get into the book, we need to import the Python code we need. These libraries are all part of Python distribution installed with Anaconda-Navigator:

In [5]:
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 *

Table of contents

In this section, we will use our displayTOC(...) unitility to generate the table of contents for the whole book. There are some limitations to 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:

In [6]:
%%javascript
IPython.OutputArea.prototype._should_scroll = function(lines) {return false;}

Now we can generate the TOC:

In [7]:
#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

Introduction

  • Introduction
  • Audience
  • Jupyter Notebooks
    • Jupyter cells
  • Instructions for running the notebooks
  • About the Python 3 code
    • Reusing the code
    • The SymPy library
  • Table of contents
  • Advanced setup
    • Retina displays
  • Contact us

Chapter 1: Points and lines

  • Chapter 1: Points and lines
  • Points
    • The distance between two points
  • Lists of Points
    • Integer point lists
    • Ordered Point sets
  • Extreme Points of a PointList
  • Random sets of Points not in general position
  • Displaying Points and other geometrical objects
  • Lines, rays, and line segments
  • Representing line segments
    • The geometry of line segments
  • Displaying lines, rays and line segments
  • Summary

Chapter 2: Polygonal chains in two dimensions

  • Chapter 2: Polygonal chains in two dimensions
  • Polygonal chains
    • Simple polygonal chains
    • Monotone polygonal chains
  • Summary

Chapter 3: Triangles and the relationship of points to lines

  • Chapter 3: Triangles and the relationship of points to lines
  • Polygons
    • Representing polygons in Python
  • Triangles
    • Signed area of a triangle
  • Triangles and the relationships of points to lines
    • isCollinear, isLeft, isLeftOn, isRight, isRightOn
    • Between
    • Demo program for relationships between points and lines
  • Points in general position
    • Probability of a random point set being in general position
    • Random point sets in general position
  • The relationship of points to the half-plane
  • Summary

Chapter 4: Triangle geometry

  • Chapter 4: Triangle geometry
  • The centroid, medians and circumcircle of a triangle
    • Circumcenter from perpendicular edge bisectors
    • Circumcircle from distances to vertexes
  • The internal angles of a triangle
  • Triangulating a triangle with an internal point
  • Random triangles
  • Summary

Chapter 5: Polygons

  • Chapter 5: Polygons
  • Polygon edges
  • Polygon indexes and modular arithmetic
    • Splitting a polygon
  • A polygon class
  • Regular polygons
    • Regular star polygons
  • Monotone mountain polygons
  • Convex polygon areas
    • Triangulate the convex polygon
    • Sum the areas of the triangles
    • The total number of convex polygon triangulations
  • General polygon areas
  • Summary

Chapter 6: Random polygons

  • Chapter 6: Random polygons
  • Chapter contents
  • Random polygon
  • Random simple star shaped polygons
      1. Generate a random polygon
      1. Choose an origin
      1. Sort anti-clockwise
      1. Loop until no collinear triples
    • Random star shaped polygons using the rightmost lowest vertex
    • Comparing origins for random star shaped polygons
  • Point lists to star shaped polygons
  • Summary

Chapter 7: Intersections

  • Chapter 7: Intersections
  • Types of intersection of line segments
    • Proper intersection of line segments
    • Improper intersection of line segments
    • Intersection of line segments
  • Point of intersection of two lines
  • The relationship of points to convex polygons
    • Test for polygon convexity
    • Point inside convex polygon
  • Line segment intersection with polygon
  • Polygon self intersection and simple polygons
  • Summary

Chapter 8: Polygon extreme points, tangents, monotonicity and splitting

  • 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 across tangent vertexes
  • Summary

Chapter 9: Convex hulls

  • Chapter 9: Convex hulls
  • Incremental convex hull algorithm
  • Graham scan convex hull algorithm
  • Comparison of incremental and Graham scan convex hull algorithms
  • Summary

Chapter 10: Polygon triangulations

  • Chapter 10: Polygon triangulations
  • Polygon diagonals
    • Finding polygon diagonals
  • Polygon triangulation by ear tip removal
  • Summary

Chapter 11: Point set triangulation and dual graph

  • Chapter 11: Point set triangulation and dual graph
  • Triangle-splitting triangulation algorithm
  • Simple incremental triangulation with convex hull
  • Finding the edges in a triangulation
  • 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: Optimal triangulation

  • Chapter 12: Optimal triangulation
  • Angle vectors
  • The MinMax and MaxMin criteria
  • Triangulation deviation from equiangular
  • Delaunay triangulation
  • Flipping diagonals
  • Converting a triangulation to a Delaunay triangulation
  • Voronoi diagrams
  • Summary

Bibliography

  • Bibliography

Advanced setup

You might need to customize some settings to make the notebooks look good on your display. In particular, Apple and other systems with retina displays might need larger font sizes. Do not change anything here unless you really have to and know what you are doing!

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:

  1. Make any changes you want in the next cell.

  2. Uncomment the indicated lines of the next cell.

  3. Execute the cell.

  4. Replace the comments.

  5. Restart your Anaconda-Navigator environment to see the changes.

Repeat until everything looks as you want it to.

In [8]:
# 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.

Retina displays

Jupyter can work very nicely indeed with retina displays, and can give you very high quality output. If you have a retina display (or think you have) you can enable support for it.

Look at the second cell in each notebook. It should look like this:

# Uncomment the line below for better graphics if you have a retina display
#%config InlineBackend.figure_format = 'retina'

If you follow the instruction, uncomment the line and then run the notebook, you should see significantly higher quality graphics. Congratulations, you have a retina display!

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!

Contact us

We always like to hear from our readers, and you can contact the author, Jim Arlow, at Clear View Training Limited.