Cây tứ giác

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

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

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

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

Tiện ích quadtree là một phần của SDK Bản đồ dành cho iOS Thư viện tiện ích. Nếu bạn chưa thiết lập thư viện, 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 tứ giác và tìm kiếm các điểm trong một khu vực nhất định

Đoạn mã sau đây sẽ tạo một cây tứ giác, 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