AI-generated Key Takeaways
-
This page explains the quadtree utility within the Maps SDK for iOS Utility Library, a data structure for efficiently finding nearby points.
-
Quadtrees enable searching for points within a 2D range using latitude/longitude or cartesian coordinates by indexing them by region.
-
To use the quadtree, you must first set up the Maps SDK for iOS Utility Library as a prerequisite.
-
Code examples are provided to demonstrate creating a quadtree, adding points, and searching for points within a specified area in both Swift and Objective-C.
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
