Combinatorial computational geometry

Also called algorithmic geometry, the applications of this field are plenty. In robotics, it is used to solve visibility problems, and motion planning, for instance. Similar applications are employed to design route planning or search algorithms in geographic information systems (GIS).

Let's describe the different categories of problems, putting emphasis on the tools to solve them, which are available in the SciPy stack.

Static problems

The fundamental problems in this category are the following:

• Convex hulls: Given a set of points in space, find the smallest convex polyhedron containing them.

• Voronoi diagrams: Given a set of points in space (the seeds), compute a partition in regions consisting of all points closer to each seed.

• Triangulations: Partition the plane with triangles in a way that two triangles are either disjointed, or otherwise they share an edge or a vertex. There are different triangulations depending on the input objects or constraints...