Spatial provides Scala with space partitioning data structures, currently: Point Region Octree PROctree, PRQuadTree, PROctreeMap[T], and PRQuadTreeMap[T]. This library cross compiles to all Scala compilation targets: JVM, Native, and Scala.js.

Design Goals:

1. Cross compile to JVM, Native, and JavaScript platforms
2. Maximize performance
3. Minimize memory footprint
4. Provide convenient syntax
5. Seamlessly interoperate with other libraries
6. Seamlessly interoperate with native languages like JavaScript, C/C++, and Java

To meet these design goals, Spatial relies on SLASH for its vector formats. TLDR: regardless of platform, it uses the lightest, fastest, and most portable vector format in the entire Scala ecosystem.

To circumvent collections overhead, Spatial relies on NArr and its highly optimized NArrayBuilder[T]. This simultaneously minimizes memory footprint and maximizes speed.

Spatial data structures optimize population and querying. Concerns like thread safety and standard Scala collections semantics go partially supported or, in cases like element removal, completely ignored. We make it efficient and easy to build QuadTrees and Octrees and then perform nearest neighbor, k-nearest neighbor, and radial searches on them. Instead of removing nodes, though, we recommend building a new data structure from scratch with the removed nodes omitted. Likewise, instead of iterating over a spatial data structure as one does with normal Scala collections. If you need to map, filter, foreach, etc, we recommend storing references to the same points in a traditional Scala collection.

We aspire to add support for k-d trees in the near future, and variants of Octree and QuadTree that support volumes/areas, not just points.

Pull requests welcome!

To use this library with SBT:

libraryDependencies +="ai.dragonfly"%%%"spatial"%"<LATEST_VERSION>"

How to use PRQuadTree:

// constructionvalqt=newPRQuadTree(
100.0, // The extent/length/width of this QuadTreeVec[2](0.0, 0.0) // the centroid
)
// insertion:valb:Boolean= qt.insert(Vec[2](25.0, 25.0))
// nearest neighbor search:valnn:Vec[2] = qt.nearestNeighbor(Vec[2](24.0, 23.0))
// k nearest neighbor search:valknn:NArray[Vec[2]] = qt.knn(Vec[2](24.0, 23.0))
// radial query:valradialResults:NArray[Vec[2]] = qt.radialQuery(Vec[2](0.0, 0.0), 42.0)
// test if a point lies within the boundary of the QuadTree:valisInside:Boolean= qt.encompasses(Vec[2](42.0, 42.0))
// cardinality:vals:Int= qt.size
// bounds:valbnds:slash.vector.VecBounds[2] = qt.bounds

How to use PRQuadTreeMap[T]:

// constructionvalqtm=newPRQuadTreeMap[String](
100.0, // The extent/length/width of this QuadTreeVec[2](0.0, 0.0) // the centroid
)
// insertion:valb:Boolean= qtm.insert(Vec[2](25.0, 25.0), "QuadTreeMap Love!")
// nearest neighbor search:valnn: (Vec[2], String) = qtm.nearestNeighbor(Vec[2](24.0, 23.0))
// k nearest neighbor search:valknn:NArray[(Vec[2], String)] = qtm.knn(Vec[2](24.0, 23.0))
// radial query:valradialResults:NArray[(Vec[2], String)] = qtm.radialQuery(Vec[2](0.0, 0.0), 42.0)
// test if a point lies within the boundary of the QuadTree:valisInside:Boolean= qtm.encompasses(Vec[2](42.0, 42.0))
// cardinality:vals:Int= qtm.size
// bounds:valbnds:slash.vector.VecBounds[2] = qtm.bounds

How to use PROctree:

// constructionvalot=newPROctree(
100.0, // The extent/length/width of this QuadTreeVec[3](0.0, 0.0, 0.0) // the centroid
)
// insertion:valb:Boolean= ot.insert(Vec[3](25.0, 25.0, 25.0))
// nearest neighbor search:valnn:Vec[3] = ot.nearestNeighbor(Vec[3](24.0, 23.0, 26.0))
// k nearest neighbor search:valknn:NArray[Vec[3]] = ot.knn(Vec[3](24.0, 23.0, 26.0))
// radial query:valradialResults:NArray[Vec[3]] = ot.radialQuery(Vec[3](0.0, 0.0, 0.0), 42.0)
// test if a point lies within the boundary of the Point Region Octree:valisInside:Boolean= ot.encompasses(Vec[3](42.0, 42.0, 42.0))
// cardinality:vals:Int= ot.size
// bounds:valbnds:slash.vector.VecBounds[3] = ot.bounds

How to use PROctreeMap[T]:

// constructionvalotm=newPROctreeMap[String](
100.0, // The extent/length/width of this QuadTreeVec[3](0.0, 0.0, 0.0) // the centroid
)
// insertion:valb:Boolean= otm.insert(Vec[3](25.0, 25.0, 25.0), "PROctreeMap Love!")
// nearest neighbor search:valnn: (Vec[3], String) = otm.nearestNeighbor(Vec[3](24.0, 23.0, 26.0))
// k nearest neighbor search:valknn:NArray[(Vec[3], String)] = otm.knn(Vec[3](24.0, 23.0, 26.0))
// radial query:valradialResults:NArray[(Vec[3], String)] = otm.radialQuery(Vec[3](0.0, 0.0, 0.0), 42.0)
// test if a point lies within the boundary of the Point Region Octree Map:valisInside:Boolean= otm.encompasses(Vec[3](42.0, 42.0))
// cardinality:vals:Int= otm.size
// bounds:valbnds:slash.vector.VecBounds[3] = otm.bounds

Projects that rely on Spatial:

https://github.com/dragonfly-ai/bitfrost

https://github.com/dragonfly-ai/beacon