چهار درخت

این صفحه ابزار چهار درختی را توصیف می‌کند که در کتابخانه ابزار برای Maps SDK برای iOS موجود است.

چهار درخت یک ساختار داده ای است که برای یافتن نقاط نزدیک به یک نقطه، با جستجو در یک منطقه اطراف نقطه مورد نظر مفید است.

با استفاده از چهاردرخت، می‌توانید نقاطی را در محدوده دوبعدی جستجو کنید، جایی که آن نقاط به عنوان مختصات lat/lng یا مختصات دکارتی (x، y) تعریف می‌شوند. Quadtree سطل هایی از مختصات را در گره ها ذخیره می کند و آنها را بر اساس منطقه (جعبه مرزی) فهرست می کند. برای یافتن یک جفت مختصات معین، از گره های درخت چهارگانه عبور می کنید.

پیش نیازها و نکات

ابزار quadtree بخشی از Maps SDK برای کتابخانه ابزار iOS است. اگر هنوز کتابخانه را راه‌اندازی نکرده‌اید، قبل از خواندن بقیه این صفحه ، راهنمای راه‌اندازی را دنبال کنید.

اضافه کردن یک چهار درخت و جستجو برای نقاط در یک منطقه مشخص

کد زیر یک چهار درخت ایجاد می کند، سپس تمام نقاط یک منطقه مشخص را جستجو می کند:

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))");
    }
  }
}
      

@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