Skip to content

About

MoonBit spatial indexing library with 2D/3D/4D STR trees, geometry and trajectory tools, and reproducible benchmarks.

Topics

Resources

Stars

1 star

Watchers

1 watching

Forks

Repository files navigation

MoonSTRtree

MoonSTRtree spatial index

Apache-2.0 license

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.

Quick start

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 0.2.4 to an existing MoonBit project:

moon add LING71671/moon_strtree@0.2.4

Consumers 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.

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

moon check
moon test
moon test --target js
moon test --target wasm-gc
moon info
moon fmt

The 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.

Source ownership

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.

For developers and agents

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.

CI and licenses

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.

About

MoonBit spatial indexing library with 2D/3D/4D STR trees, geometry and trajectory tools, and reproducible benchmarks.

Topics

Resources

Stars

1 star

Watchers

1 watching

Forks

Releases

Packages

Contributors

Languages