Introducing scikit-geometry

The Python ecosystem is lacking a library with useful geometric types — we aim to fix this by introducing scikit-geometry. This new library implements the basic types like Point, Line, Ray and Polygon, and contains functions to compute geometric properties such as intersections, dilations, inner skeletons etc.

As a robotics researcher (but also in many other fields) computations on geometric primitives are used very frequently— but it’s harder than anticipated to find the right abstractions in a nice Python library. The C++ ecosystem has a very mature library that implements the basic geometric types very nicely: the Computational Geometry Algorithms Library. scikit-geometry is a Python library that has nice wrappers around many of the CGAL types, thanks to the awesome pybind11.

The repository can be found on GitHub https://github.com/scikit-geometry/scikit-geometry and the docs are here: http://scikit-geometry.github.io/scikit-geometry/

Some of the basic types are:

• Point2 for 2D, Point3 for 3D
• Segment2 , Ray2 , Line2 , and for 3D
• Circle2
• IsoRectangle2 , BBox2 and for 3D
• Plane3 , Triangle3
• …

As one can imagine, these types go a long way to define all sorts of geometries, and query for properties or generate new ones based on programmatic construction using intersections or other algorithms.

The following example shows how easy it is to use the geometric primitives to find all pairwise intersections. The scikit-geometry library also offers functionality to draw the geometric types easily, using the draw function (implemented on top of matplotlib).

Finding intersections between multiple line segments

Polygons in Python

Another extremely useful type in scikit-geometry is the Polygon . We have a lot of functionality in scikit-geometry that works with polygons, or polygons with holes (a polygon with an outer and inner boundary). Polygons can be created from NumPy arrays, and the points can be read as NumPy array by using the coords accessor.

Joining the blue and red polygon using scikit-geometry’s boolean set operations

Or you can use the straight skeleton methods to compute offset or inset polygons (works with polygons with holes as well).

Left: straight skeleton of the gray polygon, center: right: inset polygon (red) of the gray polygon

Another functionality that is very useful in robotics is to compute the visibility of 2D arrangements. The visibility is defined as the obstruction free space (the visibile 2D, polygonal space from some point).

Computing the visibility polygon in a 2D arrangement

Polygon simplification is implemented in the simplification module (and can optionally be topology preserving, which is an important property e.g. for contour lines of maps).

Original random polygon on the left, and simplified polygon overlaid in gray on the right

And much more …

scikit-geometry also comes with functions to compute the Voronoi diagram, the convex hull, bounding boxes, the minkowski sum of two polygons, a AABB tree for fast nearest neighbor queries and many other useful utilities for geometric computations, with plans to add many more!

scikit-geometry also uses the CGAL multi-precision number type on the C++ side so that intersection computations stay accurate, and there are no errors due to floating point rounding or divisions.

Comparison with existing libraries

There are some libraries for handling geometric primitives out there already, but we found all of them lacking:

• pyclipper is a nice library based on Clipper for offseting polygons, and boolean combinations of them, but it mostly stops there
• Shapely is another very good, GEOS based library with some geometric types. As far as I know it implements very few basic types (only point, line string (really a “line segment” string) and polygon). It doesn’t have support for fundamental geometric types such as rays or infinite lines. GEOS and shapely come with some nice functions for buffering (offseting) line strings, points and polygons, as well as boolean operations and certain helper functions to test predicates (overlap, touch, crossing …)
• GEOS also has another nice, vectorized wrapper (pyGEOS) by the folks who develop geopandas. All in all, GEOS seems very much geared towards GIS applications
• The CGAL SWIG wrappers, obviously, support some of the functionality exposed here. But SWIG is an oldschool tool, that doesn’t offer as much flexibility as pybind11 and is not as specific to Python which makes it harder to create seamless bindings.

Compared to these libraries, scikit-geometry tries to offer a more comprehensive toolkit for computational geometry, that feels natural in Python and offers fast performance. We still lack vectorized operations (although they can be emulated by putting scikit-geometry objects in a NumPy array.

Installation

scikit-geometry can either be built from source, or installed from conda .

We have published the package for Linux, OS X and Windows to the conda-forge channel. Users of conda can simply install via

conda install scikit-geometry -c conda-forge

Otherwise, CGAL 5.0 needs to be available, and then running python -m pip install -e . -vfrom the cloned scikit-geometry git repository should install and build scikit-geometry (note: this takes a while to build!).

Contribute

If you are interesting in helping out the development of this young library, feel free to join us on GitHub with PRs, and issues!

If you are a company and want to sponsor this project, feel free to reach out to me on wolf.vollprecht@quantstack.net

About the author

Wolf Vollprecht is a robotics engineer working at QuantStack. QuantStack is a small software consultancy based in Europe, focusing on Open Source Scientific Software. We are working on high performance C++ libraries and data visualization in combination with interactive computing. Feel free to reach out to us!

Follow me on Twitter