2D Geometry¶
Computational geometry (sometimes called algorithmic geometry) deals with solving mathematical and computational problems involving geometric objects. Although computational geometry covers a variety of dimensions, 2D geometry algorithms primarily deal with flat objects such as points, lines, polygons, circles and curves.
Basic concepts¶
- Point: The most basic object in 2D geometry. It is characterized by two coordinates: \((x, y)\).
- Perimeter: The connection of two points by a line.
- Polygon: A closed figure formed by three or more segments.
- Circle: All points equidistant from one central point.
Key Issues¶
- Point Location: Determining whether a point is inside, outside or on the periphery of a given polygon.
- intersection of segments: Determining whether two segments intersect.
- Convex perimeter: Finding the smallest convex polygon containing a given set of points.
- Nearest pair of points: Finding the two closest lying points in a set of points.
Algorithms and techniques¶
- Graham scanning: An algorithm for finding the convex envelope for a set of points.
- Sweep Line: A technique used in many 2D geometry problems, such as finding intersections of segments.
- Divide and Conquer: A basic method used to solve the nearest pair of points problem.
Applications¶
2D geometry algorithms have a wide range of applications in various fields, from computer graphics to robotics to geospatial analysis. They enable the creation of realistic simulations, optimization of robot routes or spatial analysis in GIS.
Summary¶
Knowledge of basic 2D geometry algorithms is essential for anyone working in computer graphics, geospatial analysis or robotics. Although these are flat problems, they can be surprisingly complex. However, a properly chosen algorithm can make a difficult problem easily solvable.