# `Monty.Frameworks.Utils.KdTree`
[🔗](https://github.com/d-led/ex.tbp.monty/blob/v0.1.0/packages/ex_tbp_monty_core/lib/monty/frameworks/utils/kd_tree.ex#L1)

A k-nearest-neighbour index over points.

Monty asks scipy for this — `KDTree(graph.pos)` — and then queries it once per
hypothesis to find the stored nodes an unobserved pose would have been seen
from. Comparing against every node instead is the same answer at a cost that
grows with the product of hypotheses and nodes: a pretrained object of two
thousand nodes matched by two thousand hypotheses is four million distance
calculations per graph per step, and that is where most of the port's time
went.

So this is the same structure scipy builds: a binary tree that splits the
points along whichever axis they are most spread over, at their median, so a
query descends to the region its answer is in and stops looking at regions
that cannot beat what it already has. It is our own code rather than a port —
scipy's tree is not part of Monty — and is documented as such.

## Determinism

Answers are ordered nearest first, and a tie in distance goes to the lower id,
which is what makes two runs of the same episode choose the same nodes. Points
are taken as `{point, id}` pairs so the caller decides what an id is.

# `id`

```elixir
@type id() :: non_neg_integer()
```

# `point`

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

# `t`

```elixir
@type t() :: {:nif, reference()} | tree()
```

# `tree`

```elixir
@type tree() ::
  :empty | {number(), number(), number(), id(), 0 | 1 | 2, tree(), tree()}
```

# `build`

```elixir
@spec build([{point(), id()}]) :: t()
```

Indexes `points`, each a `{point, id}` pair.

The native index when this machine has one, the tree below otherwise. Both
answer the same question; `build_elixir/1` is the one that says which.

# `build_elixir`

```elixir
@spec build_elixir([{point(), id()}]) :: tree()
```

The reference index: our own tree, in Elixir.

This is what the tests describe — including how many nodes a query looks at —
and what runs wherever the native index is not built. A caller asking for it
by name wants that answer, not the fastest one.

# `nearest`

```elixir
@spec nearest(t(), point(), pos_integer()) :: [id()]
```

The ids of the `count` points nearest `query`, nearest first.

Fewer than `count` when the tree holds fewer points.

# `nearest_many`

```elixir
@spec nearest_many(t(), [point()], pos_integer()) :: [[id()]]
```

The ids of the `count` points nearest each of `queries`, one list per query.

One call for a step's worth of questions, in the order they were asked, and
each answer is exactly what `nearest/3` would have said: a caller never has to
interleave the index with its own loop. On the native index this is genuinely
one call — twenty thousand queries cross the boundary once, not twenty
thousand times.

# `nearest_many_ids`

```elixir
@spec nearest_many_ids(t(), [point()] | binary(), pos_integer()) ::
  {binary(), pos_integer()} | nil
```

The same answers as `nearest_many/3`, left as the bytes the index wrote.

Nothing is decoded, rejected or grouped: the answer is `{ids, count}` —
`queries * count` little-endian u32 ids, row after row, with
`4_294_967_295` where a query found fewer than `count` — because the caller is
a native kernel that reads them there. Decoding twenty thousand ids into lists
of lists was a fifth of what the answers cost, and the kernel can skip the
marker itself.

`nil` for a tree that is not the native index: the Elixir tree has no such
bytes, and a caller that needs them keeps the decoded path.

# `nearest_with_distances`

```elixir
@spec nearest_with_distances(t(), point(), pos_integer()) :: [{float(), id()}]
```

The `count` points nearest `query` with their distances, nearest first.

scipy answers this from the same call as the ids — `return_distance=True` —
and the distance is what a caller needs when it wants to compare answers
rather than use them: two objects differ most where one has a part the other
lacks, which shows up as a node far from everything in the other graph.

# `nearest_with_visits`

```elixir
@spec nearest_with_visits(t(), point(), pos_integer()) :: {[id()], non_neg_integer()}
```

The same answer as `nearest/3`, and how many nodes finding it took.

The count is the point of a tree: a query is supposed to descend to the
region its answer is in and stop, so the number of nodes it looks at belongs
to the logarithm of the tree rather than to the number of points. A test can
hold it to that, which is the only way to notice if pruning stops pruning —
the answers stay right while the cost goes linear.

# `points_bytes`

```elixir
@spec points_bytes([point()]) :: binary()
```

Points as the bytes an index or a kernel reads: three little-endian f64 each.

Public so that a caller which asks two native things about the same points
encodes them once, and so that both see exactly the same numbers.

---

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