iphone - How can I reduce the number of annotations on a map?

Question

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

Answer 1

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).