Regarding iPhone Map Kit cluster pinpoints:
I have 1000's of marks that I want to show on the map but it's just too many to handle so I want to cluster them.
Are there frameworks available or proof of concepts? That this is possible or is already been done?
I think Foto Brisko (iTunes link) does this.
I do not think there is a Cocoa Touch framework for it.
This might be a bit like using a chainsaw to mow the lawn, but here is an excerpt from Algorithms in a Nutshell
Creating a KD-Tree...
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;
}
}
Finding nearest neighbors best: O(log n) worst 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;
}
More on KD-Trees at Wikipedia