Dörtlü Ağacı

Bu sayfada, iOS için Haritalar SDK'sının yardımcı program kitaplığında bulunan quadtree yardımcı programı açıklanmaktadır.

Dört ağaç, önemli yerin etrafındaki bir alanın içinde arama yaparak tek bir noktanın yakınındaki noktaları bulmak için yararlı olan bir veri yapısıdır.

Dört ağaç kullanarak, 2D bir aralıktaki noktaları etkili bir şekilde arayabilirsiniz. Bu noktalar, enlem/boylam koordinatları veya kartezyen (x, y) koordinatları olarak tanımlanır. Dört ağaç, koordinat paketlerini düğümlerde depolar ve bunları bölgeye (sınırlayıcı kutu) göre dizine ekler. Belirli bir koordinat çiftini bulmak için dörtlü ağacın düğümlerini katlayarak geçersiniz.

Ön koşullar ve notlar

quadtree yardımcı programı, iOS için Haritalar SDK'sı Yardımcı Program Kitaplığı'nın bir parçasıdır. Kitaplığı henüz oluşturmadıysanız bu sayfanın geri kalanını okumadan önce kurulum kılavuzundaki talimatları uygulayın.

Dört ağaç ekleme ve belirli bir bölgedeki noktaları arama

Aşağıdaki kod bir dörtlü ağaç oluşturur ve ardından belirli bir alandaki tüm noktaları arar:

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