Aleph::PowerDiagram Class Reference

Power diagram (weighted Voronoi diagram). More...

#include <geom_algorithms.H>

Classes
struct	PowerCell
	Represents a cell in the power diagram. More...
struct	PowerEdge
	Represents an edge in the power diagram. More...
struct	Result
	Complete result of a power diagram computation. More...
struct	WeightedSite
	A site with an associated weight (squared radius). More...

Public Member Functions
Result	operator() (const Array< WeightedSite > &sites) const
	Compute the power diagram.

Static Public Member Functions
static Point	power_center (const WeightedSite &a, const WeightedSite &b, const WeightedSite &c)
	Compute the power center of three weighted sites.

Detailed Description

Power diagram (weighted Voronoi diagram).

Each site sᵢ has a weight wᵢ. The power distance from a point p to site sᵢ is ||p - sᵢ||² − wᵢ.

The power diagram partitions the plane into cells where each cell contains points closer (in power distance) to one site than to all others.

Algorithm

1. Compute the regular triangulation (weighted Delaunay) via RegularTriangulationBowyerWatson, which uses the power test (weighted in-circle predicate) to determine triangulation connectivity.
2. For each triangle, compute the power center (the point equidistant in power distance to the three sites).
3. Connect power centers of adjacent triangles to form power edges, using sorted triangle-edge keys.

Complexity

Let T be the number of triangles in the regular triangulation.

• Adjacency extraction: O(T log T).
• Additional processing (centers/cells): O(T + n).

When all weights are equal this reduces to the standard Voronoi diagram.

Example

Array<PowerDiagram::WeightedSite> sites;
sites.append({Point(0,0), Geom_Number(0)});
sites.append({Point(2,0), Geom_Number(1)});
sites.append({Point(0,2), Geom_Number(0)});
PowerDiagram pd;
auto res = pd(sites);
// res.cells contains one cell per site (boundedness depends on input).

Definition at line 10873 of file geom_algorithms.H.

Member Function Documentation

operator()()

Result Aleph::PowerDiagram::operator() ( const Array< WeightedSite > &  sites ) const

inline

Compute the power diagram.

Uses the regular triangulation (weighted Delaunay) so that the triangulation connectivity correctly reflects the site weights.

Parameters

sites

Weighted point set.

Returns

The power diagram: vertices, edges, and cells.

Definition at line 10962 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::GeomTriangleAdjacencyUtils::for_each_sorted_edge_group(), power_center(), Aleph::Array< T >::reserve(), Aleph::PowerDiagram::PowerEdge::site_u, and Aleph::Array< T >::size().

power_center()

static Point Aleph::PowerDiagram::power_center ( const WeightedSite &  a, const WeightedSite &  b, const WeightedSite &  c  )

inlinestatic

Compute the power center of three weighted sites.

The power center is equidistant in power distance to all three sites.

Definition at line 10926 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::PowerDiagram::WeightedSite::position, and Aleph::PowerDiagram::WeightedSite::weight.

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

---

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

• geom_algorithms.H