Computational Geometry

|

11 November 2010

This is a list of libraries and resources I have found on computational geometry. There are libraries in C/C++, Java and python. Also some interesting books are listed and sites with other lists.

2D libraries

JTS Topology Suite

The JTS Topology Suite is a Java API for modeling and manipulating 2-dimensional linear geometry. It provides numerous geometric predicates and functions. JTS conforms to the Simple Features Specification for SQL published by the Open GIS Consortium. See also:

GEOS
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite
(JTS).
Shapely 1.2.6
Geometric objects, predicates, and operations in python. Python bindings for the GEOS library. So it is also based on JTS.
Python Imaging Library (PIL)
The Python Imaging Library (PIL) adds image processing capabilities to your Python interpreter. This library supports many file formats, and provides powerful image processing and graphics capabilities.
scipy
Scientific programming with Python. It has some support for geometric calculations.

3D libraries

CGAL - Computational Geometry Algorithms Library

C++ library of efficient and reliable geometric algorithms. Offers data structures and algorithms like triangulations in 2D and 3D, arrangements of curves, mesh generation including volumes and skin surfaces, geometry processing (surface mesh simplification), convex hull algorithms (in 2D, 3D), search structures (kd trees), interpolation, shape analysis, fitting, and distances. See also:

GTS - The GNU Triangulated Surface Library

C library to deal with 3D surfaces meshed with interconnected triangles. Construct, manipulate, and perform computations on 3D triangulated surfaces. Efficient library to scientists dealing with 3D computational surface meshes. 2D dynamic Delaunay and constrained Delaunay triangulations. Robust geometric predicates, operations on surfaces (union, intersection, difference), surface refinement and coarsening, dynamic view-independent continuous level-of-detail, bounding-boxes trees and Kd-trees, metric operations (area, volume, curvature...), Triangle strips generation for fast rendering. There are python bindings, see:

(scipy.spatial)
Spatial algorithms and data structures .

Some auxiliary libraries

Rtree
Spatial indexing for Python
NURBS library (missing link)
NURBS - Non Uniform Rational B-Splines library programmed in python.

Other lists of resources

Computational Geometry Code
"small" pieces of geometric software available on the Internet.

Computational Geometry Software Libraries :

Related tags: geometry, gis