# `Expresso.Element.Chart.Voronoi`
[🔗](https://github.com/rellen/expresso/blob/main/lib/expresso/element/chart/voronoi.ex#L1)

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:

1. 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.
2. Make the power diagram of the sites. The cell of a site is the
   container, clipped by one half-plane for each other site.
3. 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.
4. 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.
5. 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.

# `box`

```elixir
@type box() :: %{left: number(), right: number(), top: number(), bottom: number()}
```

A box, as the edges of a chart give it

# `item`

```elixir
@type item() :: %{id: term(), value: number(), children: [item()]}
```

A part to lay out. A leaf has a value, and a group has the sum of the
values of its children.

# `point`

```elixir
@type point() :: {float(), float()}
```

A point in the units of the SVG

# `polygon`

```elixir
@type polygon() :: [point()]
```

A convex polygon, as its corners in order

# `shape`

```elixir
@type shape() :: :rectangle | :circle | :hexagon | [{number(), number()}]
```

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

# `area`

```elixir
@spec area(polygon()) :: float()
```

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.0

# `centroid`

```elixir
@spec centroid(polygon()) :: point()
```

Return 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_shape`

```elixir
@spec check_shape(term()) :: :ok | {:error, String.t()}
```

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`

```elixir
@spec clip(polygon(), {number(), number(), number()}) :: polygon()
```

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}]

# `container`

```elixir
@spec container(shape(), box()) :: polygon()
```

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}]

# `diagram`

```elixir
@spec diagram([point()], [number()], polygon()) :: [polygon()]
```

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.

# `error`

```elixir
@spec error([polygon()], [number()], number()) :: float()
```

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

# `inside?`

```elixir
@spec inside?(point(), polygon()) :: boolean()
```

Return true when a point is inside a convex polygon or on its edge

# `layout`

```elixir
@spec layout([item()], polygon()) :: %{required(term()) =&gt; polygon()}
```

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

# `limit`

```elixir
@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.01

# `pole`

```elixir
@spec pole(polygon()) :: {point(), float()}
```

Return 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}

# `shape`

```elixir
@spec shape(term()) :: {:ok, shape()} | {:error, String.t()}
```

Check the `shape` option of a chart, for the DSL

    iex> Expresso.Element.Chart.Voronoi.shape(:circle)
    {:ok, :circle}

---

*Consult [api-reference.md](api-reference.md) for complete listing*