search NSDictionary for latitude longitude with a certain distance

Question

I have an NSDictionary of about 2000 locations with lat and long and I am dropping pins on map based on if they are in the visible map region.

Currently every time the pan the map I simply loop through my dictionary and calculate the distance to see if the location is visible, if so drop a pin.

CLLocationCoordinate2D centre = [self.map centerCoordinate];
CLLocation *mapCenter =[[CLLocation alloc] initWithLatitude: centre.latitude  longitude: centre.longitude];

        for (int i=0; i < [self.dealersSource count]; i++) {

            CLLocation *d = [[CLLocation alloc] initWithLatitude: [[[self.dealersSource objectAtIndex:i] valueForKey:@"lat"] floatValue]
                                                           longitude: [[[self.dealersSource objectAtIndex:i] valueForKey:@"long"] floatValue]];

                CLLocationDistance distance = [d distanceFromLocation:mapCenter];
                float dist =(distance/1609.344);

            if (dist <= radius && dist !=0) {
               // this will be visible on the map, add to list of annotations
            }
}

This works but seems pretty inefficient and can be slow on older iPads - especially if more and more locations get added to this list. I would like to be able to use some sort of NSPredicate to filter my initial list before I start looping though them.

I assume you have and NSArray of 2000 dictionaries where each dict has @"lat" and @"lon" key - values. You can use NSPredicate for filtering NSArray for given predicate. I.e. like this: NSArray *filteredarray = [array filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"(lat >= %d)", 16.0989]]; Also take a look at this link where NSPredicate filtering is explained in details: http://stackoverflow.com/questions/110332/filtering-nsarray-into-a-new-nsarray-in-objective-c — Josip B., Jan 19 '14 at 14:07
I guess my confusion is I would need to do a >= and a <= both right based on the visible are of the map? For both lat and long — Slee, Jan 19 '14 at 14:20
Exactly like that. Predicate is just like if statement condition, so you need to write condition that will satisfy your needs in the end. Addind (a>=some_value && a<=some_value) should solve the problem. — Josip B., Jan 19 '14 at 14:23
Instead of creating CLLocations and calling distanceFromLocation for each pin, it might be faster to create an MKMapPoint from each pin's coordinate and calling MKMapRectContainsPoint and passing the map's visibleMapRect. You'll still be iterating through the pins but the MKMapPointForCoordinate and MKMapRectContainsPoint functions should be faster than the Objective-C methods. You'll be testing against a rectangle instead of a radius (circle) but you may be ok with this difference. — , Jan 19 '14 at 16:28
It's only 2000 points. Have you tried adding them all onto the map and letting iOS decide if they are in region or not? — Craig, Jan 19 '14 at 21:30

score 0 · Answer 1 · answered Jan 19 '14 at 14:19

There is not really any standard Objective-C structure that is well-suited to finding values within a range -- you pretty much have to search one-by-one (though you can use "predicates" to "hide" the search inside filteredArray... operations, etc, and so write fewer lines of code).

The best structure for efficiently finding values between bounds on a line is probably an array sorted on the values which is searched with a binary search algorithm. You'd do one binary search for the lower bound an another for the upper bound. This is log(n) complexity, so fairly efficient for large lists (if you don't have to sort the lists very often).

Precisely how one would do this for a 2-d surface is harder to figure. Perhaps first use the above technique to find "candidates" in the X direction, then check their Y coordinate. Would not be log(n), though.

search NSDictionary for latitude longitude with a certain distance

1 Answers1