sphereql-index 0.3.0

Spatial indexing and queries for sphereQL
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

# sphereql-index

Spatial indexing for the [sphereQL](https://github.com/bkahan/sphereQL) project.

Partitions S² into a two-tier index — radial shells × angular sectors
— so spatial queries scan only the buckets that overlap the query
region instead of the whole point set.

## What's here

- **`SectorIndex<T>`** — angular sector grid (`theta_divisions ×
  phi_divisions`) for fast in-region lookups (`Cone`, `Cap`, `Band`,
  `Wedge`, …) defined in `sphereql-core`.
- **`ShellIndex<T>`** — radial shell partitioning for r-range
  filtering. Composes with `SectorIndex` via `SpatialIndex`.
- **`SpatialIndex<T>`** — composite of shell + sector. Built through
  `SpatialIndexBuilder` (chained config: shell boundaries, theta /
  phi divisions, then `.build()`).
- **`CachedIndex<T>`** — wraps `SpatialIndex` with an LRU cache
  (IndexMap-backed, O(1) touch and evict) over recent query keys,
  invalidated by a generation counter on mutation. `CachedIndexBuilder`
  exposes `.cache_capacity(n)`.
- **k-NN** — uses precomputed unit Cartesian vectors and `1 − dot`
  as a cosine proxy instead of full Vincenty per pair, so the inner
  loop is 3 muls + 2 adds per item.

The `SpatialItem` trait is the integration point: implement it on your
record type to plug into any of the indexes above.

## Example

```rust
use sphereql_core::SphericalPoint;
use sphereql_index::{SpatialIndex, SpatialItem};

#[derive(Debug, Clone)]
struct Star { id: u64, pos: SphericalPoint }

impl SpatialItem for Star {
    type Id = u64;
    fn id(&self) -> &u64 { &self.id }
    fn position(&self) -> &SphericalPoint { &self.pos }
}

let mut idx = SpatialIndex::<Star>::builder()
    .uniform_shells(3, 10.0)
    .theta_divisions(8)
    .phi_divisions(4)
    .build();

idx.insert(Star { id: 1, pos: SphericalPoint::new_unchecked(1.0, 0.5, 0.8) });
idx.insert(Star { id: 2, pos: SphericalPoint::new_unchecked(1.0, 3.0, 2.0) });

let hits = idx.nearest(&SphericalPoint::new_unchecked(1.0, 0.6, 0.9), 1);
assert_eq!(*hits[0].item.id(), 1);
```

## Versioning

Part of the sphereQL workspace, currently `0.3.0`; API may change
before 1.0. `IndexError` is `#[non_exhaustive]`. Builder types are
`#[must_use]` — forgetting `.build()` warns at the use site.

## Documentation

See the workspace
[architecture.md](https://github.com/bkahan/sphereQL/blob/main/docs/architecture.md)
and
[performance.md](https://github.com/bkahan/sphereQL/blob/main/docs/performance.md).