كوادتري

توضّح هذه الصفحة أداة quadtree التي تتوفّر في مكتبة الأدوات المساعدة لحزمة تطوير البرامج (SDK) لتطبيق "خرائط Google" لنظام التشغيل iOS.

الشجرة الرباعية هي بنية بيانات مفيدة للعثور على نقاط بالقرب من نقطة واحدة، من خلال البحث داخل منطقة محيطة بنقطة الاهتمام.

باستخدام شكل رباعي الأبعاد، يمكنك البحث بفعالية عن نقاط ضمن نطاق ثنائي الأبعاد، حيث يتم تحديد هذه النقاط كإحداثيات خطوط الطول/العرض أو كإحداثيات الديكارتية (س، وص). يخزِّن النظام الرباعي مجموعات من الإحداثيات في عُقد، ويفهرسها حسب المنطقة (مربّع الإحاطة). للعثور على زوج إحداثي معيّن، تتقاطع من خلال عقد الشكل الرباعي.

المتطلّبات الأساسية والملاحظات

تعتبر أداة quadtree جزءًا من حزمة تطوير البرامج (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