Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Member Functions | Static Public Member Functions | List of all members
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).
Aleph::Array
Simple dynamic array with automatic resizing and functional operations.
Definition tpl_array.H:139
Aleph::Array::append
T & append(const T &data)
Append a copy of data
Definition tpl_array.H:245
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229
Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133
Aleph::Geom_Number
mpq_class Geom_Number
Numeric type used by the geometry module.
Definition point.H:115

Definition at line 10907 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
sitesWeighted point set.
Returns
The power diagram: vertices, edges, and cells.

Definition at line 11001 of file geom_algorithms.H.

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

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