This is Part 6 in a multi-part series about using the location functions in FileMaker Go.
1. Where Am I?
2. What’s Accuracy?
3. Where’s My Stuff?
4. How Far?
5. Which Way?
6. What’s Close?
Now that we can use the location functions in FileMaker Go to get our current geographic coordinates and figure our location relative to particular geocoded points of interest, it’s natural to want to perform a find for any locations in a database close to your current position. “I just finished a job in the field; what other jobs are nearby that I could do next?”
Find within radius
So how do we do that? If you just get your current position with the Location function and perform a find for the matching latitude and longitude, you’ll only be able to find records for other locations within about an 11 cm radius — too cozy for my taste. We want to be able to find records within a given, much larger, radius. You might try using the haversine formula from part 4 to check how far every record in a table is from your current position, and omit all the records that are farther than your search radius. I’ll call this the record scan strategy, and it is molasses slow.
The fast finds we’re accustomed to in FileMaker are fast when they work on fields that are indexed. This means that all the data values in an indexed field are stored separately so that when we perform a find for records with particular values in that field, FileMaker doesn’t have to do a record scan checking the records one-by-one for matches; FileMaker instead finds those values in the index, which tells us much more quickly exactly which records match the values and where to find those records. It’s the difference between finding a book in a library by checking books from a giant disorganized pile one at a time vs. looking it up in the card catalog and finding it on the shelf. (Do libraries still have card catalogs?)
The reason the record scan strategy is slow is that it’s checking records one at a time, rather than quickly finding a whole set at once using a find on indexed fields. So how are you supposed to perform a find for all the records in a circle? Well, you’re not. We can index latitude fields, we can index longitude fields, and we can perform fast finds on either one. But when we try to specify find criteria for both fields falling in a circular region, we run into the problem that the longitude range will be different for every latitude value, and vice versa. Tough luck. This is a fine time to invoke one of my favorite problem-solving strategies: pick an easier problem to solve instead.
If you’re willing to bend the parameters of the problem, there’s a much faster solution. Since latitude and longitude fields can each be indexed, we can perform a find for one range on each field to match a square region around our current location instead of a circular region. (The region will actually only be approximately square due to the geometry on the surface of a sphere.) Since practical distances by transit and neighborhood boundaries rarely correspond to exact circular regions anyway, this is usually just as good. And since it’s typically an order of magnitude faster, I’d say it’s worth it.
To perform a location-based find within a square region, we need north & south latitude boundaries and east & west longitude boundaries for the region. We can do this by working the haversine formula backwards, then encapsulating that calculation in a script or custom function so we never have to think about it again. Once we have those bounds, we can perform a find for records where the latitude is between our calculated south and north bounds, and where the longitude is between our calculated west and east bounds.
Find closest records
As often as not, we just want to find the closest handful of records, with no particular idea how close they are in advance. To do that, we repeat the find in a loop, increasing the size of the search region until we get a big enough found set or we just get tired of looking.
Find record for current location
If you want to only find the one record that corresponds to your current location — to check-in to a job site, for example — you can do the same process, only in reverse order, decreasing the size of your find region until you only find 1 record. Keen readers will notice that the script using the double false position method to look for the first radius that only finds 1 record.
Circular find rehash
I have yet to work on a project where the square location find wasn’t perfectly adequate. Still, the problem of the circular find nags me. Can I write a circular “find” that is less slow? Nevermind that I don’t need it for any practical purposes. I just want to know how well I can do. It’s good exercise.
The lesson we learned before was that record scans are slow, and finds on indexed fields are fast. But record scanning is necessary to distinguish records inside an exact circular region. We can make the slower speed of the record scan less of a problem by minimizing the number of records that need to be subjected to it. (This is consistent with the developer wisdom that the only way software ever gets faster is by asking the computer to do less in one way or another.) We do this by using faster find methods to omit any records that are obviously not inside the circular region before doing the record scan.
Constrained record scan
The faster find method I described finds records within a square that already circumscribes a circle with the same radius — anything outside that square is already outside the circle. Once the found set is reduced to the square region, the record scan has less work to do to reduce that found set to a circular region. Since the square find and circular constrain have already been written, combining the two is a piece of cake.
Riemann find
In the constrained scan above, the circumscribed square serves as a fast approximation to the circle, then we whittle down the found set from there. If we have a closer approximation to the circle, we may start with an even smaller found set before the record scan. We can do this by piecing together several smaller rectangular regions, similar to how a Riemann sum works. This script is more involved to write because it has to create several find criteria for rectangular regions instead of a single find for a square region. We can’t just call the square find as a subscript this time. It’s more script than I care to inflict on casual readers, but I think the visual does a better job explaining the idea, and you can see the script in the demo file for this post if you’re interested.
The flip side of omitting records that are obviously not inside the circle is that we can also omit any records that obviously are inside the circle before doing the record scan, then extend the found set to include them again after the record scan is done. By omitting rectangular areas approximating the inside of the circular region, the record scan only has to be done over an area approximating the edge of the circle. In the figure below, this means we only have to do a record scan for any locations between the blue and green rectangles.
That looks great in theory. In practice, the Riemann finds appear to be very sensitive to the number of rectangles we try to slice the circle into. The square constrain and the Riemann find both take the edge off finding locations inside an exact circular area, but my testing hasn’t shown it to be the order-of-magnitude difference I’d really like to see. I never had particularly high expectations for the square constrain, but I was surprised the Riemann find didn’t do better. The simple find for a single square area is nice and zippy, but as the find gets increasingly complicated as I add more and more rectangular sub-regions, FileMaker starts having trouble keeping pace.
If you want to use any of these techniques in your own applications, you’re welcome to copy from the demo file for this post. Location.fmp12
