Fortune sweep-line Voronoi construction. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::VoronoiDiagramFortune:

Classes
struct	Arc
	Arc in the beach-line state structure. More...

struct	Event
	Forward declaration of beach-line arc. More...

struct	EventCmp
	Comparator for prioritizing events in the sweep-line. More...

struct	TriKey
	Key for identifying a triangle by its vertex indices. More...

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.

Array< ClippedCell >	clipped_cells (const std::initializer_list< Point > il, const Polygon &clip) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Static Private Member Functions
static double	as_double (const Geom_Number &v)

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

static DelaunayTriangulationBowyerWatson::IndexedTriangle	normalized_triangle (const size_t i, const size_t j, const size_t k, const Array< Point > &sites)

static double	breakpoint_x (const Point &left_site, const Point &right_site, const double sweepline_y)

static Arc *	locate_arc (Arc *head, const Array< Point > &sites, const double x, const double sweepline_y)

static void	invalidate_circle_event (Arc *arc)

static void	enqueue_circle_event (Arc arc, const double sweepline_y, const Array< Point > &sites, DynBinHeap< Event , EventCmp > &queue, Array< std::unique_ptr< Event > > &event_pool, size_t &next_event_id)

static bool	is_valid_delaunay (const DelaunayTriangulationBowyerWatson::Result &dt)
	Validates if a triangulation holds the Delaunay property (empty circumcircle).

static DelaunayTriangulationBowyerWatson::Result	triangulate_sweep (const Array< Point > &sites)

Private Attributes
VoronoiDiagramFromDelaunay	voronoi_

DelaunayTriangulationBowyerWatson	fallback_

Static Private Attributes
static constexpr double	kEps = 1e-9

Detailed Description

Fortune sweep-line Voronoi construction.

This class computes a Delaunay triangulation via Fortune's beach-line sweep (site + circle events) and then reuses VoronoiDiagramFromDelaunay to build Voronoi vertices/edges/cells, avoiding duplicated dual logic.

Fortune's algorithm is a sweep-line algorithm for generating Voronoi diagrams in O(n log n) time.

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

Definition at line 4237 of file geom_algorithms.H.

Member Typedef Documentation

◆ Cell

using Aleph::VoronoiDiagramFortune::Cell = VoronoiDiagramFromDelaunay::Cell

Type for Voronoi cells.

Definition at line 4241 of file geom_algorithms.H.

◆ ClippedCell

using Aleph::VoronoiDiagramFortune::ClippedCell = VoronoiDiagramFromDelaunay::ClippedCell

Type for clipped Voronoi cells.

Definition at line 4242 of file geom_algorithms.H.

◆ Edge

using Aleph::VoronoiDiagramFortune::Edge = VoronoiDiagramFromDelaunay::Edge

Type for Voronoi edges.

Definition at line 4240 of file geom_algorithms.H.

◆ Result

using Aleph::VoronoiDiagramFortune::Result = VoronoiDiagramFromDelaunay::Result

Complete result structure.

Definition at line 4243 of file geom_algorithms.H.

Member Function Documentation

◆ all_collinear()

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

inlinestaticprivate

Definition at line 4322 of file geom_algorithms.H.

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

Referenced by triangulate_sweep().

◆ as_double()

static double Aleph::VoronoiDiagramFortune::as_double ( const Geom_Number & v )

inlinestaticprivate

Definition at line 4317 of file geom_algorithms.H.

References Aleph::geom_number_to_double().

Referenced by breakpoint_x(), enqueue_circle_event(), and triangulate_sweep().

◆ breakpoint_x()

static double Aleph::VoronoiDiagramFortune::breakpoint_x	(	const Point &	left_site,
		const Point &	right_site,
		const double	sweepline_y
	)

inlinestaticprivate

Definition at line 4343 of file geom_algorithms.H.

References ah_domain_error_if, as_double(), Aleph::blossom_maximum_cardinality_matching(), and kEps.

Referenced by locate_arc().

◆ clipped_cells() [1/2]

Array< ClippedCell > Aleph::VoronoiDiagramFortune::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 4683 of file geom_algorithms.H.

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

Referenced by clipped_cells(), and TEST_F().

◆ clipped_cells() [2/2]

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

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 4689 of file geom_algorithms.H.

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

◆ enqueue_circle_event()

static void Aleph::VoronoiDiagramFortune::enqueue_circle_event	(	Arc *	arc,
		const double	sweepline_y,
		const Array< Point > &	sites,
		DynBinHeap< Event *, EventCmp > &	queue,
		Array< std::unique_ptr< Event > > &	event_pool,
		size_t &	next_event_id
	)

inlinestaticprivate

Definition at line 4417 of file geom_algorithms.H.

References as_double(), Aleph::blossom_maximum_cardinality_matching(), Aleph::VoronoiDiagramFortune::Arc::circle, Aleph::CW, Aleph::Point::get_x(), Aleph::Point::get_y(), invalidate_circle_event(), kEps, Aleph::VoronoiDiagramFortune::Arc::next, Aleph::orientation(), Aleph::VoronoiDiagramFortune::Arc::prev, Aleph::DynBinHeap< T, Compare >::put(), r, Aleph::VoronoiDiagramFortune::Arc::site, and Aleph::VoronoiDiagramFortune::Event::y.

Referenced by triangulate_sweep().

◆ invalidate_circle_event()

static void Aleph::VoronoiDiagramFortune::invalidate_circle_event ( Arc * arc )

inlinestaticprivate

Definition at line 4408 of file geom_algorithms.H.

References Aleph::and, Aleph::VoronoiDiagramFortune::Arc::circle, and Aleph::VoronoiDiagramFortune::Event::valid.

Referenced by enqueue_circle_event(), and triangulate_sweep().

◆ is_valid_delaunay()

static bool Aleph::VoronoiDiagramFortune::is_valid_delaunay ( const DelaunayTriangulationBowyerWatson::Result & dt )

inlinestaticprivate

Validates if a triangulation holds the Delaunay property (empty circumcircle).

Parameters

dt	The triangulation result to validate.

Returns: True if it is a valid Delaunay triangulation, false otherwise.

Definition at line 4485 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::CCW, Aleph::COLLINEAR, Aleph::CW, Aleph::in_circle_determinant(), k, Aleph::orientation(), Aleph::DelaunayTriangulationBowyerWatson::Result::sites, and Aleph::DelaunayTriangulationBowyerWatson::Result::triangles.

Referenced by operator()().

◆ locate_arc()

static Arc * Aleph::VoronoiDiagramFortune::locate_arc	(	Arc *	head,
		const Array< Point > &	sites,
		const double	x,
		const double	sweepline_y
	)

inlinestaticprivate

Definition at line 4381 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), breakpoint_x(), kEps, Aleph::VoronoiDiagramFortune::Arc::next, and Aleph::VoronoiDiagramFortune::Arc::prev.

Referenced by triangulate_sweep().

◆ normalized_triangle()

static DelaunayTriangulationBowyerWatson::IndexedTriangle Aleph::VoronoiDiagramFortune::normalized_triangle	(	const size_t	i,
		const size_t	j,
		const size_t	k,
		const Array< Point > &	sites
	)

inlinestaticprivate

Definition at line 4335 of file geom_algorithms.H.

References Aleph::CW, k, and Aleph::orientation().

Referenced by triangulate_sweep().

◆ operator()() [1/2]

Result Aleph::VoronoiDiagramFortune::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 4649 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), fallback_, is_valid_delaunay(), triangulate_sweep(), and voronoi_.

◆ operator()() [2/2]

Result Aleph::VoronoiDiagramFortune::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 4669 of file geom_algorithms.H.

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

◆ triangulate_sweep()

static DelaunayTriangulationBowyerWatson::Result Aleph::VoronoiDiagramFortune::triangulate_sweep ( const Array< Point > & sites )

inlinestaticprivate

Member Data Documentation

◆ fallback_

DelaunayTriangulationBowyerWatson Aleph::VoronoiDiagramFortune::fallback_

private

Definition at line 4315 of file geom_algorithms.H.

Referenced by operator()().

◆ kEps

constexpr double Aleph::VoronoiDiagramFortune::kEps = 1e-9

staticconstexprprivate

Definition at line 4312 of file geom_algorithms.H.

Referenced by breakpoint_x(), enqueue_circle_event(), locate_arc(), and triangulate_sweep().

◆ voronoi_

VoronoiDiagramFromDelaunay Aleph::VoronoiDiagramFortune::voronoi_

private

Definition at line 4314 of file geom_algorithms.H.

Referenced by operator()().

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

geom_algorithms.H

Classes

Public Types

Public Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Cell

◆ ClippedCell

◆ Edge

◆ Result

Member Function Documentation

◆ all_collinear()

◆ as_double()

◆ breakpoint_x()

◆ clipped_cells() [1/2]

◆ clipped_cells() [2/2]

◆ enqueue_circle_event()

◆ invalidate_circle_event()

◆ is_valid_delaunay()

◆ locate_arc()

◆ normalized_triangle()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ triangulate_sweep()

Member Data Documentation

◆ fallback_

◆ kEps

◆ voronoi_