This page provides some useful resources about computational geometry using Python.
(For computational geometry in C++, check out the excellent library CGAL (website, GitHub repo); for computational geometry in Java, check out the JTS library (GitHub repo, website))
(Stay tuned, as I will update the content on this page while I plow and grow in my deep learning garden:))
- Libraries
- SymPy (GitHub repo, website) — sympy.geometry (Utils, Points, Lines, Curves, Ellipses, Polygons, Plane) — SymPy Cheatsheet
- SymPy is a Python library for symbolic mathematics. It aims to become a full-featured computer algebra system (CAS) while keeping the code as simple as possible in order to be comprehensible and easily extensible. SymPy is written entirely in Python.
https://docs.sympy.org/latest/modules/geometry/utils.html
-
- scipy.spatial (Spatial algorithms and data structures) — reference page — SciPy Cheat Sheet (Linear Algebra)
-
- PySAL –Python Spatial Analysis Library (website, GitHub repo), its computational geometry component, esp its
cg.shapes
— Shapes - Shapely (GitHub repo, documentation and manual) — Manipulation and analysis of geometric objects in the Cartesian plane
- PySAL –Python Spatial Analysis Library (website, GitHub repo), its computational geometry component, esp its
-
- PyVisiLibity (GitHub repo) — Python binding of VisiLibity 1
Current Functionality of VisiLibity1 in planar polygonal environments with polygonal holes:
-
-
-
- visibility polygons
- visibility graphs
- Euclidean shortest paths for a point
- Python, Ruby, and Matlab bindings
-
-
-
- TBA
- Good posts:
- Computational Geometry in Python: From Theory to Application (by CHARLES MARSH) — PDF
- Computational Geometry in Python (Oct 28, 2014) — (using sympy.geometry, with code examples, including Bézier Curves,Convex Hulls, Voronoi Diagrams, Triangulations, Shortest Paths, Geometric Query Problems using scipy.spatial; Plane Geometry using sympy.geometry , including points, line segments, lines, circles, triangles, curves) —PDF
- Image Processing with numpy, scipy and matplotlibs in sage (Dec 15, 2010) — PDF
- Boundary enclosing a given set of points
- JavaScript code that builds concave hull: https://github.com/AndriiHeonia/hull (See live examples here.)
An alphaShape creates a bounding area or volume that envelops a set of 2-D or 3-D points. You can manipulate the alphaShape object to tighten or loosen the fit around the points to create a nonconvex region. You also can add or remove points or suppress holes or regions.After you create an alphaShape object, you can perform geometric queries. For example, you can determine if a point is inside the shape or you can find the number of regions that make up the shape. You also can calculate useful quantities like area, perimeter, surface area, or volume, and plot the shape for visual inspection.
Source: from Zhou, W., & Yan, H. (2012). Alpha shape and Delaunay triangulation in studies of protein-related interactions. Briefings in bioinformatics, 15(1), 54-64.
Source: https://en.wikipedia.org/wiki/Alpha_shape
-
-
- Convex and Concave hull
-
“Convex and concave hulls are useful concepts for a wide variety of application
areas, such as pattern recognition, image processing, statistics, and classification tasks.
Concave hull performs better than convex hull, but it is difficult to formulate and few
algorithms are suggested. Especially, an n-dimensional concave hull is more difficult
than a 2- or 3- dimensional one. In this paper, we propose a new concave hull algorithm
for n-dimensional datasets. It is simple but creative. We show its application to dataset
analysis. We also suggest a concaveness measure and a graph that captures geometric
shape of an n-dimensional dataset. Proposed concave hull algorithm and concaveness
measure/graph are implemented using java, and are posted to http://user.dankook.ac.kr/
~bitl/dkuCH.”
source from: Park, J. S., & Oh, S. J. (2012). A new concave hull algorithm and concaveness measure for n-dimensional datasets. Journal of Information science and engineering, 28(3), 587-600. (Paper PDF link)
- TBA
- Good blogs
- Books
- Interactive Computational Geometry in Python (by Jim Arlow, 2018)
This book is an interactive introduction to some of the fundamental algorithms of computational geometry. It is supplied as a set of interactive Jupyter Notebooks.