Aleph::DelaunayTriangulationRandomizedIncremental Class Reference

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
Result	operator() (const std::initializer_list< Point > il) const

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 2513 of file geom_algorithms.H.

Member Typedef Documentation

IndexedTriangle

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

Definition at line 2516 of file geom_algorithms.H.

Result

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

Definition at line 2517 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 2544 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 2568 of file geom_algorithms.H.

References Aleph::CCW, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), 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 2536 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 2596 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), 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

Definition at line 2632 of file geom_algorithms.H.

References adj_of(), Aleph::all(), Aleph::and, Aleph::Array< T >::append(), Aleph::CCW, Aleph::COLLINEAR, Aleph::divide_and_conquer_partition_dp(), 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

Definition at line 2859 of file geom_algorithms.H.

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

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 2552 of file geom_algorithms.H.

References Aleph::and, Aleph::CCW, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), 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 2621 of file geom_algorithms.H.

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

Member Data Documentation

NONE

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

staticconstexprprivate

Definition at line 2520 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