Der iPhone Map Kit-Cluster zeigt genau an



google-maps annotations (6)

Dies könnte ein bisschen wie mit einer Kettensäge, um den Rasen zu mähen, aber hier ist ein Auszug aus Algorithmen in Kürze

KD-Baum erstellen ...

public class KDFactory {
  // Known comparators for partitioning points along dimensional axes.
  private static Comparator<IMultiPoint> comparators[ ] ;
  // Recursively construct KDTree using median method on input points.
  public static KDTree generate (IMultiPoint [ ] points) {
    if (points. length == 0) { return null; }
    // median will be the root.
    int maxD = points[ 0] . dimensionality( );
    KDTree tree = new KDTree(maxD) ;
    // Make dimensional comparators that compare points by ith dimension
    comparators = new Comparator[ maxD+1] ;
    for (int i = 1; i <= maxD; i++) {
      comparators[ i] = new DimensionalComparator(i) ;
    }
    tree. setRoot(generate (1, maxD, points, 0, points. length-1) ) ;
    return tree;
  }

  // generate the node for the d-th dimension (1 <= d <= maxD)
  // for points[ left, right]
  private static DimensionalNode generate (int d, int maxD,
                                           IMultiPoint points[ ] ,
                                           int left, int right) {
    // Handle the easy cases first
    if (right < left) { return null; }
    if (right == left) { return new DimensionalNode (d, points[ left] ) ; }
    // Order the array[ left, right] so the mth element will be the median
    // and the elements prior to it will all be <=, though they won' t
    // necessarily be sorted; similarly, the elements after will all be >=
    int m = 1+(right-left) /2;
    Selection. select(points, m, left, right, comparators[ d] ) ;
    // Median point on this dimension becomes the parent
    DimensionalNode dm = new DimensionalNode (d, points[ left+m-1] ) ;
    // update to the next dimension, or reset back to 1
    if (++d > maxD) { d = 1; }
    // recursively compute left and right sub-trees, which translate
    // into ' below' and ' above' for n-dimensions.
    dm. setBelow(maxD, generate (d, maxD, points, left, left+m-2) ) ;
    dm. setAbove(maxD, generate (d, maxD, points, left+m, right) ) ;
    return dm;
  }
}

Nächsten Nachbarn am besten finden: O (log n) schlechtestes O (n)

// method in KDTree
public IMultiPoint nearest (IMultiPoint target) {
  if (root == null) return null;
  // find parent node to which target would have been inserted. This is our
  // best shot at locating closest point; compute best distance guess so far
  DimensionalNode parent = parent(target) ;
  IMultiPoint result = parent. point;
  double smallest = target. distance(result) ;
  // now start back at the root, and check all rectangles that potentially
  // overlap this smallest distance. If better one is found, return it.
  double best[ ] = new double[ ] { smallest };
  double raw[ ] = target. raw( );
  IMultiPoint betterOne = root. nearest (raw, best) ;
  if (betterOne ! = null) { return betterOne; }
  return result;
}

// method in DimensionalNode. min[ 0] contains best computed shortest distance.
IMultiPoint nearest (double[ ] rawTarget, double min[ ] ) {
    // Update minimum if we are closer.
    IMultiPoint result = null;
    // If shorter, update minimum
    double d = shorter(rawTarget, min[ 0] ) ;
    if (d >= 0 && d < min[ 0] ) {
      min[ 0] = d;
      result = point;
    }
    // determine if we must dive into the subtrees by computing direct
    // perpendicular distance to the axis along which node separates
    // the plane. If d is smaller than the current smallest distance,
    // we could "bleed" over the plane so we must check both.
    double dp = Math. abs(coord - rawTarget[ dimension-1] ) ;
    IMultiPoint newResult = null;
    if (dp < min[ 0] ) {
      // must dive into both. Return closest one.
      if (above ! = null) {
        newResult = above. nearest (rawTarget, min) ;
        if (newResult ! = null) { result = newResult; }
      }
      if (below ! = null) {
        newResult = below. nearest(rawTarget, min) ;
        if (newResult ! = null) {  result = newResult; }
      }
    } else {
      // only need to go in one! Determine which one now.
      if (rawTarget[ dimension-1] < coord) {
        if (below ! = null) {
          newResult = below. nearest (rawTarget, min) ;
        }
      } else {
        if (above ! = null) {
          newResult = above. nearest (rawTarget, min) ;
        }
      }
      // Use smaller result, if found.
      if (newResult ! = null) { return newResult; }
    }
    return result;
  }

Mehr zu KD-Trees bei Wikipedia

In Bezug auf das iPhone Map Kit Cluster:

Ich habe 1000 von Markierungen, die ich auf der Karte anzeigen möchte, aber es sind einfach zu viele, um sie zu verarbeiten, daher möchte ich sie gruppieren.

Gibt es Rahmen oder Konzepte? Dass das möglich ist oder schon gemacht wurde?



Ich habe versucht, die anderen hier vorgeschlagen, und ich fand auch OCMapView die am besten OCMapView hat.

Es ist kostenlos und ermöglicht eine einfache Gruppierung von Annotationen, was ich brauchte. Es ist ein wenig neuer und aktueller als Revolver und für mich ist es einfacher zu implementieren.


Ich musste kürzlich Annotation Clustering mit MapKit implementieren. Die oben genannten Lösungen sind gut, abhängig von Ihrem Anwendungsfall. Ich ging mit FBAnnotationClustering (Objective-C), weil es kostenlos war, und hatte viele Sterne und einige Probleme auf GitHub:

https://github.com/infinum/FBAnnotationClustering

Die App, an der ich arbeitete, war sehr kartenzentriert, daher machte es Sinn, FBAnnotationClustering in Swift zu übersetzen. Hier ist ein Blogbeitrag zum Ansatz, der einen Link zum Beispielprojekt auf github enthält.

http://ribl.co/blog/2015/05/28/map-clustering-with-swift-how-we-implemented-it-into-the-ribl-ios-app/



Hinweis: Dies ist ein kommerzielles Produkt, mit dem ich verbunden bin, aber es löst genau dieses Problem.

Ich habe dieses Problem in einigen meiner Apps gelöst und beschlossen, es in ein wiederverwendbares Framework zu extrahieren. Es heißt Superpin und ist ein (kommerzielles, Lizenzkosten $ 149) iOS-Framework, das intern Quadtrees für Annotationsspeicher verwendet und Grid-basiertes Clustering durchführt. Der Algorithmus ist ziemlich schnell, die mitgelieferte Beispiel-App zeigt Flughäfen der Welt (mehr als 30k + Anmerkungen) und läuft auf einem 3G-iPhone ziemlich flüssig.





markerclusterer