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
import GoogleMapsUtils
class QuadTreeItem : NSObject, GQTPointQuadTreeItem {
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.
tree.add(QuadTreeItem(point: GQTPoint(x: -1, y: -1)))
tree.add(QuadTreeItem(point: GQTPoint(x: -1, y: -1)))
tree.add(QuadTreeItem(point: GQTPoint(x: -1, y: 1)))
tree.add(QuadTreeItem(point: GQTPoint(x: 1, y: 1)))
tree.add(QuadTreeItem(point: GQTPoint(x: 1, y: -1)))
// 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
@import GoogleMapsUtils;
@interface QuadTreeItem : NSObject<GQTPointQuadTreeItem>
- (instancetype)initWithPoint:(GQTPoint)point;
@end
@implementation QuadTreeItem {
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};
GQTPointQuadTree *tree = [[GQTPointQuadTree alloc] initWithBounds:bounds];
// Add 4 points to the tree.
[tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){-1, -1}]];
[tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){-1, 1}]];
[tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){1, 1}]];
[tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){1, -1}]];
// 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