geom_algorithms.H File Reference

Computational geometry algorithms. More...

#include <polygon.H>
#include <htlist.H>
#include <tpl_dynSetTree.H>
#include <tpl_sort_utils.H>
#include <ah-errors.H>

Include dependency graph for geom_algorithms.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::CuttingEarsTriangulation
	Polygon triangulation using the ear-cutting algorithm. More...
class	Aleph::BruteForceConvexHull
	Brute force convex hull algorithm. More...
struct	Aleph::BruteForceConvexHull::CmpSegment
class	Aleph::GiftWrappingConvexHull
	Gift wrapping (Jarvis march) convex hull algorithm. More...
class	Aleph::QuickHull
	QuickHull convex hull algorithm. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Computational geometry algorithms.

This file provides fundamental algorithms for computational geometry:

Triangulation

• CuttingEarsTriangulation: Triangulate a simple polygon using the ear-cutting algorithm. Complexity: O(n²)

Convex Hull

Three algorithms to compute the convex hull of a point set:

Algorithm	Complexity	Best For
BruteForceConvexHull	O(n³)	Small sets, educational
GiftWrappingConvexHull	O(nh)	Few hull points (h small)
QuickHull	O(n log n) avg, O(n²) worst	General use

where n = number of points, h = number of hull points.

Dependencies

Requires polygon.H for geometric primitives:

• Point: 2D point with x, y coordinates
• Segment: Line segment between two points
• Polygon: Sequence of connected vertices
• Triangle: Three-point polygon
• Vertex: Point with connectivity information

Usage Example

#include <geom_algorithms.H>
 
// Create a point set
DynList<Point> points;
points.append(Point(0, 0));
points.append(Point(4, 0));
points.append(Point(4, 4));
points.append(Point(0, 4));
points.append(Point(2, 2));  // Interior point
 
// Compute convex hull
QuickHull qh;
Polygon hull = qh(points);  // Returns square (excludes interior point)
 
// Triangulate a polygon
Polygon square;
square.add_vertex(Point(0, 0));
square.add_vertex(Point(4, 0));
square.add_vertex(Point(4, 4));
square.add_vertex(Point(0, 4));
square.close();
 
CuttingEarsTriangulation triangulator;
DynList<Triangle> triangles = triangulator(square);

See also

polygon.H Geometric primitives

Point, Segment, Polygon, Triangle

Author

Leandro Rabindranath León

Alejandro J. Mujica

Definition in file geom_algorithms.H.