I'm coding a map view with around 900 annotations. Having this many annotations on a map make the performance suffer, so I'd like to reduce it to about 300 at a time. The annotations are representing shops in a country, so they tend to cluster a lot around major cities, then in small groups of 2 or 3 in smaller towns. I want to reduce the numbers so that the groups of 2 or 3 are left alone, but the numbers in the city are thinned (they're so close together that they offer no useful information).
In the image you can see that there are a couple of big groups (Tokyo, Nagoya and Osaka) which I want to thin out. But with the pins on their own or in small groups, I want to make sure they don't get filtered. Once I zoom in, I want to show the missing pins.
Does anyone know of some good code that I can use, so that points which are close together are eliminated, but ones more spread out are left alone?
alt text http://img.skitch.com/20100204-jpde6wugc94nn692k7m36gmqf1.jpg
One approach is that before placing a new pin, check if there's another pin already placed within distance d of the new pin. If there is, don't place the new pin. You need to vary d based on the current zoom level.
You can reduce the number of pins you check against by considering only pins in a bounding box centered on the new pin. The box could be d x d degrees on a side (with d varying based on zoom level).
If a commercial, third party library is an option, check out Superpin (license costs $199). It is an iOS Framework that internally uses quadtrees for annotation storage and performs grid-based clustering. The algorithm is quite fast, the included sample app is showing airports of the world (more than 30k+ annotations) and it's running quite smooth on an 3G iPhone.
You may also want to check http://revolver.be/blog/mapkit-clustering-with-ios/, another ready-made solution, which is free for non-commerical projects.
Disclaimer: I'm one of the Superpin developers
Two options I can think of:
- If you have points of interest to work with (Eg, cities), you can simply group all pins by the POI they're closest to, in lower zoom levels.
- You can use K-means clustering to group pins into clusters and represent them with a midpoint pin.
Here's a code snippet that takes an MKAnnotation's coordinates, convert it to a CGPoint relative to the MKMapView, and logs what's the underlying view at that CGPoint.
CGPoint pinPoint = [mapView convertCoordinate:pinView.annotation.coordinate toPointToView:mapView];
NSLog(@"pointing to %@", [[mapView hitTest:pinPoint withEvent:nil] description]);
Put that inside a loop that iterates through all your pins. If the underlying view is another MKAnnotation instance, then hide that pin.
if([[mapView hitTest:pinPoint withEvent:nil] isKindOfClass:[FFMapPinView class]])
pinView.hidden = YES;
For this to work properly, you need the pinsArray to be ordered so that index 0 is the frontmost pin.
Considering that many pins in densely-populated areas will be on the same street, you could consider making "super pins" that list the pins on a particular street, instead of on each individual address.
-S!
Late to the party, I know, but you may find this routine useful. It comes from this file, which is part of a FOSS project.
/**************************************************************//**
\brief This function looks for meetings in close proximity to each
other, and collects them into "red markers."
\returns an NSArray of BMLT_Results_MapPointAnnotation objects.
*****************************************************************/
- (NSArray *)mapMeetingAnnotations:(NSArray *)inResults ///< This is an NSArray of BMLT_Meeting objects. Each one represents a meeting.
{
#ifdef DEBUG
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations - Checking %d Meetings.", [inResults count]);
#endif
NSMutableArray *ret = nil;
NSInteger displayIndex = 1;
if ( [inResults count] )
{
NSMutableArray *points = [[NSMutableArray alloc] init];
for ( BMLT_Meeting *meeting in inResults )
{
#ifdef DEBUG
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations - Checking Meeting \"%@\".", [meeting getBMLTName]);
#endif
CLLocationCoordinate2D meetingLocation = [meeting getMeetingLocationCoords].coordinate;
CGPoint meetingPoint = [(MKMapView *)[self view] convertCoordinate:meetingLocation toPointToView:nil];
CGRect hitTestRect = CGRectMake(meetingPoint.x - BMLT_Meeting_Distance_Threshold_In_Pixels,
meetingPoint.y - BMLT_Meeting_Distance_Threshold_In_Pixels,
BMLT_Meeting_Distance_Threshold_In_Pixels * 2,
BMLT_Meeting_Distance_Threshold_In_Pixels * 2);
BMLT_Results_MapPointAnnotation *annotation = nil;
#ifdef DEBUG
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations - Meeting \"%@\" Has the Following Hit Test Rect: (%f, %f), (%f, %f).", [meeting getBMLTName], hitTestRect.origin.x, hitTestRect.origin.y, hitTestRect.size.width, hitTestRect.size.height);
#endif
for ( BMLT_Results_MapPointAnnotation *annotationTemp in points )
{
CGPoint annotationPoint = [(MKMapView *)[self view] convertCoordinate:annotationTemp.coordinate toPointToView:nil];
#ifdef DEBUG
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations - Comparing the Following Annotation Point: (%f, %f).", annotationPoint.x, annotationPoint.y);
#endif
if ( !([[annotationTemp getMyMeetings] containsObject:meeting]) && CGRectContainsPoint(hitTestRect, annotationPoint) )
{
#ifdef DEBUG
for ( BMLT_Meeting *t_meeting in [annotationTemp getMyMeetings] )
{
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations - Meeting \"%@\" Is Close to \"%@\".", [meeting getBMLTName], [t_meeting getBMLTName]);
}
#endif
annotation = annotationTemp;
}
}
if ( !annotation )
{
#ifdef DEBUG
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations -This meeting gets its own annotation.");
#endif
NSArray *meetingsAr = [[NSArray alloc] initWithObjects:meeting, nil];
annotation = [[BMLT_Results_MapPointAnnotation alloc] initWithCoordinate:[meeting getMeetingLocationCoords].coordinate andMeetings:meetingsAr andIndex:0];
[annotation setDisplayIndex:displayIndex++];
[points addObject:annotation];
}
else
{
#ifdef DEBUG
NSLog(@"BMLTMapResultsViewController mapMeetingAnnotations -This meeting gets lumped in with others.");
#endif
[annotation addMeeting:meeting];
}
if ( annotation )
{
if ( !ret )
{
ret = [[NSMutableArray alloc] init];
}
if ( ![ret containsObject:annotation] )
{
[ret addObject:annotation];
}
}
}
}
// This is the black marker.
BMLT_Results_MapPointAnnotation *annotation = [[BMLT_Results_MapPointAnnotation alloc] initWithCoordinate:[[BMLTAppDelegate getBMLTAppDelegate] searchMapMarkerLoc] andMeetings:nil andIndex:0];
if ( annotation )
{
[annotation setTitle:NSLocalizedString(@"BLACK-MARKER-TITLE", nil)];
[ret addObject:annotation];
}
return ret;
}
You can see it in action in the released version of the app.
Meetings in close proximity are gathered into red annotations, which open a list.
