Aleph::DelaunayTriangulationBowyerWatson Class Reference

Exact Delaunay triangulation using the Bowyer-Watson incremental algorithm. More...

#include <geom_algorithms.H>

Classes
struct	IndexedTriangle
	Represents a triangle by the indices of its three vertices. More...
struct	Result
	The result of a Delaunay triangulation. More...

Public Member Functions
Result	operator() (const DynList< Point > &point_set) const
	Compute Delaunay triangulation of a point set.
Result	operator() (const std::initializer_list< Point > il) const
	Convenience overload using initializer-list input.

Static Public Member Functions
static DynList< Triangle >	as_triangles (const Result &result)
	Convert indexed triangulation to geometric triangles.

Static Private Member Functions
static bool	lexicographic_less (const Point &p1, const Point &p2)
	Lexicographical comparison for points.
static bool	all_collinear (const Array< Point > &pts)
	Check if all points in an array are collinear.
static bool	point_in_circumcircle (const Array< Point > &pts, const size_t ia, const size_t ib, const size_t ic, const size_t ip)
	Predicate to check if a point lies inside the circumcircle of a triangle.
static Array< Point >	unique_points (const DynList< Point > &point_set)
	Extracts unique points from a list and sorts them lexicographically.

Detailed Description

Exact Delaunay triangulation using the Bowyer-Watson incremental algorithm.

This class computes the Delaunay triangulation of a set of 2D points. The Delaunay triangulation for a set P of points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).

Implementation Details

1. Preprocessing: Duplicate points are removed, and the remaining points are sorted lexicographically to ensure deterministic behavior.
2. Super-triangle: A large triangle enclosing all points is created to initialize the triangulation.
3. Incremental Insertion: Points are inserted one by one. For each point:
   • Identify all triangles whose circumcircle contains the point (the cavity).
   • Remove these triangles and find the boundary of the cavity.
   • Create new triangles by connecting the new point to each edge of the cavity boundary.
4. Cleanup: Triangles connected to the super-triangle vertices are removed.

Complexity

• Time: Average O(n log n), Worst-case O(n²) where n is the number of points.
• Typical random input: near O(n log n).
• Space: O(n) to store the triangulation.

Author

Leandro Rabindranath León

Alejandro J. Mujica

Definition at line 2100 of file geom_algorithms.H.

Member Function Documentation

all_collinear()

static bool Aleph::DelaunayTriangulationBowyerWatson::all_collinear ( const Array< Point > &  pts )

inlinestaticprivate

Check if all points in an array are collinear.

Definition at line 2140 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::COLLINEAR, and Aleph::orientation().

Referenced by operator()().

as_triangles()

static DynList< Triangle > Aleph::DelaunayTriangulationBowyerWatson::as_triangles ( const Result &  result )

inlinestatic

Convert indexed triangulation to geometric triangles.

Parameters

result

Triangulation result.

Returns

List of geometric triangles.

Definition at line 2264 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), k, out, Aleph::DelaunayTriangulationBowyerWatson::Result::sites, and Aleph::DelaunayTriangulationBowyerWatson::Result::triangles.

Referenced by TEST_F().

lexicographic_less()

static bool Aleph::DelaunayTriangulationBowyerWatson::lexicographic_less ( const Point &  p1, const Point &  p2  )

inlinestaticprivate

Lexicographical comparison for points.

Definition at line 2128 of file geom_algorithms.H.

References Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by unique_points().

operator()() [1/2]

Result Aleph::DelaunayTriangulationBowyerWatson::operator() ( const DynList< Point > &  point_set ) const

inline

Compute Delaunay triangulation of a point set.

Parameters

point_set

Input points.

Returns

Unique sites and triangulation indices.

Definition at line 2223 of file geom_algorithms.H.

References all_collinear(), Aleph::blossom_maximum_cardinality_matching(), point_in_circumcircle(), Aleph::DelaunayTriangulationBowyerWatson::Result::sites, and unique_points().

operator()() [2/2]

Result Aleph::DelaunayTriangulationBowyerWatson::operator() ( const std::initializer_list< Point >  il ) const

inline

Convenience overload using initializer-list input.

Parameters

il	Input points.

Returns

Unique sites and triangulation indices.

Definition at line 2250 of file geom_algorithms.H.

References Aleph::DynList< T >::append(), and Aleph::blossom_maximum_cardinality_matching().

point_in_circumcircle()

static bool Aleph::DelaunayTriangulationBowyerWatson::point_in_circumcircle ( const Array< Point > &  pts, const size_t  ia, const size_t  ib, const size_t  ic, const size_t  ip  )

inlinestaticprivate

Predicate to check if a point lies inside the circumcircle of a triangle.

Definition at line 2155 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CCW, Aleph::CW, Aleph::in_circle_determinant(), and Aleph::orientation().

Referenced by operator()().

unique_points()

static Array< Point > Aleph::DelaunayTriangulationBowyerWatson::unique_points ( const DynList< Point > &  point_set )

inlinestaticprivate

Extracts unique points from a list and sorts them lexicographically.

Definition at line 2196 of file geom_algorithms.H.

References Aleph::all(), Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::HTList::Iterator::has_curr(), lexicographic_less(), Aleph::quicksort_op(), and Aleph::Array< T >::reserve().

Referenced by operator()().

---

The documentation for this class was generated from the following file:

• geom_algorithms.H