This page describes the quadtree utility that's available in the utility library for the Maps SDK for iOS.

A quadtree is a data structure that's useful for finding points near a single point, by searching inside an area surrounding the point of interest.

Using a quadtree, you can search efficiently for points within a 2D range, where those points are defined as lat/lng coordinates or as cartesian (x, y) coordinates. The quadtree stores buckets of coordinates in nodes, and indexes them by region (bounding box). To find a given coordinate pair, you traverse through the nodes of the quadtree.

## Prerequisites and notes

The quadtree utility is part of the Maps SDK for iOS Utility Library. If you haven't yet set up the library, follow the setup guide before reading the rest of this page.

## Adding a quadtree and search for points in a given area

The following code creates a quadtree, then searches for all points within a given area:

### Swift

private let gqtPoint : GQTPoint

init(point : GQTPoint) {
self.gqtPoint = point
}

func point() -> GQTPoint {
return gqtPoint
}

/// Function demonstrating how to create and use a quadtree
private func test() {

// Create a quadtree with bounds of [-2, -2] to [2, 2].
let bounds = GQTBounds(minX: -2, minY: -2, maxX: 2, maxY: 2)
guard let tree = GQTPointQuadTree(bounds: bounds) else {
return
}

// Add 4 points to the tree.

// Search for items within the rectangle with lower corner of (-1.5, -1.5)
// and upper corner of (1.5, 1.5).
let searchBounds = GQTBounds(minX: -1.5, minY: -1.5, maxX: 1.5, maxY: 1.5)
for item in tree.search(with: searchBounds) as! [QuadTreeItem] {
print("(\(item.point().x), \(item.point().y))");
}
}
}

### Objective-C

- (instancetype)initWithPoint:(GQTPoint)point;
@end

GQTPoint _point;
}

- (instancetype)initWithPoint:(GQTPoint)point {
if ((self = [super init])) {
_point = point;
}
return self;
}

- (GQTPoint)point {
return _point;
}

/// Function demonstrating how to create and use a quadtree
- (void)test {
// Create a quadtree with bounds of [-2, -2] to [2, 2].
GQTBounds bounds = {-2, -2, 2, 2};

// Add 4 points to the tree.

// Search for items within the rectangle with lower corner of (-1.5, -1.5)
// and upper corner of (1.5, 1.5).
NSArray *foundItems = [tree searchWithBounds:(GQTBounds){-1.5, -1.5, 1.5, 1.5}];

for (QuadTreeItem *item in foundItems) {
NSLog(@"(%lf, %lf)", item.point.x, item.point.y);
}
}

@end

[]
[]