You're all set!

To start developing, please head over to our developer documentation.

Activate the Google Maps SDK for iOS

To get you started we'll guide you through the Google Developers Console to do a few things first:

  1. Create or choose a project
  2. Activate the Google Maps SDK for iOS
  3. Create appropriate keys
Continue

Quadtree

This page describes the quadtree utility that's available in the utility library for the Google 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 Google 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.

Add 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

// Assume that <Google-Maps-iOS-Utils/GQTPointQuadTree.h> is in the bridging-header file.

class QuadTreeItem : NSObject, GQTPointQuadTreeItem {
  let gqtPoint : GQTPoint

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

  func point() -> GQTPoint {
    return gqtPoint
  }
}

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

// 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)))

// 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.searchWithBounds(searchBounds) as! [QuadTreeItem] {
  NSLog("(\(item.point().x), \(item.point().y))");
}

Objective-C

#import <Google-Maps-iOS-Utils/GQTPointQuadTree.h>

@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;
}

@end

int main(int argc, char* argv[]) {
  // 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);
  }
  return 0;
}

Send feedback about...

Google Maps SDK for iOS
Google Maps SDK for iOS
Need help? Visit our support page.