SQLite query with location fields inside of region

Question

I have a database with two columns, latitude and longitude. I wonder if it's possible in the Transact-SQL command to retrieve only the records in a defined region of the location passed as a parameter;

For example let's say you have the following records, which is all from the same location, but we're using them for testing purposes.

Now I have the SQL query:

[self.fmQueue inDatabase:^(FMDatabase *db)
    {
    CLLocationCoordinate2D center = CLLocationCoordinate2DMake(latitude, longitude);
    CLCircularRegion *region = [[CLCircularRegion alloc] initWithCenter:center radius:400.0f identifier:@"identifier"];

    NSString* queryCommand = [NSString stringWithFormat:@"SELECT * FROM %@ WHERE ?EXPRESSION_ABOUT_REGION?", readingsTable];
    FMResultSet* result = [db executeQuery:queryCommand];
    if (completionblock)
        {
        completionblock([self readingsArrayFromResultSet:result]);
        }
    }];

I could just retrieve records and then compare for every each one with a constructed CLLocationCoordinate2D, [region containsCoordinate:CLLocationCoordinate2D], but that feels so bad performant.

I'm looking for the most performant and appropriate solution to retrieve the desired region related location records in the T-SQL query.

Answer 1

Issues with the Previous Approximation

The previous answer here models the Earth as a Cartesian plane, with latitude and longitude as x and y, and then draws either a circle or a rectangle around the points---the actual shape does not matter, both methods have the same properties.

This can be fine if your constraints are really loose, and they may be here in your particular instance. For the sake of making this answer more useful to everybody I've answered the problem assuming your constraints are not quite as loose. For mobile geolocation apps in general this approximation causes problems. Maybe you've seen an app that's got it wrong. The resulting distances don't make any sense. There are several flaws with the previous approach:

1. Bad approximation: The scale of the Earth is big so simple approximations can be off by a scale of miles. This is bad if the user is in a car and really bad if the user is on foot. Simple tricks with degrees are not an improvement over circles or squares: latitude and longitude are not evenly distributed, and you need a full approximation like Haversine to get accurate data.
2. Excludes good points: Unless you severely expand the shape, your sample will exclude valid points.
3. Includes bad points: And the more you expand the shape to capture excluded valid points, the more you capture invalid points.
4. Broken sort order: Without the real calculation, you won't be able to correctly sort the output by distance. This means any ordered list you produce will be way off. Usually you want the points in order of closeness.
5. Two calculations: If you go back and fix it, you're doing two computations.

Single-point Haversine in C/Objective-C

The selection code is already in the other answer. This is the recomputation you referenced that you'll have to perform for each point after in Objective-C or C:

/////////////////////////////////////
//Fill these in or turn them into function arguments
float lat1=center_point.latitude;
float lon1=center_point.longitude;

float lat2=argument_point.latitude;
float lon2=argument_point.longitude;
/////////////////////////////////////

//Conversion factor, degrees to radians
float PI=3.14159265358979;
float f=PI/180;
lat1*=f; lon1*=f; lat2*=f; lon2*=f;

//Haversine Formula (from R.W. Sinnott, "Virtues of the Haversine", Sky and Telescope, vol. 68, no. 2, 1984, p. 159):
float dlon = lon2 - lon1;
float dlat = lat2 - lat1;
float a = pow((sin(dlat/2)),2) + cos(lat1) * cos(lat2) * pow((sin(dlon/2)),2);
float c = 2 * asin(MIN(1,sqrt(a)));
float R = 6378.137;//km Radius of Earth
float d = R * c;

d *= 0.621371192; //optional: km to miles [statute] conversion factor

//NSString conversion?
//if (d >= .23) return [NSString stringWithFormat:@"%0.1f m",d]; //.23m ~ 400 yds
//d *= 5280; //miles to feet conversion factor
//d /= 3; //feet to yards
//int y=(int)d;
//return [NSString stringWithFormat:@"%d yds",y];

return d;

That should be all the tools you need to complete your task as discussed.

Haversine in SQLite

I would like to show you a direct SQLite-only solution, but I was never able to get Haversine to run satisfactorily directly inside of SQLite. You don't get a square root in SQLite. You don't get a pow() function, though you can repeat an argument times itself. You don't get sin, cos, or sinh. There are extensions that add some of these features. I don't know how well-supported they are compared to the base SQLite. Even with them it's going to be too slow.

People seem to recommend updating the columns with pre-computed sines. That's fine as long as you don't need to take the sine of a difference over a whole column, in which case you're writing a new column to the table every time you need to make a new calculation, which is terrible. At any rate, I'd like to show you a comparison of how slow SQLite is on computing the Haversine, but I can't get it to compute it at all. (I think my memory of SQLite being slow on this is actually a memory of MySQL on the server being slow.)

All-points Solution in Kerf

The preceding discussion I hope is a close-to-exhaustive look at what you can do with the standard tools.

The good news is if you do it right this calculation is fast on the phone. I built a thing for you that I think solves your problem in a better way. If you are willing to use another tool, in Kerf this problem is easy. I went back and committed to the repo vectorized operations for trigonometric functions so that the calculations would be fast. My iPhone 5 will do 10,000 points in 20 milliseconds, and 100,000 points in 150 milliseconds. You can do a million points in 1.5 seconds, but at that point you'd need a throbber. Disclosure as per the rules: I built it.

From the Kerf REPL:

//ARTIFICIAL POINT GENERATION ///////////////////
n: 10**4
point_lat: 80 + rand(40.0)
point_lon: 80 + rand(40.0)

mytable: {{lats: 60 + rand(n, 60.0), lons: 60 + rand(n, 60.0)}}

lats : mytable.lats
lons : mytable.lons

/////////////////////////////////////
//COMPUTATION////////////////////////

dlon: lons - point_lon
dlat: lats - point_lat

distances_km: (6378.137 * 2) * asin(mins(1,sqrt(pow(sin(dlat/2),2) + cos(point_lat) * cos(lats) * pow(sin(dlon/2) ,2))))


//distances_miles: 0.621371192  * distances_km //km to miles [statute] conversion
//sort_order: ascend distances_km

Or via the Kerf iOS SDK. Removing the semicolon at the end of a statement will allow you to log it as JSON to the terminal.

KSKerfSDK *kerf = [KSKerfSDK new];

kerf.showTimingEnabled = YES;

//Sample Data Generation
[kerf jsonObjectFromCall:@"n: 10**4;"];
[kerf jsonObjectFromCall:@"point_lat: 80 + rand(40.0);"];
[kerf jsonObjectFromCall:@"point_lon: 80 + rand(40.0);"];
[kerf jsonObjectFromCall:@"mytable: {{lats: 60 + rand(n, 60.0), lons: 60 + rand(n, 60.0)}};"];
[kerf jsonObjectFromCall:@"lats : mytable.lats;"];
[kerf jsonObjectFromCall:@"lons : mytable.lons;"];

//Computation
[kerf jsonObjectFromCall:@"dlon: lons - point_lon;"];
[kerf jsonObjectFromCall:@"dlat: lats - point_lat;"];
NSLog(@"%@", [kerf jsonObjectFromCall:@"distances_km: (6378.137 * 2) * asin(mins(1,sqrt(pow(sin(dlat/2),2) + cos(point_lat) * cos(lats) * pow(sin(dlon/2) ,2)))); "]);

Answer 2

To test whether points (x,y) are inside a circle with center (cx,cy) and radius r, use the equation (x-cx)² + (y-cy)² <= r². This does not correspond to circle because longitude and latitude values do not have the same length in the earth's surface, but it's near enough. In SQL:

... WHERE (longitude - :lon) * (longitude - :lon) +
          (latitude  - :lat) * (latitude  - :lat) <= :r * :r

If you use a rectangle instead, you can use simpler expressions that have a chance of being optimized with an index:

... WHERE longitude BETWEEN :XMin AND :XMax
      AND latitude  BETWEEN :YMin AND :YMax