Cây tứ giác

Trang này mô tả tiện ích quadtree có sẵn trong thư viện tiện ích dành cho SDK bản đồ dành cho iOS.

Quadtree là một cấu trúc dữ liệu hữu ích trong việc tìm các điểm ở gần một điểm duy nhất, bằng cách tìm kiếm bên trong khu vực xung quanh địa điểm yêu thích.

Khi sử dụng quadtree, bạn có thể tìm kiếm hiệu quả các điểm trong phạm vi 2D, trong đó các điểm đó được xác định là toạ độ vĩ độ/lng hoặc toạ độ Descartes (x, y). Quadtree lưu trữ các nhóm toạ độ trong các nút và lập chỉ mục các nhóm toạ độ đó theo khu vực (hộp giới hạn). Để tìm một cặp toạ độ nhất định, bạn di chuyển qua các nút của tứ giác.

Điều kiện tiên quyết và lưu ý

Tiện ích 4 cây này nằm trong SDK Maps dành cho Thư viện tiện ích iOS. Nếu bạn chưa thiết lập thư viện, hãy làm theo hướng dẫn thiết lập trước khi đọc phần còn lại của trang này.

Thêm một cây quadtree và tìm các điểm trong một khu vực nhất định

Mã sau đây tạo ra một cây quadtree, sau đó tìm kiếm tất cả các điểm trong một khu vực nhất định:

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