Voronoi diagram derived as the dual of a Delaunay triangulation. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::VoronoiDiagramFromDelaunay:

Classes
struct	Cell
	Represents a Voronoi cell. More...

struct	ClippedCell
	Represents a Voronoi cell clipped by a bounding polygon. More...

struct	Edge
	Represents an edge in the Voronoi diagram. More...

struct	Result
	The complete result of a Voronoi diagram computation. More...

Public Member Functions
Result	operator() (const DelaunayTriangulationBowyerWatson::Result &dt) const
	Build Voronoi from a precomputed Delaunay triangulation.

Result	operator() (const DynList< Point > &point_set) const
	Build Voronoi from a point set (computes Delaunay first).

Result	operator() (const std::initializer_list< Point > il) const
	Convenience overload using initializer-list input.

Array< Polygon >	clipped_cells (const DynList< Point > &point_set, const Polygon &clip) const
	Compute Voronoi and clip its cells against a closed convex polygon.

Array< Polygon >	clipped_cells (const std::initializer_list< Point > il, const Polygon &clip) const
	Convenience overload with initializer-list input.

Array< ClippedCell >	clipped_cells_indexed (const DynList< Point > &point_set, const Polygon &clip) const
	Compute/clip Voronoi cells and return site-indexed records.

Array< ClippedCell >	clipped_cells_indexed (const std::initializer_list< Point > il, const Polygon &clip) const
	Convenience overload with initializer-list input.

Static Public Member Functions
static Array< Polygon >	clipped_cells (const Array< Point > &sites, const Polygon &clip)
	Clip Voronoi cells against a closed convex polygon.

static Array< Polygon >	clipped_cells (const Result &vor, const Polygon &clip)
	Clip Voronoi cells against a closed convex polygon.

static Array< ClippedCell >	clipped_cells_indexed (const Array< Point > &sites, const Polygon &clip)
	Clip Voronoi cells and return explicit site-indexed records.

static Array< ClippedCell >	clipped_cells_indexed (const Result &vor, const Polygon &clip)
	Clip Voronoi cells (from result) into site-indexed records.

Static Private Member Functions
static Point	circumcenter (const Point &a, const Point &b, const Point &c)
	Computes the circumcenter of three points.

static Array< Point >	extract_vertices (const Polygon &p)
	Extracts vertices from a closed polygon.

static bool	is_convex (const Array< Point > &verts)
	Checks if a vertex set forms a convex polygon.

static HalfPlaneIntersection::HalfPlane	bisector_halfplane_for_site (const Point &s, const Point &t)
	Creates a half-plane from a directed edge.

static Array< ClippedCell >	indexed_clipped_cells (const Array< Point > &sites, const Array< Polygon > &polys)

Private Attributes
DelaunayTriangulationBowyerWatson	delaunay
	Internal Delaunay triangulator.

Detailed Description

Voronoi diagram derived as the dual of a Delaunay triangulation.

A Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators).

Implementation Details

Vertices: Voronoi vertices are the circumcenters of the Delaunay triangles.
Edges: Each edge in the Delaunay triangulation corresponds to an edge in the Voronoi diagram. Internal Delaunay edges map to bounded Voronoi segments, while Delaunay edges on the convex hull map to unbounded Voronoi rays.
Cells: Each site has a corresponding Voronoi cell, which is a convex polygon (possibly unbounded).

Author: Leandro Rabindranath León; Alejandro J. Mujica

Definition at line 3681 of file geom_algorithms.H.

Member Function Documentation

◆ bisector_halfplane_for_site()

static HalfPlaneIntersection::HalfPlane Aleph::VoronoiDiagramFromDelaunay::bisector_halfplane_for_site	(	const Point &	s,
		const Point &	t
	)

inlinestaticprivate

Creates a half-plane from a directed edge.

Definition at line 3785 of file geom_algorithms.H.

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

◆ circumcenter()

static Point Aleph::VoronoiDiagramFromDelaunay::circumcenter	(	const Point &	a,
		const Point &	b,
		const Point &	c
	)

inlinestaticprivate

Computes the circumcenter of three points.

Definition at line 3735 of file geom_algorithms.H.

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

Referenced by operator()().

◆ clipped_cells() [1/4]

static Array< Polygon > Aleph::VoronoiDiagramFromDelaunay::clipped_cells	(	const Array< Point > &	sites,
		const Polygon &	clip
	)

inlinestatic

Clip Voronoi cells against a closed convex polygon.

This produces bounded polygons for all cells, including originally unbounded hull-site cells.

Parameters

sites	Voronoi sites.
clip	Closed convex clipping polygon.

Returns: One clipped convex polygon per site (same order as sites).

Exceptions

domain_error if the clip is not closed/convex or has < 3 vertices.

Definition at line 3990 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), FunctionalMethods< Container, T >::for_each(), Aleph::HalfPlaneIntersection::from_convex_polygon(), Aleph::Array< T >::insert(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

◆ clipped_cells() [2/4]

Array< Polygon > Aleph::VoronoiDiagramFromDelaunay::clipped_cells	(	const DynList< Point > &	point_set,
		const Polygon &	clip
	)		const

inline

Compute Voronoi and clip its cells against a closed convex polygon.

Parameters

point_set	Input sites.
clip	Closed convex clipping polygon.

Returns: One clipped convex polygon per site.

Definition at line 4085 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ clipped_cells() [3/4]

static Array< Polygon > Aleph::VoronoiDiagramFromDelaunay::clipped_cells	(	const Result &	vor,
		const Polygon &	clip
	)

inlinestatic

Clip Voronoi cells against a closed convex polygon.

Parameters

vor	Voronoi result.
clip	Closed convex clipping polygon.

Returns: One clipped convex polygon per site.

Definition at line 4072 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ clipped_cells() [4/4]

Array< Polygon > Aleph::VoronoiDiagramFromDelaunay::clipped_cells	(	const std::initializer_list< Point >	il,
		const Polygon &	clip
	)		const

inline

Convenience overload with initializer-list input.

Parameters

il	Input sites.
clip	Closed convex clipping polygon.

Returns: One clipped convex polygon per site.

Definition at line 4099 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ clipped_cells_indexed() [1/4]

static Array< ClippedCell > Aleph::VoronoiDiagramFromDelaunay::clipped_cells_indexed	(	const Array< Point > &	sites,
		const Polygon &	clip
	)

inlinestatic

Clip Voronoi cells and return explicit site-indexed records.

Parameters

sites	Voronoi sites.
clip	Closed convex clipping polygon.

Returns: Array of {site_index, site, polygon} records.

Definition at line 4112 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::VoronoiDiagram::clipped_cells(), Aleph::VoronoiDiagramFortune::clipped_cells(), demo_advanced_algorithms(), and main().

◆ clipped_cells_indexed() [2/4]

Array< ClippedCell > Aleph::VoronoiDiagramFromDelaunay::clipped_cells_indexed	(	const DynList< Point > &	point_set,
		const Polygon &	clip
	)		const

inline

Compute/clip Voronoi cells and return site-indexed records.

Parameters

point_set	Input sites.
clip	Closed convex clipping polygon.

Returns: Array of {site_index, site, polygon} records.

Definition at line 4138 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ clipped_cells_indexed() [3/4]

static Array< ClippedCell > Aleph::VoronoiDiagramFromDelaunay::clipped_cells_indexed	(	const Result &	vor,
		const Polygon &	clip
	)

inlinestatic

Clip Voronoi cells (from result) into site-indexed records.

Parameters

vor	Voronoi result.
clip	Closed convex clipping polygon.

Returns: Array of {site_index, site, polygon} records.

Definition at line 4125 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ clipped_cells_indexed() [4/4]

Array< ClippedCell > Aleph::VoronoiDiagramFromDelaunay::clipped_cells_indexed	(	const std::initializer_list< Point >	il,
		const Polygon &	clip
	)		const

inline

Convenience overload with initializer-list input.

Parameters

il	Input sites.
clip	Closed convex clipping polygon.

Returns: Array of {site_index, site, polygon} records.

Definition at line 4151 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ extract_vertices()

static Array< Point > Aleph::VoronoiDiagramFromDelaunay::extract_vertices ( const Polygon & p )

inlinestaticprivate

Extracts vertices from a closed polygon.

Definition at line 3763 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::GeomPolygonUtils::extract_vertices(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

◆ indexed_clipped_cells()

static Array< ClippedCell > Aleph::VoronoiDiagramFromDelaunay::indexed_clipped_cells	(	const Array< Point > &	sites,
		const Array< Polygon > &	polys
	)

inlinestaticprivate

Definition at line 3798 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::VoronoiDiagramFromDelaunay::ClippedCell::polygon, Aleph::Array< T >::reserve(), Aleph::VoronoiDiagramFromDelaunay::ClippedCell::site, Aleph::VoronoiDiagramFromDelaunay::ClippedCell::site_index, and Aleph::Array< T >::size().

◆ is_convex()

static bool Aleph::VoronoiDiagramFromDelaunay::is_convex ( const Array< Point > & verts )

inlinestaticprivate

Checks if a vertex set forms a convex polygon.

Definition at line 3774 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::GeomPolygonUtils::is_convex().

◆ operator()() [1/3]

Result Aleph::VoronoiDiagramFromDelaunay::operator() ( const DelaunayTriangulationBowyerWatson::Result & dt ) const

inline

Build Voronoi from a precomputed Delaunay triangulation.

Parameters

dt	Delaunay triangulation result.

Returns: Voronoi vertices, edges, and per-site cells.

Definition at line 3826 of file geom_algorithms.H.

References Aleph::CCW, circumcenter(), Aleph::divide_and_conquer_partition_dp(), Aleph::GeomTriangleAdjacencyUtils::for_each_sorted_edge_group(), k, Aleph::orientation(), Aleph::Array< T >::reserve(), and Aleph::VoronoiDiagramFromDelaunay::Result::sites.

◆ operator()() [2/3]

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

inline

Build Voronoi from a point set (computes Delaunay first).

Parameters

point_set Input points.

Returns: Voronoi diagram.

Definition at line 3962 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ operator()() [3/3]

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

inline

Convenience overload using initializer-list input.

Parameters

il	Input points.

Returns: Voronoi diagram.

Definition at line 3973 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

Member Data Documentation

◆ delaunay

DelaunayTriangulationBowyerWatson Aleph::VoronoiDiagramFromDelaunay::delaunay

private

Internal Delaunay triangulator.

Definition at line 3730 of file geom_algorithms.H.

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

geom_algorithms.H

Classes

Public Member Functions

Static Public Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Implementation Details

Member Function Documentation

◆ bisector_halfplane_for_site()

◆ circumcenter()

◆ clipped_cells() [1/4]

◆ clipped_cells() [2/4]

◆ clipped_cells() [3/4]

◆ clipped_cells() [4/4]

◆ clipped_cells_indexed() [1/4]

◆ clipped_cells_indexed() [2/4]

◆ clipped_cells_indexed() [3/4]

◆ clipped_cells_indexed() [4/4]

◆ extract_vertices()

◆ indexed_clipped_cells()

◆ is_convex()

◆ operator()() [1/3]

◆ operator()() [2/3]

◆ operator()() [3/3]

Member Data Documentation

◆ delaunay