# `Cauldron2D.Sectors.Bsp`
[🔗](https://github.com/jaman/cauldron/blob/v0.2.2/cauldron_2d/lib/cauldron_2d/sectors/bsp.ex#L1)

A binary space partition of a sector map: the order to draw it in from any point, front
to back, and the convex piece any point is in.

    {segs, subsectors, nodes} = Cauldron2D.Sectors.Bsp.build(map)
    Cauldron2D.Sectors.Bsp.locate(map, {x, y})

The level is cut by lines into convex **subsectors**, each a run of **segs** — pieces of
the map's lines — in one sector. A **node** is a cutting line `{x, y, dx, dy}` with a
child on each side and the bounding box of each child; the last node is the root.

  * a seg is `%{from: {x, y}, to: {x, y}, line: index, side: 0 | 1, offset: distance}`,
    where `side` is the side of its line it shows and `offset` how far along that side
    it starts
  * a subsector is `%{first: index, count: n, sector: index}`, its segs being
    `first..first + count - 1`
  * a node is `%{x:, y:, dx:, dy:, boxes: {front_box, back_box}, children: {front, back}}`,
    a box `{top, bottom, left, right}` and a child `{:node, index}` or `{:leaf, index}`;
    the front is the right of the cutting line, as `Cauldron2D.Sectors.Map.point_side/2`
    reckons it

`build/2` builds one from a map's lines. A level that carries its own BSP is read into
the same shapes and used as it is.

# `box`

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

# `child`

```elixir
@type child() :: {:node, non_neg_integer()} | {:leaf, non_neg_integer()}
```

# `build`

```elixir
@spec build(Cauldron2D.Sectors.Map.t(), keyword()) :: {tuple(), tuple(), tuple()}
```

A BSP for `map` built from its lines: `{segs, subsectors, nodes}` as tuples.

Cutting lines are chosen among the segs' own lines, weighing how many segs a cut would
split against how unevenly it divides them. Options: `:split_cost`, the weight of one
split against one seg of imbalance, default `8`; `:candidates`, how many cutting lines are
tried at each step, default `48`.

# `locate`

```elixir
@spec locate(Cauldron2D.Sectors.Map.t(), Cauldron2D.Sectors.Map.point()) ::
  non_neg_integer()
```

The subsector `point` is in.

# `root`

```elixir
@spec root(Cauldron2D.Sectors.Map.t()) :: child()
```

The root of the map's BSP.

# `walk`

```elixir
@spec walk(
  Cauldron2D.Sectors.Map.t(),
  Cauldron2D.Sectors.Map.point(),
  acc,
  (non_neg_integer(), acc -> acc),
  (box(), acc -> boolean())
) :: acc
when acc: term()
```

Visit the subsectors front to back as seen from `point`.

`leaf` is called `leaf.(subsector_index, acc)` and returns the new `acc`. Before going
into the far side of a node, `far?.(box, acc)` is asked whether anything in that box can
still be seen; returning `false` skips it.

---

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