이 페이지에서는 iOS용 Maps SDK의 유틸리티 라이브러리에서 사용할 수 있는 쿼드트리 유틸리티에 대해 설명합니다.
쿼드트리는 관심 장소 주변 영역 내부를 검색하여 단일 지점 근처의 지점을 찾는 데 유용한 데이터 구조입니다.
쿼드트리를 사용하면 2D 범위 내의 점을 효율적으로 검색할 수 있습니다. 이러한 점은 위도/경도 좌표 또는 데카르트 좌표 (x, y) 좌표로 정의됩니다. 쿼드트리는 노드에 좌표 버킷을 저장하고 지역 (경계 상자)별로 색인을 생성합니다. 지정된 좌표 쌍을 찾으려면 쿼드트리의 노드를 통과해야 합니다.
사전 요구사항 및 참고 사항
쿼드트리 유틸리티는 iOS용 Maps SDK 유틸리티 라이브러리의 일부입니다. 아직 라이브러리를 설정하지 않았다면 이 페이지의 나머지 부분을 읽기 전에 설정 가이드를 따르세요.
쿼드트리 추가 및 특정 영역에서 지점 검색
다음 코드는 쿼드트리를 생성한 다음 지정된 영역 내의 모든 지점을 검색합니다.
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