I wish to produce a large database of Gps navigation coordinates that may be queried by saying "Return all coordinates which are within 'n' metres of [this coordinate]".

I want so that it is as efficient as you possibly can so looping through all of the coordinates within the database and calculating whether a coordinate is at 'n' metres would not be a preferred solution.

Can there be an simpler solution?


There's support in SQL Server 2008 for storing spatial data. I have never labored by using it myself but I know you may create queries from the type you would like.

Many database systems have function for dealing with geospatial data.

Here's comparsion geospatial functions between SQL Server 2008, PosGIS and MySQL http://www.bostongis.com/PrinterFriendly.aspx?content_name=sqlserver2008_postgis_mysql_compare

If you're able to have the selection of DB, I would suggest just like rwwilden and employ SQL 2008 using its spatial data abilities. If you fail to use that solution a treadmill including spatial querying, you are able to have a look at Microsoft's own paper on Hierarchical Triangular Mesh and implement individuals things. The SDK for MSSQL '05 included an entire solution for HTM out-of-the-box too, which means you could simply take might convert it to whatever platform you're searching at using.


This is a more detail document explaining HTM and implementation. You are able to obviously become your DB of preference. You'll find the origin code to some full HTM implementation within the SDK for 2005.

GIS databases (MS PostgreSQL etc) really implement some data structure for 2- or 3d region-searches (spatial indices). The easiest sturcture may be the power grid index, then your different search trees (kd-tree, quad-tree) with R-tree because the most often used (a generalized B-tree for additional dimensions). These techniques appear sufficient.

A fundamental power grid-index (partitioning the area into power grid-cells, and looking out only within the nearby cells) could be implemented easily and may lessen the search time for you to logarithmic. The search trees are a little harder to implement, but you will find plenty of open-source implementations for many programming languages. However, generally power grid indexing is efficient enough.

I typically do that kind of query using lat/lon. Using spherical geometry, place the a bounding box around a particular point. For instance, if you have a place (X,Y) that you would like all coordinates within 1 mile (conversion to meters I'll leave being an exercise for that readers). You are able to determine a bounding box of (X-1,Y-1),(X+1,Y+1). Then you definitely query your points database while using BETWEEN operator (Choose foo FROM bar WHERE LAT BETWEEN X-1 AND X+1 AND LON BETWEEN Y-1 AND Y+1). Then you definitely do your detail distance calculation to "across the corners" of the bounding box.

The caveat is the fact that longitude line is closer together towards the top of the sphere, so you will get skewed results the even further away you're in the equator. However it still serves to rapidly filter lower your results sets.

Google "Great Circle Distance" for that information.

EDIT: You will find .167469 levels of longitude per mile (it really ranges from .167469 to .014564), and .014483 levels of latitude per mile. So that your bounding box is (lat - (miles * 0.014483), lon - (miles * 0.167469)), (lat + (miles * 0.014483), lon + (miles * 0.167469))

Following on Erich - for those who have your decision use PostGIS (postgresql) it's free and free, does the queries you're explaining super rapidly, operates on just about all platforms, and i adore it's free?