12. Computational Geometry#
Computational geometry is divided into two main branches:
Combinatorial computational geometry, which considers problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc. Examples of problems in this field include:
Line segment intersection: Find the intersections between a given set of line segments.
Convex hull: Given a set of points, find the smallest convex polyhedron/polygon containing all the points.
Polygon triangulation: Given a polygon, partition its interior into triangles
Point in polygon: Decide whether a point is inside or outside a given polygon.
Mesh generation: Generate a polygonal mesh that approximates a geometric domain
Numerical computational geometry, closely related to Computer-aided design (CAD), considers problems involving curves and surfaces, represented e.g. in Bézier or spline form. These are extensively used in various engineering disciplines, and important problems include the efficient representation of general shapes, and operations such as intersection of surfaces and other objects.