The layout of a Voronoi treemap: a convex polygon divided into cells, with an area in proportion to the value of each part
A Voronoi treemap divides a container into one cell for each part of the top level. Each group then divides its own cell for its parts, down to the leaves. A cell has no fixed direction, so the cell of a small part does not become a thin strip, as a rectangle of a squarified treemap can.
The layout uses the algorithm of Nocaj and Brandes, "Computing Voronoi Treemaps: Faster, Simpler, and Resolution-independent" (2012). In each container, the algorithm does these steps:
- Put one site for each part inside the container. The sites come from the Halton sequence of the bases 2 and 3, so the same input gives the same layout.
- Make the power diagram of the sites. The cell of a site is the container, clipped by one half-plane for each other site.
- Move each site to the centroid of its cell, and change its weight by the ratio of the target area to the area of its cell. A change is at most 50 percent. When the error becomes larger than in the iteration before, the most change becomes smaller, so the weights do not swing from side to side. Then make sure that each site stays in its own cell, and do step 2 again. After 50 iterations, the sites stay where they are, and only the weights change.
- Stop when the error is less than 1 percent and each part has a cell, or after 200 iterations. The error is the sum of the differences between each area and its target, as a part of the area of the container. A small part can lose its cell while the error stays below the limit, so a diagram with an empty cell does not stop the iterations.
- When the error is still more than 1 percent, start again with the next sites of the Halton sequence, for at most 6 starts. The layout keeps the diagram with the smallest error.
The error of each area is therefore less than the error of the diagram. A part with the value 0 gets no cell.
The sites stop because a moving site can keep the small cells in a cycle. With one large part and three small parts in a box, the small parts can pass area among themselves until the last iteration, and the error stays near 3 percent after each start. With fixed sites, the weights alone bring each area to its target.
A very thin container, such as a triangle with one side of a few units and two sides of hundreds, leaves little room to move the sites. Its error can stay above the limit after each start, and the layout then returns the diagram with the smallest error. A container that is a box, a circle, a hexagon or a polygon with no sharp corner reaches the limit.
The container must be convex. A cell is convex before the clip, so a
convex container gives convex cells, and each group can divide its cell
again. The dent of a concave container can cut a cell into two pieces.
check_shape/1 refuses a concave polygon.
The coordinates are the units of the SVG, and the y axis goes down. Each polygon has its corners in the order that gives it a positive area.
Summary
Types
A box, as the edges of a chart give it
A part to lay out. A leaf has a value, and a group has the sum of the values of its children.
A point in the units of the SVG
A convex polygon, as its corners in order
The shape of the container: the box, a circle or a hexagon in the box, or the corners of a polygon in a unit box
Functions
Return the area of a polygon
Return the centroid of a polygon
Check a shape of a container
Clip a convex polygon to the half-plane a x + b y <= c
Return the polygon of a shape in a box
Return the power diagram of weighted sites, clipped to a convex polygon
Return the error of the cells of one container: the sum of the differences between each area and its target, as a part of the area of the container
Return true when a point is inside a convex polygon or on its edge
Divide a convex polygon into the cells of a tree of parts
Return the limit of the error of a diagram, as a part of the area of its container
Return the pole of inaccessibility of a convex polygon, and its distance to the nearest edge
Check the shape option of a chart, for the DSL
Types
A box, as the edges of a chart give it
A part to lay out. A leaf has a value, and a group has the sum of the values of its children.
A point in the units of the SVG
@type polygon() :: [point()]
A convex polygon, as its corners in order
The shape of the container: the box, a circle or a hexagon in the box, or the corners of a polygon in a unit box
Functions
Return the area of a polygon
iex> Expresso.Element.Chart.Voronoi.area([{0.0, 0.0}, {4.0, 0.0}, {4.0, 3.0}])
6.0Return the centroid of a polygon
iex> Expresso.Element.Chart.Voronoi.centroid([{0.0, 0.0}, {4.0, 0.0}, {4.0, 2.0}, {0.0, 2.0}])
{2.0, 1.0}Check a shape of a container
A list of points must have at least 3 points, each in the unit box from 0 to 1. The polygon must not cross itself, and it must be convex.
iex> Expresso.Element.Chart.Voronoi.check_shape(:hexagon)
:ok
iex> Expresso.Element.Chart.Voronoi.check_shape([{0, 0}, {1, 0}, {0.5, 1}])
:ok
iex> {:error, _message} = Expresso.Element.Chart.Voronoi.check_shape([{0, 0}, {1, 0}])Clip a convex polygon to the half-plane a x + b y <= c
iex> square = [{0.0, 0.0}, {2.0, 0.0}, {2.0, 2.0}, {0.0, 2.0}]
iex> Expresso.Element.Chart.Voronoi.clip(square, {1, 0, 1})
[{1.0, 0.0}, {1.0, 2.0}, {0.0, 2.0}, {0.0, 0.0}]Return the polygon of a shape in a box
A circle and a hexagon have their center at the center of the box, and the largest size that fits it. The points of a list go into the largest square at the center of the box, so the polygon keeps its proportions.
iex> box = %{left: 0, right: 200, top: 0, bottom: 100}
iex> Expresso.Element.Chart.Voronoi.container([{0, 0}, {1, 0}, {0.5, 1}], box)
[{50.0, 0.0}, {150.0, 0.0}, {100.0, 100.0}]Return the power diagram of weighted sites, clipped to a convex polygon
The cell of a site holds each point p of the polygon where
|p - site|² - weight is the least of all the sites.
Return the error of the cells of one container: the sum of the differences between each area and its target, as a part of the area of the container
Return true when a point is inside a convex polygon or on its edge
Divide a convex polygon into the cells of a tree of parts
Return a map from the id of each part to its cell. A group gets the cell that holds the cells of its parts. A part with the value 0, and a group with the sum 0, get an empty list.
iex> square = [{0.0, 0.0}, {10.0, 0.0}, {10.0, 10.0}, {0.0, 10.0}]
iex> cells = Expresso.Element.Chart.Voronoi.layout([%{id: :a, value: 1, children: []}], square)
iex> cells.a == square
true@spec limit() :: float()
Return the limit of the error of a diagram, as a part of the area of its container
iex> Expresso.Element.Chart.Voronoi.limit()
0.01Return the pole of inaccessibility of a convex polygon, and its distance to the nearest edge
The pole is the point inside the polygon that is farthest from its edges,
so a label at the pole has the most room. The search of Agafonkin
(polylabel) divides the box of the polygon into squares, and it divides
each square again while the square can hold a better point. It stops at a
precision of half a unit.
iex> square = [{0.0, 0.0}, {10.0, 0.0}, {10.0, 10.0}, {0.0, 10.0}]
iex> {{x, y}, distance} = Expresso.Element.Chart.Voronoi.pole(square)
iex> {round(x), round(y), round(distance)}
{5, 5, 5}Check the shape option of a chart, for the DSL
iex> Expresso.Element.Chart.Voronoi.shape(:circle)
{:ok, :circle}