Dörtlü Ağacı

Koleksiyonlar ile düzeninizi koruyun İçeriği tercihlerinize göre kaydedin ve kategorilere ayırın.

Bu sayfada, iOS için Haritalar SDK'sının yardımcı program kitaplığında sunulan dörtlü sistem yardımcı programı açıklanmaktadır.

Dörtlü ağaç, tek bir noktanın yakınında bulunan ve o noktanın etrafındaki bir alanı arayarak nokta bulmaya yarayan bir veri yapısıdır.

Dörtlük ağacı kullanarak, 2D aralık içindeki noktaları verimli bir şekilde arayabilirsiniz. Buradaki noktalar, enlem/boylam koordinatları veya kartezyen (x, y) koordinatları olarak tanımlanır. Quadtree, koordinat gruplarını 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ük ağacının düğümlerinden geçersiniz.

Ön koşullar ve notlar

quadtree yardımcı programı, iOS Yardımcı Program Kitaplığı SDK'sının bir parçasıdır. Kitaplığı henüz kurmadıysanız bu sayfanın geri kalanını okumadan önce kurulum kılavuzunu uygulayın.

Dörtte birlik dilim ekleme ve belirli bir noktadaki noktaları arama

Aşağıdaki kod dörtlü oluşturur, 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