Un quadtree est une structure de données utile pour trouver des points à proximité d'un seul
en effectuant une recherche dans une zone autour du point d'intérêt.
Avec un quadtree, vous pouvez rechercher efficacement des points dans une plage 2D,
où ces points sont définis en tant que coordonnées de latitude/longitude ou en tant que cartésiens (x, y)
coordonnées. Le quadtree stocke des buckets de coordonnées dans des nœuds et des index
par région (cadre de délimitation). Pour trouver une paire de coordonnées donnée, vous traversez
à travers les nœuds du quadtree.
Ajouter un quadtree et rechercher des points dans une zone donnée
Le code suivant crée un quadtree, puis recherche tous les points dans
pour une zone donnée:
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
Sauf indication contraire, le contenu de cette page est régi par une licence Creative Commons Attribution 4.0, et les échantillons de code sont régis par une licence Apache 2.0. Pour en savoir plus, consultez les Règles du site Google Developers. Java est une marque déposée d'Oracle et/ou de ses sociétés affiliées.
Dernière mise à jour le 2025/07/26 (UTC).
[[["Facile à comprendre","easyToUnderstand","thumb-up"],["J'ai pu résoudre mon problème","solvedMyProblem","thumb-up"],["Autre","otherUp","thumb-up"]],[["Il n'y a pas l'information dont j'ai besoin","missingTheInformationINeed","thumb-down"],["Trop compliqué/Trop d'étapes","tooComplicatedTooManySteps","thumb-down"],["Obsolète","outOfDate","thumb-down"],["Problème de traduction","translationIssue","thumb-down"],["Mauvais exemple/Erreur de code","samplesCodeIssue","thumb-down"],["Autre","otherDown","thumb-down"]],["Dernière mise à jour le 2025/07/26 (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```"]]