StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Sounds like you're building a rideshare website. :)</p> <p>The bottom line is that in order to sort your query result by surface distance, you'll need spatial indexing built into the database engine. I think your options here are MySQL with OpenGIS extensions (already mentioned) or <a href="http://postgis.refractions.net/" rel="nofollow">PostgreSQL with PostGIS</a>. It looks like it's possible in ravenDB too: <a href="http://ravendb.net/documentation/indexes/sptial" rel="nofollow">http://ravendb.net/documentation/indexes/sptial</a></p> <p>But if that's not an option, there's a few other ways. Let's simplify the problem and say you just want to sort your database records by their distance to location A, since you're just doing that twice and summing the result.</p> <p>The simplest solution is to pull every record from the database and calculate the distance to location A one by one, then sort, in code. Trouble is, you end up doing a lot of redundant computations and pulling down the entire table for every query. </p> <p>Let's once again simplify and pretend we only care about the <a href="http://en.wikipedia.org/wiki/Chebyshev_distance" rel="nofollow">Chebyshev (maximum) distance</a>. This will work for narrowing our scope within the db before we get more accurate. We can do a "binary search" for nearby records. We must decide an approximate number of closest records to return; let's say <strong>10</strong>. Then we query inside of a square area, let's say 1 degree latitude by 1 degree longitude (that's about 60x60 miles) around the location of interest. Let's say our location of interest is lat,lng=43.5,86.5. Then our db query is SELECT COUNT(*) FROM locations WHERE (lat > 43 AND lat < 44) AND (lng > 86 AND lng < 87). If you have indexes on the lat/lng fields, that should be a fast query.</p> <p>Our goal is to get just above <strong>10</strong> total results inside the box. Here's where the "binary search" comes in. If we only got 5 results, we double the box area and search again. If we got 100 results, we cut the area in half and search again. If we get 3 results immediately after that, we increase the box area by 50% (instead of 100%) and try again, proceeding until we get close enough to our 10 result target.</p> <p>Finally we take this manageable set of records and calculate their euclidean distance from the location of interest, and sort, in code.</p> <p>Good luck!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload