MoonBit static spatial indexes: 2D bounds, 3D volumes and 4D spacetime, with geometry and trajectory extensions.
English | 中文 | Live showcase | Quick start | API | Architecture
Requires **moonc 0.10.14 or newer**. Run `moonc -v` to check the compiler rather than the `moon` CLI version. ## Quick start ```powershell git clone https://github.com/LING71671/MoonSTRtree.git cd MoonSTRtree moon check moon run cmd/main --target js ``` These commands verify the source checkout and run the CLI using the same package. To add version 0.2.1 to an existing MoonBit project: ```powershell moon add LING71671/moon_strtree@0.2.1 ``` Consumers use the following alias in their `moon.pkg`: ```text import { "LING71671/moon_strtree" @spatial, } ``` ```moonbit let items = [ (@spatial.Rect::new(0.0, 0.0, 10.0, 10.0), 101), (@spatial.Rect::new(20.0, 20.0, 30.0, 30.0), 102), ] let tree = @spatial.StrTree::build(items, node_capacity=16) let hits = tree.query(@spatial.Rect::new(5.0, 5.0, 15.0, 15.0)) ``` The query includes ID 101. Touching boundaries count as intersections. IDs must be non-negative and coordinates finite. The index is immutable after construction; rebuild when data changes. Result order and the identity chosen among tied nearest neighbors are unspecified. ## Capabilities and limits | Domain | Implemented | | --- | --- | | Indexes | 2D, 3D and 4D STR packing, range and point queries | | 2D / 3D queries | Counts, first hit, filters, nearest neighbors, radius, segments, spatial joins | | Geometry | Bounding-box predicates, mesh ray queries, polygon calculations and clipping | | Analysis | Center-based DBSCAN, grid density, geofence events | | Trajectories | Time-window candidates, simplification, streaming compression, DTW and discrete Frechet distance | | Storage | Independently copied arrays; optional checked restore for 2D and 3D | `query_into` reuses caller-owned result and traversal arrays. Count queries avoid result arrays but allocate traversal scratch. Storage import/export copies arrays; this is neither a zero-copy protocol nor the FlatBuffers binary format. Heavy overlap can require visiting every object, so logarithmic query cost is not guaranteed. ## Explore and verify ```powershell moon check moon test moon test --target js moon test --target wasm-gc moon info moon fmt ``` The [browser experiment](playground/) runs compiled MoonBit queries beside real Flatbush and RBush implementations. Draw a query, reveal actual packed node bounds, measure identical seeded inputs, and export raw timing evidence. The comparison ledger measures the JS target and 2D queries; a separate 3D/4D experiment exposes height and time queries with complete result export. It does not establish a universal speed ranking. Start it with `cd playground` and `pnpm dev` after `pnpm install`. `moon run cmd/main` prints diagnostic examples, not benchmark timings. See the [development guide](docs/en/DEVELOPMENT.md) for toolchain setup and the [validation record](docs/en/VALIDATION.md) for executed checks. ## Source ownership