Aleph::VoronoiDiagram Class Reference

O(n log n) Voronoi diagram construction. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::VoronoiDiagram:

Public Types
using	Edge = VoronoiDiagramFromDelaunay::Edge
	Type for Voronoi edges.
using	Cell = VoronoiDiagramFromDelaunay::Cell
	Type for Voronoi cells.
using	ClippedCell = VoronoiDiagramFromDelaunay::ClippedCell
	Type for clipped Voronoi cells.
using	Result = VoronoiDiagramFromDelaunay::Result
	Complete result structure.

Public Member Functions
Result	operator() (const DynList< Point > &pts) const
	Compute the Voronoi diagram for a list of points.
Result	operator() (const std::initializer_list< Point > il) const
	Compute the Voronoi diagram from an initializer list.
Array< ClippedCell >	clipped_cells (const DynList< Point > &pts, const Polygon &clip) const
	Compute Voronoi cells clipped to a bounding polygon.

Private Attributes
DelaunayTriangulationRandomizedIncremental	delaunay_
	Internal Delaunay triangulator.
VoronoiDiagramFromDelaunay	voronoi_
	Internal dual builder.

Detailed Description

O(n log n) Voronoi diagram construction.

Computes the Voronoi diagram by composing:

1. O(n log n) randomized incremental Delaunay triangulation
2. O(n) dual construction (circumcenters → Voronoi vertices)

Uses exact rational arithmetic (Geom_Number) throughout.

The output types are identical to VoronoiDiagramFromDelaunay.

Complexity

• Expected time: O(n log n)
• Space: O(n)

Example

VoronoiDiagram vd;
auto res = vd({Point(0,0), Point(1,0), Point(0,1)});
// res.cells / res.edges contain the diagram.

Fast Voronoi diagram computation using randomized incremental Delaunay.

This class provides a convenient interface to compute the Voronoi diagram of a set of points. It combines DelaunayTriangulationRandomizedIncremental with VoronoiDiagramFromDelaunay to produce the dual diagram.

Author

Leandro Rabindranath León

Alejandro J. Mujica

Definition at line 4175 of file geom_algorithms.H.

Member Typedef Documentation

Cell

using Aleph::VoronoiDiagram::Cell = VoronoiDiagramFromDelaunay::Cell

Type for Voronoi cells.

Definition at line 4182 of file geom_algorithms.H.

ClippedCell

using Aleph::VoronoiDiagram::ClippedCell = VoronoiDiagramFromDelaunay::ClippedCell

Type for clipped Voronoi cells.

Definition at line 4183 of file geom_algorithms.H.

Edge

using Aleph::VoronoiDiagram::Edge = VoronoiDiagramFromDelaunay::Edge

Type for Voronoi edges.

Definition at line 4181 of file geom_algorithms.H.

Result

using Aleph::VoronoiDiagram::Result = VoronoiDiagramFromDelaunay::Result

Complete result structure.

Definition at line 4184 of file geom_algorithms.H.

Member Function Documentation

clipped_cells()

Array< ClippedCell > Aleph::VoronoiDiagram::clipped_cells ( const DynList< Point > &  pts, const Polygon &  clip  ) const

inline

Compute Voronoi cells clipped to a bounding polygon.

Parameters

pts	Input list of sites.
clip	Bounding polygon used for clipping.

Returns

Array of clipped cells.

Definition at line 4216 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::VoronoiDiagramFromDelaunay::clipped_cells_indexed(), and delaunay_.

operator()() [1/2]

Result Aleph::VoronoiDiagram::operator() ( const DynList< Point > &  pts ) const

inline

Compute the Voronoi diagram for a list of points.

Parameters

pts	Input list of sites.

Returns

Result structure containing the diagram components.

Definition at line 4191 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), delaunay_, and voronoi_.

operator()() [2/2]

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

inline

Compute the Voronoi diagram from an initializer list.

Parameters

il	Initializer list of points.

Returns

Result structure containing the diagram components.

Definition at line 4202 of file geom_algorithms.H.

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

Member Data Documentation

delaunay_

DelaunayTriangulationRandomizedIncremental Aleph::VoronoiDiagram::delaunay_

private

Internal Delaunay triangulator.

Definition at line 4177 of file geom_algorithms.H.

Referenced by clipped_cells(), and operator()().

voronoi_

VoronoiDiagramFromDelaunay Aleph::VoronoiDiagram::voronoi_

private

Internal dual builder.

Definition at line 4178 of file geom_algorithms.H.

Referenced by operator()().

---

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

• geom_algorithms.H