ควอดทรี

หน้านี้อธิบายยูทิลิตี quadtree ที่มีอยู่ในไลบรารียูทิลิตีสําหรับ Maps SDK สําหรับ iOS

หนึ่งในสี่ส่วนคือโครงสร้างข้อมูลที่เป็นประโยชน์ในการค้นหาจุดใกล้จุดๆ เดียว โดยการค้นหาภายในบริเวณรอบๆ จุดสนใจ

เมื่อใช้สี่เหลี่ยมจตุรัส คุณจะสามารถค้นหาจุดต่างๆ ภายในช่วง 2 มิติได้อย่างมีประสิทธิภาพ โดยจุดเหล่านั้นหมายถึงพิกัดละติจูด/ลองจิจูด หรือพิกัดคาร์ทีเชียน (x, y) Quadtree จะจัดเก็บที่เก็บข้อมูลพิกัดไว้ในโหนด และจัดทําดัชนีตามภูมิภาค (กรอบล้อมรอบ) หากต้องการค้นหาคู่พิกัดคนหนึ่ง คุณต้องข้ามผ่านโหนดของ Quadtree

เกณฑ์เบื้องต้นและหมายเหตุ

ยูทิลิตี quadtree เป็นส่วนหนึ่งของ Maps SDK สําหรับไลบรารียูทิลิตีของ iOS หากยังไม่ได้ตั้งค่าไลบรารี ให้ทําตามคู่มือการตั้งค่าก่อนอ่านส่วนที่เหลือของหน้านี้

การเพิ่ม Quadtree และค้นหาจุดในพื้นที่ที่ระบุ

โค้ดต่อไปนี้จะสร้างสี่เหลี่ยมจัตุรัส แล้วค้นหาจุดทั้งหมดภายในพื้นที่ที่กําหนด

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