Aleph::RegularTriangulationBowyerWatson Class Reference

Exact regular triangulation (weighted Delaunay) via Bowyer-Watson. More...

#include <geom_algorithms.H>

Classes
struct	Result
struct	WeightedSite
	A 2-D site with an associated weight (squared radius). More...

Public Types
using	IndexedTriangle = DelaunayTriangulationBowyerWatson::IndexedTriangle

Public Member Functions
Result	operator() (const Array< WeightedSite > &weighted_sites) const
	Compute the regular triangulation of a weighted point set.

Static Private Member Functions
static bool	lex_less (const Point &p1, const Point &p2)
static bool	all_collinear (const Array< WeightedSite > &s)
static bool	point_in_power_circle (const Array< Point > &pts, const Array< Geom_Number > &wts, const size_t ia, const size_t ib, const size_t ic, const size_t ip)
	Weighted in-circle (power) predicate.
static Array< WeightedSite >	unique_sites (const Array< WeightedSite > &input)

Detailed Description

Exact regular triangulation (weighted Delaunay) via Bowyer-Watson.

A regular triangulation is the weighted generalization of the Delaunay triangulation. Each site carries a weight wᵢ, and the standard in-circle predicate is replaced by the power test: point (p, wₚ) is inside the ortho-circle of triangle ((a,wₐ),(b,wᵦ),(c,wc)) iff

| ax−px ay−py (ax²+ay²−wₐ)−(px²+py²−wₚ) | | bx−px by−py (bx²+by²−wᵦ)−(px²+py²−wₚ) | > 0 (CCW triangle) | cx−px cy−py (cx²+cy²−wc)−(px²+py²−wₚ) |

Geometrically this is equivalent to lifting each site (xᵢ, yᵢ, wᵢ) to the 3-D point (xᵢ, yᵢ, xᵢ²+yᵢ²−wᵢ) and taking the lower convex hull, then projecting back to 2-D.

When all weights are equal this reduces to the standard Delaunay triangulation.

Policy

• Sites are sorted lexicographically by position; positional duplicates are removed (keeping the first weight encountered).
• Collinear inputs return empty triangulation.
• Output triangles are indexed against the returned deduplicated sites.

Complexity

• Worst-case time: O(n²)
• Typical random input: near O(n log n)
• Space: O(n)

Definition at line 2331 of file geom_algorithms.H.

Member Typedef Documentation

IndexedTriangle

using Aleph::RegularTriangulationBowyerWatson::IndexedTriangle = DelaunayTriangulationBowyerWatson::IndexedTriangle

Definition at line 2341 of file geom_algorithms.H.

Member Function Documentation

all_collinear()

static bool Aleph::RegularTriangulationBowyerWatson::all_collinear ( const Array< WeightedSite > &  s )

inlinestaticprivate

Definition at line 2359 of file geom_algorithms.H.

References Aleph::COLLINEAR, Aleph::orientation(), and Aleph::Array< T >::size().

Referenced by operator()().

lex_less()

static bool Aleph::RegularTriangulationBowyerWatson::lex_less ( const Point &  p1, const Point &  p2  )

inlinestaticprivate

Definition at line 2350 of file geom_algorithms.H.

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

Referenced by unique_sites().

operator()()

Result Aleph::RegularTriangulationBowyerWatson::operator() ( const Array< WeightedSite > &  weighted_sites ) const

inline

Compute the regular triangulation of a weighted point set.

Parameters

weighted_sites

Input weighted sites.

Returns

Deduplicated sites and triangulation indices.

Definition at line 2460 of file geom_algorithms.H.

References all_collinear(), Aleph::divide_and_conquer_partition_dp(), point_in_power_circle(), Aleph::Array< T >::reserve(), Aleph::RegularTriangulationBowyerWatson::Result::sites, and unique_sites().

point_in_power_circle()

static bool Aleph::RegularTriangulationBowyerWatson::point_in_power_circle ( const Array< Point > &  pts, const Array< Geom_Number > &  wts, const size_t  ia, const size_t  ib, const size_t  ic, const size_t  ip  )

inlinestaticprivate

Weighted in-circle (power) predicate.

Tests whether the weighted site at index ip lies inside the ortho-circle of the triangle (ia, ib, ic). The lifted coordinate for each vertex is x²+y²−w, so the third-column entry of the standard in-circle determinant becomes (adx²+ady²) − wₐ + wₚ instead of the unweighted adx²+ady².

Parameters

pts	Positions (including super-triangle vertices).
wts	Weights (super-triangle vertices have weight 0).
ia,ib,ic	Triangle vertex indices.
ip	Query point index.

Returns

true if (ip, wts(ip)) is inside the ortho-circle.

Definition at line 2388 of file geom_algorithms.H.

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

Referenced by operator()().

unique_sites()

static Array< WeightedSite > Aleph::RegularTriangulationBowyerWatson::unique_sites ( const Array< WeightedSite > &  input )

inlinestaticprivate

Definition at line 2432 of file geom_algorithms.H.

References Aleph::all(), Aleph::divide_and_conquer_partition_dp(), lex_less(), Aleph::RegularTriangulationBowyerWatson::WeightedSite::position, Aleph::quicksort_op(), and Aleph::Array< T >::reserve().

Referenced by operator()().

---

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

• geom_algorithms.H