Mastering SciPy

Chapter 6. Computational Geometry

Computational geometry is a field of mathematics that seeks the development of efficient algorithms to solve problems described in terms of basic geometrical objects. We differentiate between combinatorial computational geometry and numerical computational geometry.

Combinatorial computational geometry deals with the interaction of basic geometrical objects—points, segments, lines, polygons, and polyhedra. In this setting, we have three categories of problems:

• Static problems: The construction of a known target object is required from a set of input geometric objects
• Geometric query problems: Given a set of known objects (the search space) and a sought property (the query), these problems deal with the search ...