Array of geohashes based on point and radius

[Irrelon]

Hey, first off thanks for the awesome module!

I wondered if you might be able to point me in the correct direction here, I'm trying to get all geohashes that fit inside a radius from a long / lat.

The output I'm looking for would be something like this (totally random made up geohashes - probably wont resolve to any locations):

['rtgerhgwefefwef', 'hgtrgrewfgewd', 'ehgergewdfqwefd', 'htrwergffeefwwee','wefewfwef','herthtrehgre']

So if I call something like: getHashesInRadiusFromPoint(long, lat, radius); it will return that array of hashes.

Is this something that node-geo-proximity can achieve? I'm guessing it's all there but there isn't a method to call to do it yet?

Many thanks,

Rob

[arjunmehta]

Hey Rob!

There isn't currently implemented a way to get the raw geohashes... the soonest I could implement that would be in 2 or 3 days, but you're right, it's all there.

But there is the values option when querying a point:

proximity.query(43.646838, -79.403723, 5000, {values: true}, function(err, replies){
  if(err) console.error(err);
  console.log(replies);
});

This returns an array of names WITH lat/lon coordinates.

[Irrelon]

Many thanks for your response! Does that query work if no prior call to addCoordinate is made? My use case is perhaps a bit specific but I have realtime websocket streams pushing to channels that are named by geohashes. I want a client to be able to subscribe to every channel that exists inside their point and radius but calculating all those geohashes seems quite complex... hence I was looking for a library that could do it and stumbled across this!

[arjunmehta]

Ah! I think I understand what you're trying to do. I think this module may be overkill BUT I think I can help and create a new module that may help.

You want to look into geohash neighbors. I've worked on the node-geohash module as well and I think neighbors is what you want to look at. The problem is you need to equate a radius to a geohash bit depth.

I can create a module that converts a human radius (meters) to a geohash bit depth. There is already a table I'm using in this module (geo-proximity). If you're curious you can look at the main.js file and see the rangeDepth method.

[hems]

@Irrelon i'm trying to do something similar.. have you managed to solve your problem?

I also stumbled on this redis-geo which seems to automatically create this pub/sub channels for each item on the list, but i'm trying to avoid running the redis server myself, at least at early stages.

@arjunmehta i think we could achieve something very similar with your module, right? Basically we would need to create a pub/sub channel for each item, so then we can subscribe to multiple channels in order to keep track of them. Similar to what waze do when they present multiple cars in the map.

Any insights are more than appreciated ( :

Sorry for the semi-off-topic-plus-question-comment

thanks for your work :+1:

[arjunmehta]

@hems @Irrelon Sorry about not following up on this. I got distracted!

I just realized, if you just need all the geohashes that exist within a radius from a specific point, you can use the proximity.getQueryCache method. It will give you a set of ranges of all geohashes within the radius from the spec'd lat/lon. These will be given at the geohash resolution they're stored in (ie. 52-bit).

I'm not sure if you an create pub/subs for ranges... or if you'd want to for the huge sets of geohashes.

An alternative is to reduce the resolution specific to the radius. That would be much more efficient, of course! But I'd need to modify the methods to not increase the ranges' resolution to 52-bits. Let me see what I can do in the next two days. :)

@hems my hypothesis is that redis-geo is VERY fast as it is native. It uses the same algorithm that this module uses, I believe, but since it's baked into redis as an extension (C++ I believe) it'll be really fast. But it requires a special redis build and custom compiling etc. I've been wanting to do a performance comparison with this module, mongo's spatial index, and redis-geo for a while!

[hems]

@arjunmehta might be a good time to do now that mongo 3 is out!

although from my personal experience with redis and mongo, mongo has a very little change of wining..

what i like about redis-geo is that it gives a pub/sub for each "member" ( please correct me if i understood something wrong ).

what i really like about your module is that i don't need to roll my own instance of redis, which is kind of counter-productive if you want to focus on building your product instead of dealing with server management.

i think just the time and real life tests will bring the right answer for us ( :

[arjunmehta]

@hems @Irrelon Hey guys, I've added a new method to the module!

The new method is: proximity.getGeohashArray(lat, lon, radius) This will return an object that has two properties: A hashArray of 9 geohashes that, together, approximately bound the given radius and the bitDepth of these hashes, which corresponds to the radius value provided. This means that this is probably only useful if your search radius remains consistent.

You can subscribe to all 9 of these hashes and any point that is hashed at the given bitDepth that matches, you'll know is within the radius of the original lat/lon.

Does this make sense and match what you were looking for? This is an example of the object returned:

var hashArray = proximity.getGeohashArray(43.646838, -79.403723, 50000)
console.log(hashArray)
/*
{
    bitDepth: 20,
    hashArray: [
        415671,
        415677,
        415679,
        415714,
        415715,
        415720,
        415721,
        415722,
        415723
    ]
}
*/

To use this branch:

npm install "git://github.com/arjunmehta/node-geo-proximity.git#hashArray"

I will merge it to master shortly after your feedback!

Thanks :)

[Irrelon]

That is really cool. Many thanks for your hard work! :+1:

[arjunmehta]

@Irrelon Thank you! Do you think it's in-line with what you had needed? I know it's a few months ago now... :P @hems any thoughts?

[hems]

@arjunmehta to be honest i don't fully understand what is going on with this new method, i don't understand all this concepts fully, so i'm left with some beginner questions here:

1 - What exactly "bitDepth" means in this context? Bit depth is something i understand to measure "resolution", therefore i don't understand why it's presented on the response and what exactly it means in this context.

2 - I don't know which information is hashed inside of a geohash, does it contain only lat/lon ? Why it returns 9 items?

Regarding the subscription: How could i subscribe to that hash?

Sorry for my OT questions here, perhaps me and other less advanced ( fancy way of saying beginners ) users would need some examples on the readme ( :

thanks again!

:+1:

[arjunmehta]

@hems AH! I wasn't aware that you didn't know about geohashes. To answer your questions in reverse order (makes more sense):

1. A geohash is a way of combining both latitude and longitude (2 separate values) into a single hashed value. The problem with any mapping of more than 1 point to a single value is that the mapping by nature will be approximate, and represent boxes* (vs definite points). This module uses geohashes as an inherent part of its algorithm.
2. bitDepth in this context is the level of resolution at which to resolve the geohash. The higher the resolution, the smaller the box is, and the more accurate the geohash box will be to the original latitude and longitude values. The lower the resolution, the larger the box is and the less accurate the box will be at representing the original point. I've written a two part post that describes how this module works, but also intros into how geohashes work too.

The reason why we use 9 hash values is explained in the second part of my post, but basically if you want to know which points from a set {X} that lie within a certain radius of another point p, creating a new set {P}, you can "geohash" all points in {X} that would be candidate members of {P} and see if they live within boxes that approximately match the radius from the point p. You use 9 boxes instead of finding all points that share the same geohash box because of the way geohashes work (again, explained in my posts), two coordinates that may be literally only a meter apart could have two very different geohashes.

So in the case of this method, if you want to know all the points within a given radius at a given lat, lon, this will

1. Give you the bitDepth that associates with the given radius. You will use this to geohash your coordinates with. Then you will publish a name, or some other identifier to that geohash channel.
2. It will give the 9 geohash values that associate with point p and the given radius. So you know that any coordinate geohashed at the given bitDepth from {X} that matches any of the 9 geohashes provided is within a certain (approximate) radius from p.

Whooo. Complicated I know. But it's actually a really fast algorithm. Not sure how fast pub/sub is though. This method definitely doesn't do that for you. It would actually be really awesome if I could find the time to include that as a method in this module! Subscriptions to locations! Now that's an idea. :)

[hems]

@arjunmehta super awesome! to be honest it is exactly what i thought but my lack of experience made me totally unconfident about my assumptions!

Thank you so much for taking your time to do the module and explain it really well!

( :

hopefully we speak soon from within the same box!

[arjunmehta]

Deferring this, as the module has changed focus.

[hems]

:+1: