רביעייה

דף זה מתאר את כלי העזר לריבוע (quadtree) שזמין ב- ספריית תשתיות ל-SDK של מפות Google ל-iOS.

מרובע הוא מבנה נתונים שיכול לעזור לכם למצוא נקודות ליד על ידי חיפוש בתוך האזור שמסביב לנקודת העניין.

בעזרת מרובע, אפשר לחפש ביעילות נקודות בטווח דו-ממדי. שבהן הנקודות האלה מוגדרות כקואורדינטות של קו רוחב/lng או כקרטזית (x, y) של הקואורדינטות. ה-quadtree מאחסן קטגוריות של קואורדינטות בצמתים ובאינדקסים לפי אזור (תיבה תוחמת). כדי למצוא צמד קואורדינטות נתון, צריך לחצות דרך הצמתים של הריבוע.

דרישות מוקדמות והערות

כלי השימוש ב-Qudtree הוא חלק SDK של מפות ל-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))");
    }
  }
}
      

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