Latest 0.1.0
Homepage https://github.com/blackmirror-media/BMQuadtree
License MIT
Platforms ios 10.0
Authors

CI Status
Version
License
Platform

Swift implementation of a Quadtree. A drop-in replacement for GameplayKit’s
GKQuadtree for it is not working properly.

A quadtree manages its structure to optimize for spatial searches—unlike a basic
data structure such as an array or dictionary, a quadtree can find all elements
occupying a specific position or region very quickly. The quadtree partitioning
strategy divides space into four quadrants at each level, as illustrated in
Figure 1. When a quadrant contains more than one object, the tree subdivides
that region into four smaller quadrants, adding a level to the tree.

Figure 1

The tree can hold any objects (AnyObject).
The implementation follows the GKQuadtree.

The implementation is using Axis-Aligned Bounding Boxed (AABB) just like the GameplayKit implementation.

TODO

  • [ ] Unify/clean-up after removing object from tree

Creating A Tree

A tree is initialised with a bounding quad (axis-aligned bounding rectangle),
a minimum cell size and a maximum depth.

let tree = BMQuadtree(
boundingQuad: boundingQuad,
minimumCellSize: 3)

By default, the minimum cell size is 1, but it does make sense to use a larger
cell size, for instance 3.

Adding And Removing Elements

let location = CLLocation(
latitude: item.latitude, 
longitude: item.longitude)
tree.add(location, at: float2(item.latitude, item.longitude))
tree.remove(location)

Searching For Elements

Nearest neigbour to a defined point.

let nearest = tree.element(nearestTo: float2(0, 0))

You filter for different types (classes) when performing a nearest element
search.

let nearestOfType: CLLocation? =
tree.element(
nearestTo: float2(0, 0), 
type: CLLocation.self) as? CLLocation

All of the elements in the quadtree node this point would be placed in.

let elementAtPoint = tree.elements(at: float2(0, 0))

All of the elements that resides in quadtree nodes which
intersect the given quad. Recursively check if the earch quad contains
the points in the quad.

let searchQuad = GKQuad(
quadMin: float2(-10, -10), 
quadMax: float2(10, 10))

let elementInQuad = tree.elements(in: searchQuad)

Extensions for MapKit

To be able to use the quadtree for managing map data (locations, coordinates,
instructions, POIs, etc.), there are a few extensions available
for your convenience.

GKQuad With CLLocation And Offset

To define a quad using coordinated and offset in meters.

let vienna = CLLocation(latitude: 48.21128, longitude: 16.364537)
let quad = GKQuad(location: vienna, offset: 5000)

GKQuad For Overlays

Let us say you have a track you show on the map as anMKOverlay.
You can access the bounding quad using:

let quad = trackOverlay.boundingQuad

CLLocationCoordinate2D And CLLocation To vector_float2

As float2-s are used to store the location of the objects, we added
convenience properties to work with CLLocation and CLLocationCoordinate2D

let vienna = CLLocation(latitude: 48.21128, longitude: 16.364537)
let vector = vienna.vector
let vienna = CLLocationCoordinate2DMake(
latitude: 48.21128, 
longitude: 16.364537)
let vector = vienna.vector

Debugging

Finally, to be able to visualise and debug the quadtree on the map, you
can use the convenience debugOverlay property of the tree and simply add it
as a new overlay.

let quadtreeDebugOverlay: MKOverlay = tree?.debugOverlay
map.add(quadtreeDebugOverlay)

Further Dicussions

The minCellSize parameter controls the memory usage and performance of the
tree. A lower value causes the tree to make more spatial divisions when adding
elements; a higher value causes the tree to create fewer such divisions,
but store more elements in each node. Which direction leads to better
performance depends on the number and spatial arrangement of the elements you
add to the tree—for best results, profile with different values to find one
best suited to your app or game.

The maximum depth is added for performance reasons and to aviod stack
overflow crashed when adding the same or very close elements in large numbers.
The default value is 10. This limits the maximum amount of elements to be
stored in the tree:

numberOfNodes ^ maximumDepth * minCellSize
4 ^ 10 * 3 = 3.145.728
let largeTree = BMQuadtree(
boundingQuad: largeOverlay.boundingQuad,
minimumCellSize: 10,
maximumDepth: 100)

Latest podspec

{
    "name": "BMQuadtree",
    "version": "0.1.0",
    "summary": "Swift implementation of a quadtree.",
    "swift_version": "4.2",
    "description": "Swift implementation of a quadtree. A drop-in replacement for GameplayKit's GKQuadtree for it is not working properly.",
    "homepage": "https://github.com/blackmirror-media/BMQuadtree",
    "license": {
        "type": "MIT",
        "file": "LICENSE"
    },
    "authors": {
        "Adam Eri": "[email protected]"
    },
    "source": {
        "git": "https://github.com/blackmirror-media/BMQuadtree.git",
        "tag": "0.1.0"
    },
    "platforms": {
        "ios": "10.0"
    },
    "source_files": "BMQuadtree/Classes/**/*"
}

Pin It on Pinterest

Share This