Function Repository Resource:

PowerDiagram

Source Notebook

Generate the power diagram of a set of circles

Contributed by: Jan Mangaldan

ResourceFunction["PowerDiagram"][{c₁,c₂,…}]

gives a MeshRegion representing the power diagram of the circles c₁,c₂, ….

ResourceFunction["PowerDiagram"][{c₁,c₂,…},{{x_min,x_max},…}]

clips the mesh to the bounds [x_min,x_max]×⋯.

Details

The circles c_i can be Circle or Disk objects.

Point objects are treated as circles with zero radius.

A power diagram is also known as Dirichlet cell complex, Laguerre diagram and Laguerre-Voronoi diagram; it is a generalization of a Voronoi diagram.

A power diagram can be considered as a weighted Voronoi diagram of the circles' centers, with the radii of the circles as weights.

A power diagram consists of n convex cells, each associated with a circle c_i, such that a point p_i belongs to the cell associated with c_i when c_i is the circle that minimizes the circle power of p_i.

The cells associated with the outer circles will be unbounded, but only a bounded range will be returned. If no explicit range {{x_min,x_max},…} is given, a range is computed automatically.

The cells will be convex polygons in 2D.

ResourceFunction["PowerDiagram"] takes the same options as MeshRegion.

Examples

Basic Examples (2)

Generate the power diagram of a set of circles:

In[1]:=

$circles = Table[Circle[RandomVariate[NormalDistribution[], 2], RandomReal[{0, 1/2}]], {10}]; \[ScriptCapitalR] = ResourceFunction["PowerDiagram"][circles]$

Out[1]=

Show the power diagram with the generating circles:

In[2]:=

$Show[\[ScriptCapitalR], Graphics[{Orange, circles}]]$

Out[2]=

Scope (2)

Create a power diagram from a set of disks:

In[3]:=

$cl = Table[Disk[RandomReal[{-2, 2}, {2}], RandomReal[{0, 1/4}]], {20}]; \[ScriptCapitalR] = ResourceFunction["PowerDiagram"][cl]$

Out[3]=

Basic properties:

In[4]:=

${RegionQ[\[ScriptCapitalR]], MeshRegionQ[\[ScriptCapitalR]]}$

Out[4]=

Power diagrams are full dimensional:

In[5]:=

${RegionDimension[\[ScriptCapitalR]], RegionEmbeddingDimension[\[ScriptCapitalR]]}$

Out[5]=

Power diagrams are bounded by their clipping values:

In[6]:=

${BoundedRegionQ[\[ScriptCapitalR]], RegionBounds[\[ScriptCapitalR]]}$

Out[6]=

Generate the power diagram of a mixture of Circle and Disk objects:

In[7]:=

cl = Table[
RandomChoice[{Circle, Disk}][
RandomVariate[NormalDistribution[], 2], RandomReal[{0, 1/2}]], {10}];
ResourceFunction["PowerDiagram"][cl]

Out[7]=

Options (10)

MeshCellHighlight (2)

MeshCellHighlight allows you to specify highlighting for parts of a PowerDiagram:

In[8]:=

Out[8]=

Individual cells can be highlighted using their cell index:

In[9]:=

Out[9]=

Or by the cell itself:

In[10]:=

Out[10]=

MeshCellLabel (2)

MeshCellLabel can be used to label parts of a PowerDiagram:

In[11]:=

Out[11]=

Individual cells can be labeled using their cell index:

In[12]:=

Out[12]=

Or by the cell itself:

In[13]:=

Out[13]=

MeshCellMarker (2)

MeshCellMarker can be used to assign values to parts of a PowerDiagram:

In[14]:=

Out[14]=

Use MeshCellLabel to show the markers:

In[15]:=

ResourceFunction["PowerDiagram"][
Table[Disk[RandomReal[1, 2], RandomReal[]], {5}], MeshCellMarker -> {{0, 1} -> 1, {0, 2} -> 2, {0, 3} -> 3, {0, 4} -> 4, {0, 5} -> 5}, MeshCellLabel -> {0 -> "Marker"}]

Out[15]=

MeshCellStyle (2)

MeshCellStyle allows you to specify styling for parts of a PowerDiagram:

In[16]:=

Out[16]=

Individual cells can be highlighted using their cell index:

In[17]:=

Out[17]=

Or by the cell itself:

In[18]:=

Out[18]=

PlotTheme (2)

Use a theme with grid lines and a legend:

In[19]:=

Out[19]=

Use a theme to draw a wireframe:

In[20]:=

Out[20]=

Properties and Relations (4)

The output of PowerDiagram is always a full-dimensional MeshRegion:

In[21]:=

Out[21]=

In[22]:=

Out[22]=

The power diagram of two circles is composed of two half-planes divided by the radical line of the two circles:

In[23]:=

$radicalLine[Circle[c1_, r1_], Circle[c2_, r2_]] := With[{u = 1/2 (1 + (r1^2 - r2^2)/SquaredEuclideanDistance[c1, c2])}, InfiniteLine[(1 - u) c1 + u c2, Cross[c2 - c1]]] Show[ResourceFunction[ "PowerDiagram"][{Circle[{0, 0}, 1], Circle[{2, 2}, 1/3]}], Graphics[{Brown, Circle[{0, 0}, 1], Circle[{2, 2}, 1/3], Directive[Dashed, Orange], radicalLine[Circle[{0, 0}, 1], Circle[{2, 2}, 1/3]]}]]$

Out[23]=

If one circle encloses the other, the cell corresponding to the inner circle is empty:

In[24]:=

Show[ResourceFunction[
"PowerDiagram"][{Circle[{0, 0}, 1], Circle[{2/5, 1/2}, 1/6]}, {{-3/2, 3/2}, {-3/2, 3/2}}], Graphics[{Brown, Circle[{0, 0}, 1], Circle[{2/5, 1/2}, 1/6], Directive[Dashed, Orange], radicalLine[Circle[{0, 0}, 1], Circle[{2/5, 1/2}, 1/6]]}]]

Out[24]=

The power diagram of a set of circles all having the same radii is equivalent to the VoronoiMesh of the circles' centers:

In[25]:=

Out[25]=

The resource function PowerTriangulation is the dual of PowerDiagram:

In[26]:=

circles = Table[Circle[RandomReal[{-7/2, 7/2}, 2], RandomReal[1/3]], {30}];
pt = HighlightMesh[
ResourceFunction["PowerTriangulation"][circles], {Style[0, Black], Style[1, Orange], Style[2, Opacity[0.5]]}];
pd = HighlightMesh[
ResourceFunction["PowerDiagram"][circles], {Style[1, Green], Style[2, Opacity[0.2]]}];
Show[pt, pd, Graphics[{Brown, circles}]]

Out[29]=

Version History

1.0.0 – 18 January 2021

Source Metadata

Citation:
- Aurenhammer F., "Power Diagrams: Properties, Algorithms and Applications." SIAM Journal on Computing, vol. 16, no. 1, 78–96, 1987. DOI: 10.1137/0216006
- Sugihara K., "Three-dimensional convex hull as a fruitful source of diagrams." Theoretical Computer Science, vol. 35, no. 2, 325-337, 2000. DOI: 10.1016/S0304-3975(99)00202-9

Related Resources

Author Notes

The current implementation is only limited to the 2D case. An extension to 3D is left for a future update.

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License

Wolfram Function Repository

PowerDiagram

Details