本頁面說明 Maps SDK for iOS 公用程式庫提供的 Qudtree 公用程式。
四元樹是一種資料結構,可在搜尋點周圍的區域內搜尋,協助您尋找單一點附近的點。
使用二元樹可讓您有效搜尋 2D 範圍中的點,這些點都會定義為經緯度座標或購物車 (x, y) 座標。四角樹會將座標值區儲存在節點中,並按區域建立索引 (定界框)。如要尋找特定的座標組合,您可以周遊四棵樹的節點。
必要條件和注意事項
quadtree 公用程式包含在 Maps SDK for iOS 公用程式庫。如果您尚未設定程式庫,請先按照設定指南的步驟完成設定,再閱讀本頁面的其他內容。
加入方形樹並搜尋指定區域中的點
下列程式碼會建立四元樹,然後搜尋指定區域中的所有點:
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