Constrained Delaunay Triangulation via Sloan's flip-based method. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::ConstrainedDelaunayTriangulation:

Classes
struct	CrossingEdge
	Collect edges that cross segment (u,v) by scanning all mesh edges. More...

struct	IndexedEdge

struct	Result

struct	Tri

Public Types
using	IndexedTriangle = DelaunayTriangulationBowyerWatson::IndexedTriangle

Public Member Functions
Result	operator() (const DynList< Point > &points, const DynList< Segment > &constraints) const
	Compute constrained Delaunay triangulation.

Result	operator() (const std::initializer_list< Point > points, const std::initializer_list< Segment > constraints) const
	Convenience overload using initializer lists.

Static Public Member Functions
static DynList< Triangle >	as_triangles (const Result &result)
	Convert indexed triangulation to geometric triangles.

Static Private Member Functions
static bool	lexicographic_less (const Point &p1, const Point &p2)

static size_t	find_point_index (const Array< Point > &pts, const Point &p)
	Find index of point p in sorted unique array, or NONE.

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 size_t	edge_opposite (const Tri &t, const size_t a, const size_t b)
	Return the local edge index for edge (a,b) in triangle t.

static void	build_adjacency (Array< Tri > &tris, const Array< IndexedTriangle > &dt_tris)
	Build adjacency mesh from DT output.

static bool	edge_exists (const Array< Tri > &tris, const size_t u, const size_t v, size_t &out_tri, size_t &out_local)
	Check if edge (u,v) already exists in the mesh.

static bool	is_convex_quad (const Array< Point > &pts, const size_t a, const size_t b, const size_t c, const size_t d)
	True if diagonal (a,d) in quad (a,b,d) + (a,d,c) forms a convex quad.

static void	flip_edge (Array< Tri > &tris, const size_t tri_a, const size_t tri_b)
	Flip the diagonal of the quad formed by tri_a and tri_b.

static Array< CrossingEdge >	find_crossing_edges (const Array< Point > &pts, const Array< Tri > &tris, const size_t u, const size_t v)

static void	mark_constrained (Array< Tri > &tris, const size_t u, const size_t v)
	Mark edge (u,v) as constrained in the mesh.

static void	enforce_constraint (Array< Point > &pts, Array< Tri > &tris, const size_t u, const size_t v)
	Enforce a single constraint edge (u,v) using Sloan's flip approach.

static void	lawson_flip (const Array< Point > &pts, Array< Tri > &tris)
	Lawson flip pass: restore Delaunay for non-constrained edges.

static Array< Point >	merge_and_deduplicate (const DynList< Point > &points, const DynList< Segment > &constraints)
	Merge input points, constraint endpoints, and constraint-constraint intersection points; then deduplicate.

static Array< IndexedEdge >	map_constraints (const Array< Point > &sites, const DynList< Segment > &constraints)
	Split constraints at interior collinear points.

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

Detailed Description

Constrained Delaunay Triangulation via Sloan's flip-based method.

Computes a triangulation that:

Contains all specified constraint edges.
Is Delaunay for non-constrained edges.
Includes all input points as vertices.

Algorithm (Sloan 1993)

Merge all points and constraint endpoints, deduplicate.
Compute unconstrained Delaunay triangulation (Bowyer-Watson).
Build half-edge adjacency mesh from DT output.
Enforce each constraint by flipping crossing edges.
Restore Delaunay property for non-constrained edges (Lawson flips).
Extract alive triangles and constrained-edge list.

Complexity

Time: O(n^2) worst-case, O(n log n) typical
Space: O(n)

Definition at line 2896 of file geom_algorithms.H.

Member Typedef Documentation

◆ IndexedTriangle

using Aleph::ConstrainedDelaunayTriangulation::IndexedTriangle = DelaunayTriangulationBowyerWatson::IndexedTriangle

Definition at line 2899 of file geom_algorithms.H.

Member Function Documentation

◆ adj_of()

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

inlinestaticprivate

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

Definition at line 2959 of file geom_algorithms.H.

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

Referenced by find_crossing_edges(), and flip_edge().

◆ as_triangles()

static DynList< Triangle > Aleph::ConstrainedDelaunayTriangulation::as_triangles ( const Result & result )

inlinestatic

Convert indexed triangulation to geometric triangles.

Definition at line 3643 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), k, Aleph::ConstrainedDelaunayTriangulation::Result::sites, and Aleph::ConstrainedDelaunayTriangulation::Result::triangles.

Referenced by main(), and TEST_F().

◆ build_adjacency()

static void Aleph::ConstrainedDelaunayTriangulation::build_adjacency	(	Array< Tri > &	tris,
		const Array< IndexedTriangle > &	dt_tris
	)

inlinestaticprivate

Build adjacency mesh from DT output.

Definition at line 2982 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), edge_opposite(), Aleph::GeomTriangleAdjacencyUtils::for_each_sorted_edge_group(), and NONE.

◆ edge_exists()

static bool Aleph::ConstrainedDelaunayTriangulation::edge_exists	(	const Array< Tri > &	tris,
		const size_t	u,
		const size_t	v,
		size_t &	out_tri,
		size_t &	out_local
	)

inlinestaticprivate

Check if edge (u,v) already exists in the mesh.

Definition at line 3024 of file geom_algorithms.H.

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

◆ edge_opposite()

static size_t Aleph::ConstrainedDelaunayTriangulation::edge_opposite	(	const Tri &	t,
		const size_t	a,
		const size_t	b
	)

inlinestaticprivate

Return the local edge index for edge (a,b) in triangle t.

The edge (v[(i+1)%3], v[(i+2)%3]) is "opposite" v[i].

Definition at line 2968 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), NONE, and Aleph::ConstrainedDelaunayTriangulation::Tri::v.

Referenced by build_adjacency(), and edge_exists().

◆ enforce_constraint()

static void Aleph::ConstrainedDelaunayTriangulation::enforce_constraint	(	Array< Point > &	pts,
		Array< Tri > &	tris,
		const size_t	u,
		const size_t	v
	)

inlinestaticprivate

Enforce a single constraint edge (u,v) using Sloan's flip approach.

Definition at line 3280 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ find_crossing_edges()

static Array< CrossingEdge > Aleph::ConstrainedDelaunayTriangulation::find_crossing_edges	(	const Array< Point > &	pts,
		const Array< Tri > &	tris,
		const size_t	u,
		const size_t	v
	)

inlinestaticprivate

Definition at line 3225 of file geom_algorithms.H.

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

◆ find_point_index()

static size_t Aleph::ConstrainedDelaunayTriangulation::find_point_index	(	const Array< Point > &	pts,
		const Point &	p
	)

inlinestaticprivate

Find index of point p in sorted unique array, or NONE.

Definition at line 2936 of file geom_algorithms.H.

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

◆ flip_edge()

static void Aleph::ConstrainedDelaunayTriangulation::flip_edge	(	Array< Tri > &	tris,
		const size_t	tri_a,
		const size_t	tri_b
	)

inlinestaticprivate

Flip the diagonal of the quad formed by tri_a and tri_b.

tri_a contains edge (p, q) at local index la (opposite vertex). tri_b is the neighbor across that edge. After flipping, the new diagonal connects the two "opposite" vertices.

Definition at line 3075 of file geom_algorithms.H.

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

◆ is_convex_quad()

static bool Aleph::ConstrainedDelaunayTriangulation::is_convex_quad	(	const Array< Point > &	pts,
		const size_t	a,
		const size_t	b,
		const size_t	c,
		const size_t	d
	)

inlinestaticprivate

True if diagonal (a,d) in quad (a,b,d) + (a,d,c) forms a convex quad.

The four points of the quadrilateral are a, b, d, c where:

Triangle 1 = (a, b, d) with vertices going around
Triangle 2 = (a, d, c) Convexity means b and c are on opposite sides of (a,d) AND a and d are on opposite sides of (b,c).

Definition at line 3050 of file geom_algorithms.H.

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

◆ lawson_flip()

static void Aleph::ConstrainedDelaunayTriangulation::lawson_flip	(	const Array< Point > &	pts,
		Array< Tri > &	tris
	)

inlinestaticprivate

Lawson flip pass: restore Delaunay for non-constrained edges.

Definition at line 3358 of file geom_algorithms.H.

References Aleph::and, Aleph::CCW, Aleph::COLLINEAR, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), Aleph::in_circle_determinant(), and Aleph::orientation().

◆ lexicographic_less()

static bool Aleph::ConstrainedDelaunayTriangulation::lexicographic_less	(	const Point &	p1,
		const Point &	p2
	)

inlinestaticprivate

Definition at line 2925 of file geom_algorithms.H.

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

Referenced by find_point_index().

◆ local_of()

static size_t Aleph::ConstrainedDelaunayTriangulation::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 2951 of file geom_algorithms.H.

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

◆ map_constraints()

static Array< IndexedEdge > Aleph::ConstrainedDelaunayTriangulation::map_constraints	(	const Array< Point > &	sites,
		const DynList< Segment > &	constraints
	)

inlinestaticprivate

Split constraints at interior collinear points.

Definition at line 3471 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::Segment::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::HTList::Iterator::has_curr(), Aleph::quicksort_op(), and Aleph::Array< T >::size().

◆ mark_constrained()

static void Aleph::ConstrainedDelaunayTriangulation::mark_constrained	(	Array< Tri > &	tris,
		const size_t	u,
		const size_t	v
	)

inlinestaticprivate

Mark edge (u,v) as constrained in the mesh.

Definition at line 3266 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

◆ merge_and_deduplicate()

static Array< Point > Aleph::ConstrainedDelaunayTriangulation::merge_and_deduplicate	(	const DynList< Point > &	points,
		const DynList< Segment > &	constraints
	)

inlinestaticprivate

Merge input points, constraint endpoints, and constraint-constraint intersection points; then deduplicate.

Definition at line 3432 of file geom_algorithms.H.

References Aleph::all(), Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::HTList::Iterator::has_curr(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), and Aleph::segment_intersection_point().

◆ operator()() [1/2]

Result Aleph::ConstrainedDelaunayTriangulation::operator()	(	const DynList< Point > &	points,
		const DynList< Segment > &	constraints
	)		const

inline

Compute constrained Delaunay triangulation.

Parameters

points	Input points.
constraints	Constraint segments (must connect input points).

Returns: Unique sites, triangulation indices, and constrained edge list.

Definition at line 3545 of file geom_algorithms.H.

References Aleph::and, Aleph::DynList< T >::append(), Aleph::COLLINEAR, Aleph::divide_and_conquer_partition_dp(), Aleph::orientation(), and Aleph::ConstrainedDelaunayTriangulation::Result::sites.

◆ operator()() [2/2]

Result Aleph::ConstrainedDelaunayTriangulation::operator()	(	const std::initializer_list< Point >	points,
		const std::initializer_list< Segment >	constraints
	)		const

inline

Convenience overload using initializer lists.

Definition at line 3626 of file geom_algorithms.H.

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

Member Data Documentation

◆ NONE

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

staticconstexprprivate

Definition at line 2915 of file geom_algorithms.H.

Referenced by adj_of(), build_adjacency(), edge_exists(), edge_opposite(), find_crossing_edges(), find_point_index(), flip_edge(), and local_of().

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

geom_algorithms.H

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Private Member Functions

Static Private Attributes

Detailed Description

Algorithm (Sloan 1993)

Complexity

Member Typedef Documentation

◆ IndexedTriangle

Member Function Documentation

◆ adj_of()

◆ as_triangles()

◆ build_adjacency()

◆ edge_exists()

◆ edge_opposite()

◆ enforce_constraint()

◆ find_crossing_edges()

◆ find_point_index()

◆ flip_edge()

◆ is_convex_quad()

◆ lawson_flip()

◆ lexicographic_less()

◆ local_of()

◆ map_constraints()

◆ mark_constrained()

◆ merge_and_deduplicate()

◆ operator()() [1/2]

◆ operator()() [2/2]

Member Data Documentation

◆ NONE