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.
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
importGoogleMapsUtilsclassQuadTreeItem:NSObject,GQTPointQuadTreeItem{privateletgqtPoint:GQTPointinit(point:GQTPoint){self.gqtPoint=point}funcpoint()->GQTPoint{returngqtPoint}/// Function demonstrating how to create and use a quadtreeprivatefunctest(){// Create a quadtree with bounds of [-2, -2] to [2, 2].letbounds=GQTBounds(minX:-2,minY:-2,maxX:2,maxY:2)guardlettree=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).letsearchBounds=GQTBounds(minX:-1.5,minY:-1.5,maxX:1.5,maxY:1.5)foritemintree.search(with:searchBounds)as![QuadTreeItem]{print("(\(item.point().x),\(item.point().y))");}}}
Objective-C
@importGoogleMapsUtils;@interfaceQuadTreeItem:NSObject<GQTPointQuadTreeItem>-(instancetype)initWithPoint:(GQTPoint)point;@end@implementationQuadTreeItem{GQTPoint_point;}-(instancetype)initWithPoint:(GQTPoint)point{if((self=[superinit])){_point=point;}returnself;}-(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].GQTBoundsbounds={-2,-2,2,2};GQTPointQuadTree*tree=[[GQTPointQuadTreealloc]initWithBounds:bounds];// Add 4 points to the tree.[treeadd:[[QuadTreeItemalloc]initWithPoint:(GQTPoint){-1,-1}]];[treeadd:[[QuadTreeItemalloc]initWithPoint:(GQTPoint){-1,1}]];[treeadd:[[QuadTreeItemalloc]initWithPoint:(GQTPoint){1,1}]];[treeadd:[[QuadTreeItemalloc]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=[treesearchWithBounds:(GQTBounds){-1.5,-1.5,1.5,1.5}];for(QuadTreeItem*iteminfoundItems){NSLog(@"(%lf, %lf)",item.point.x,item.point.y);}}@end
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2025-09-04 UTC."],[[["\u003cp\u003eThis page explains the quadtree utility within the Maps SDK for iOS Utility Library, a data structure for efficiently finding nearby points.\u003c/p\u003e\n"],["\u003cp\u003eQuadtrees enable searching for points within a 2D range using latitude/longitude or cartesian coordinates by indexing them by region.\u003c/p\u003e\n"],["\u003cp\u003eTo use the quadtree, you must first set up the Maps SDK for iOS Utility Library as a prerequisite.\u003c/p\u003e\n"],["\u003cp\u003eCode examples are provided to demonstrate creating a quadtree, adding points, and searching for points within a specified area in both Swift and Objective-C.\u003c/p\u003e\n"]]],[],null,["This page describes the quadtree utility that's available in the\n[utility library\nfor the Maps SDK for iOS](https://github.com/googlemaps/google-maps-ios-utils).\n\nA quadtree is a data structure that's useful for finding points near a single\npoint, by searching inside an area surrounding the point of interest.\n\nUsing a quadtree, you can search efficiently for points within a 2D range,\nwhere those points are defined as lat/lng coordinates or as cartesian (x, y)\ncoordinates. The quadtree stores buckets of coordinates in nodes, and indexes\nthem by region (bounding box). To find a given coordinate pair, you traverse\nthrough the nodes of the quadtree.\n\nPrerequisites and notes\n\nThe quadtree utility is part of the\n[Maps SDK for iOS\nUtility Library](https://github.com/googlemaps/google-maps-ios-utils). If you haven't yet set up the library,\nfollow the [setup guide](/maps/documentation/ios-sdk/utility/setup)\nbefore reading the rest of this page.\n\nAdding a quadtree and search for points in a given area\n\nThe following code creates a quadtree, then searches for all points within\na given area: \n\nSwift \n\n```swift\nimport GoogleMapsUtils\n\nclass QuadTreeItem : NSObject, GQTPointQuadTreeItem {\n private let gqtPoint : GQTPoint\n\n init(point : GQTPoint) {\n self.gqtPoint = point\n }\n\n func point() -\u003e GQTPoint {\n return gqtPoint\n }\n\n /// Function demonstrating how to create and use a quadtree\n private func test() {\n\n // Create a quadtree with bounds of [-2, -2] to [2, 2].\n let bounds = GQTBounds(minX: -2, minY: -2, maxX: 2, maxY: 2)\n guard let tree = GQTPointQuadTree(bounds: bounds) else {\n return\n }\n\n // Add 4 points to the tree.\n tree.add(QuadTreeItem(point: GQTPoint(x: -1, y: -1)))\n tree.add(QuadTreeItem(point: GQTPoint(x: -1, y: -1)))\n tree.add(QuadTreeItem(point: GQTPoint(x: -1, y: 1)))\n tree.add(QuadTreeItem(point: GQTPoint(x: 1, y: 1)))\n tree.add(QuadTreeItem(point: GQTPoint(x: 1, y: -1)))\n\n // Search for items within the rectangle with lower corner of (-1.5, -1.5)\n // and upper corner of (1.5, 1.5).\n let searchBounds = GQTBounds(minX: -1.5, minY: -1.5, maxX: 1.5, maxY: 1.5)\n for item in tree.search(with: searchBounds) as! [QuadTreeItem] {\n print(\"(\\(item.point().x), \\(item.point().y))\");\n }\n }\n}\n \n```\n\nObjective-C \n\n```objective-c\n@import GoogleMapsUtils;\n\n@interface QuadTreeItem : NSObject\u003cGQTPointQuadTreeItem\u003e\n- (instancetype)initWithPoint:(GQTPoint)point;\n@end\n\n@implementation QuadTreeItem {\n GQTPoint _point;\n}\n\n- (instancetype)initWithPoint:(GQTPoint)point {\n if ((self = [super init])) {\n _point = point;\n }\n return self;\n}\n\n- (GQTPoint)point {\n return _point;\n}\n\n/// Function demonstrating how to create and use a quadtree\n- (void)test {\n // Create a quadtree with bounds of [-2, -2] to [2, 2].\n GQTBounds bounds = {-2, -2, 2, 2};\n GQTPointQuadTree *tree = [[GQTPointQuadTree alloc] initWithBounds:bounds];\n\n // Add 4 points to the tree.\n [tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){-1, -1}]];\n [tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){-1, 1}]];\n [tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){1, 1}]];\n [tree add:[[QuadTreeItem alloc] initWithPoint:(GQTPoint){1, -1}]];\n\n // Search for items within the rectangle with lower corner of (-1.5, -1.5)\n // and upper corner of (1.5, 1.5).\n NSArray *foundItems = [tree searchWithBounds:(GQTBounds){-1.5, -1.5, 1.5, 1.5}];\n\n for (QuadTreeItem *item in foundItems) {\n NSLog(@\"(%lf, %lf)\", item.point.x, item.point.y);\n }\n}\n\n@end\n \n```"]]
