Computational Geometry in Python

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:))

Numerical evaluation

 

https://docs.sympy.org/latest/modules/geometry/utils.html

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:

 

 

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.

Figure Source

 

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

 

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.