8

I have a database with a lot of points in WGS84. Now I am building an cache that performs NN and points in range queries using a KDtree. The point [sic] is that the search radius will be provided in meters and that lat/lon is not a nice SRS for these geometric queries.

I am looking for a geometric SRS that is applicable to the whole world and that preserves distances. I don't care about errors of a couple of 10ths of meters.

Improve this question
1
  • Why not convert all points to 3D xyz (geocentric) coordinates and build your KD tree on that? Although it does not preserve distances, distances on the sphere are easily converted to distances in 3D for querying purposes. It's so easy, in fact, to convert lat-lon to xyz with an ellipsoidal model that you needn't sacrifice any accuracy at all, but even if you use a spherical model, all distances should be accurate to about 0.3% (at worst).
    – whuber
    Commented Nov 29, 2012 at 16:41

2 Answers 2

Reset to default
4

With SRS/Map projections, it's always a trade off. There really isn't one that is a good fit for all places of the world. Might as well assume that the earth is a sphere.

Instead of looking for a SRS that fits the whole world, I think you're better of looking for distance calculation algorithms. An example is the Great Circle Distance which is based on spherical trigonometry. It does make assumptions though like:

  • 1 minute of arc is 1 nautical mile
  • 1 nautical mile is 1.852 km.

The formula is:

D = 1.852 * 60 * ARCOS ( SIN(L1) * SIN(L2) + COS(L1) * COS(L2) * COS(DG)

Where:

L1  =   latitude at the first point (degrees)
L2  =   latitude at the second point (degrees)
G1  =   longitude at the first point (degrees)
G2  =   longitude at the second point (degrees)
DG  =   longitude of the second point minus longitude of the first point (degrees)
DL  =   latitude of the second point minus latitude of the first point (degrees)
D   =   computed distance (km)

You might want to test it with your data first though and see the results. Btw, are you using a spatial database like PostGIS?

Improve this answer
8
  • Well, that is the point. Postgis is not fast enough for me. What I do right now is put all points in redis and make a KDtree index on top of it. BUT the KDtree is a geometric solution. If I ask it a question like "give all points in 1k radius" it treads the distance geometrically. I cant do haversine there. I need to convert it beforehand to a roughly equidistant SRS. But which one?
    – RickyA
    Commented Nov 29, 2012 at 14:03
  • Updated my answer with the formula. That's the problem, there is no projected(geometric) SRS/CRS that's applicable to the whole world.
    – R.K.
    Commented Nov 29, 2012 at 14:08
  • And the best approx? I don't really care about the poles, only penguins there, but something that performs geometrically better than WGS84?
    – RickyA
    Commented Nov 29, 2012 at 14:12
  • Postgis supports spherical plane when using geography type instead of geometry. postgis.refractions.net/docs/…
    – nickves
    Commented Nov 29, 2012 at 14:13
  • 1
    @nickves yes I saw that, but postgis is really not fast enough for me. I need less then 2ms latency and should be able to handle 1000 request per sec. I could reverse engineer postgis's solutions though :)
    – RickyA
    Commented Nov 29, 2012 at 14:20
2

I did some googling for "Spherical Spatial Index". There's a bunch of possible methods using triangular decomposition of the sphere, or voronoi tilings. One method that looks easily implementable though, is to consider your data in 3d, as in the "3D Bounding Box" section here:

http://lin-ear-th-inking.blogspot.co.uk/2007/09/geodetic-data-in-postgis-spherical.html

Then you need a 3d spatial index of some kind, then you can rapidly find all points within your 1km. This would be a 1km 3D search radius, so slightly different to a 1km radius along the surface of the earth, but for small search radii, it would be effectively identical (do the maths to work out the correction).

If you want absolute precision, use this as a first step and then compute the distances via great circle to eliminate those further away (distance along a sphere is always greater than distance through a sphere).

Improve this answer
1
  • Hey, that is an idea! I could squeeze in another dimension in my KDTree and work with that. Will need some rework though :)
    – RickyA
    Commented Nov 29, 2012 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.