Quadtree

این صفحه ابزار کمکی quadtree را که در کتابخانه ابزار کمکی برای کیت توسعه نرم‌افزار Maps ویژه iOS دردسترس است شرح می‌دهد.

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

بااستفاده از درخت چهارگانه، می‌توانید به‌طور مؤثر نقاط را در محدوده دوبعدی جستجو کنید، که در آن نقاط به‌عنوان مختصات عرض/طول جغرافیایی یا مختصات دکارتی (x, y) تعریف شده‌اند. درخت چهارگانه دسته‌های مختصات را در گره‌ها ذخیره می‌کند و آن‌ها را براساس منطقه (جعبه مرزی) نمایه می‌کند. برای پیدا کردن جفت مختصات داده‌شده، از گره‌های درخت چهارگانه عبور می‌کنید.

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

ابزار کمکی quadtree بخشی از کتابخانه ابزار کمکی کیت توسعه نرم‌افزار Maps برای 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))");
    }
  }
}
      

آبجکتیو-سی

@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