O(n log n) expected-time Delaunay's triangulation. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::DelaunayTriangulationRandomizedIncremental:

Classes
struct	DagNode

struct	Tri

Public Types
using	IndexedTriangle = DelaunayTriangulationBowyerWatson::IndexedTriangle

using	Result = DelaunayTriangulationBowyerWatson::Result

Public Member Functions
Result	operator() (const DynList< Point > &point_set) const
	Computes the Delaunay triangulation of a set of points.

Result	operator() (const std::initializer_list< Point > il) const
	Computes the Delaunay triangulation from an initializer list of points.

Static Private Member Functions
static size_t	local_of (const Tri &t, const size_t id)
	Return local index (0,1,2) of vertex id in triangle t, or NONE.

static size_t	adj_of (const Tri &t, const size_t n)
	Return the local index of the edge shared with neighbor n.

static bool	point_in_tri (const Array< Point > &pts, const Tri &t, const size_t pidx)
	True if point p is inside or on triangle t (using orientation tests).

static bool	in_cc (const Array< Point > &pts, const size_t ia, const size_t ib, const size_t ic, const size_t ip)
	Standard in-circumcircle test using exact in_circle_determinant.

static size_t	locate (const Array< Point > &pts, const Array< Tri > &tris, const Array< DagNode > &dag, const size_t pidx, const size_t root)
	Locate the leaf triangle containing point pidx via a DAG walk.

static void	remap_adj (Array< Tri > &tris, const size_t ot, const size_t nt)
	Update neighbor n of the old triangle ot to point to a new triangle nt.

Static Private Attributes
static constexpr size_t	NONE = ~static_cast<size_t>(0)

Detailed Description

O(n log n) expected-time Delaunay's triangulation.

Uses randomized incremental insertion with a history DAG for O(log n) expected point location and adjacency-based Lawson flipping.

Complexity

Expected time: O(n log n)
Worst-case time: O(n²) (extremely unlikely with random shuffle)
Space: O(n)

Definition at line 2505 of file geom_algorithms.H.

Member Typedef Documentation

◆ IndexedTriangle

using Aleph::DelaunayTriangulationRandomizedIncremental::IndexedTriangle = DelaunayTriangulationBowyerWatson::IndexedTriangle

Definition at line 2508 of file geom_algorithms.H.

◆ Result

using Aleph::DelaunayTriangulationRandomizedIncremental::Result = DelaunayTriangulationBowyerWatson::Result

Definition at line 2509 of file geom_algorithms.H.

Member Function Documentation

◆ adj_of()

static size_t Aleph::DelaunayTriangulationRandomizedIncremental::adj_of	(	const Tri &	t,
		const size_t	n
	)

inlinestaticprivate

Return the local index of the edge shared with neighbor n.

Definition at line 2537 of file geom_algorithms.H.

References Aleph::DelaunayTriangulationRandomizedIncremental::Tri::adj, and NONE.

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

◆ in_cc()

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

inlinestaticprivate

Standard in-circumcircle test using exact in_circle_determinant.

Works correctly with finite super-triangle vertices (placed 16× beyond the bounding box) — no special half-plane handling needed.

Definition at line 2559 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()().

◆ local_of()

static size_t Aleph::DelaunayTriangulationRandomizedIncremental::local_of	(	const Tri &	t,
		const size_t	id
	)

inlinestaticprivate

Return local index (0,1,2) of vertex id in triangle t, or NONE.

Definition at line 2528 of file geom_algorithms.H.

References NONE, and Aleph::DelaunayTriangulationRandomizedIncremental::Tri::v.

◆ locate()

static size_t Aleph::DelaunayTriangulationRandomizedIncremental::locate	(	const Array< Point > &	pts,
		const Array< Tri > &	tris,
		const Array< DagNode > &	dag,
		const size_t	pidx,
		const size_t	root
	)

inlinestaticprivate

Locate the leaf triangle containing point pidx via a DAG walk.

Walk from root through dead (internal) nodes toward alive (leaf) triangles. Both dead and alive children are considered, so the walk follows the correct branch even through intermediate dead nodes.

Definition at line 2594 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::is_empty(), point_in_tri(), root(), and Aleph::Array< T >::size().

Referenced by operator()().

◆ operator()() [1/2]

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

inline

Computes the Delaunay triangulation of a set of points.

This implementation uses a randomized incremental algorithm with a DAG for point location.

Parameters

point_set The input set of points.

Returns: A Result object containing unique sites and the triangulated indices.

Definition at line 2640 of file geom_algorithms.H.

References adj_of(), Aleph::all(), Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::CCW, Aleph::COLLINEAR, Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::HTList::Iterator::has_curr(), in_cc(), locate(), NONE, Aleph::orientation(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), and V.

◆ operator()() [2/2]

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

inline

Computes the Delaunay triangulation from an initializer list of points.

Parameters

il	The input points.

Returns: A Result object containing unique sites and the triangulated indices.

Definition at line 2875 of file geom_algorithms.H.

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

◆ point_in_tri()

static bool Aleph::DelaunayTriangulationRandomizedIncremental::point_in_tri	(	const Array< Point > &	pts,
		const Tri &	t,
		const size_t	pidx
	)

inlinestaticprivate

True if point p is inside or on triangle t (using orientation tests).

Definition at line 2546 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::CCW, Aleph::CW, Aleph::orientation(), and Aleph::DelaunayTriangulationRandomizedIncremental::Tri::v.

Referenced by locate().

◆ remap_adj()

static void Aleph::DelaunayTriangulationRandomizedIncremental::remap_adj	(	Array< Tri > &	tris,
		const size_t	ot,
		const size_t	nt
	)

inlinestaticprivate

Update neighbor n of the old triangle ot to point to a new triangle nt.

Definition at line 2620 of file geom_algorithms.H.

References adj_of(), Aleph::blossom_maximum_cardinality_matching(), and NONE.

Member Data Documentation

◆ NONE

constexpr size_t Aleph::DelaunayTriangulationRandomizedIncremental::NONE = ~static_cast<size_t>(0)

staticconstexprprivate

Definition at line 2512 of file geom_algorithms.H.

Referenced by adj_of(), local_of(), operator()(), and remap_adj().

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

geom_algorithms.H

Classes

Public Types

Public Member Functions

Static Private Member Functions

Static Private Attributes

Detailed Description

Complexity

Member Typedef Documentation

◆ IndexedTriangle

◆ Result

Member Function Documentation

◆ adj_of()

◆ in_cc()

◆ local_of()

◆ locate()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ point_in_tri()

◆ remap_adj()

Member Data Documentation

◆ NONE