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.18 or newer. Run moonc -v to check the compiler rather than the moon CLI version.
Verified on 2026-11-11 with moonc 0.10.20 (65efd5b93, 2026-11-05) and moon / moonrun 0.1.20261104 (940aa18). The 0.10.18 minimum is also tested. Full moon version --all output and command results are retained in the compatibility record.
Use 0.2.4 with the current SDK: it fixes JS queries that fail in 0.2.3 after the compiler's array layout change. The core supports Wasm, Wasm GC, JavaScript and Native; the browser bridge targets JavaScript only. Windows Native requires Visual Studio C++ tools and the Windows SDK; see setup.
git clone https://github.com/LING71671/MoonSTRtree.git
cd MoonSTRtree
moon check
moon run cmd/main --target jsThese commands verify the source checkout and run the CLI using the same package. To add 0.2.4 to an existing MoonBit project:
moon add LING71671/moon_strtree@0.2.4Consumers use the following alias in their moon.pkg:
import {
"LING71671/moon_strtree" @spatial,
}
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.
| 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.
moon check
moon test
moon test --target js
moon test --target wasm-gc
moon info
moon fmtThe browser experiment 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 for toolchain setup and the validation record for executed checks.
Layered directory map
src/
api/ Public adapters and types
core/
geometry/ Bounds and exact predicates
packing/ STR ordering and page arithmetic
index/ Storage, traversal and analysis
stats/ Diagnostics and integrity checks
extensions/
trajectory/ Time windows and sequence operations
geofence/ Stateful fence events
polygon/ Polygon operations and indexing
support/generator/ Deterministic test data
bridge/browser/ JS host boundary for the demo
tests/api/ Root API compatibility and regressions
playground/src/ React interface, worker and adapters
docs/en/ and docs/zh/ Separate language editions
Root API names remain available. Geometry types are re-exported from src/core/geometry and opaque index adapters live in src/api; direct imports of former internal package paths must migrate. The roadmap separates implemented work from future measurements.
| Document | Purpose |
|---|---|
| Architecture | Package dependencies and source ownership |
| API | Query and storage semantics |
| Development | Commands and toolchain setup |
| Validation | Executed tests and retained measurements |
| Specification | Behavioral invariants |
| Changelog | Versioned changes and migration notes |
Apache-2.0. See LICENSE.
STR packing follows Leutenegger, Lopez and Edgington's STR: A Simple and Efficient Algorithm for R-Tree Packing (1997). Engineering references include JTS STRtree and Flatbush. These established algorithms are not claimed as original inventions. The separate comparison module uses MIT-licensed totto2727/geo; it is excluded from the published core package. Existing source copyright headers and the showcase's dependency and font notices are retained.
CI checks, builds and tests Wasm, Wasm GC, JavaScript and Native, runs the CLI example on each backend, and tests/builds the browser. It installs the official current toolchain on pushes, pull requests and each Monday at 09:00 Beijing time. Runtime dependency and font notices are distributed with the showcase. Version 0.2.0 adds a lean MoonBit distribution archive; the browser and benchmark artifacts stay in the repository. See distribution commands.
The bilingual showcase runs real 2D/3D/4D queries and displays the full 10,944-case standard benchmark with raw samples. Query, construction, coverage and slower cases remain visible; the current results do not establish overall superiority to Flatbush. Validation records the measured source snapshot and deployment checks.
