NEARBY about buntdb HOT 16 CLOSED

Right now BuntDB is limited to intersection searches on rectangles and points.

If what you are wanting is to find all points that are within a specified radius, such as:

Then may I suggest this approach.

1. Calculate the bounding box around the circle

2. Get all the points in the rectangle

3. Perform the haversine calculation on each point

This is pretty much how Tile38 does it. Below is some code that you might find helpful.

Calculate Bounds of a Geo Circle
Haversine Formula

from buntdb.

Thanks for the feedback. I’m actually just after the nearest point so might just look at implementing a kd-tree instead.

I thought Tile38 did that sort of query with a KNN query?

from buntdb.

Ah. At the moment BuntDB doesn’t have a kNN operation.

from buntdb.

Thanks @tidwall, tile38 does at the moment doesn't it?

To use this I suppose I'd need to port the R-Tree across to BuntDB?

from buntdb.

Yes, Tile38 has support for kNN searches.

BuntDB uses an R-Tree already, so it’s possible to add kNN without modifying the underlying data structure. I just haven’t gotten around to adding the operation yet.

from buntdb.

Ok thanks, will fork away 👍

from buntdb.

Sounds good. A couple of pointers.

BuntDB uses this R-Tree package.
https://github.com/tidwall/rtree

Tile38 uses this one and includes the kNN code
https://github.com/tidwall/tile38/tree/master/index/

They have an entirely different codebases.
Tile38 rtree is strictly 2 dimensions while the BuntDB is a composite of 20 dimensions.

from buntdb.

Wow, 20!!! For a lat/lon I'll only need the 2 dimensions.

I'll see if I can tackle it but suspect I might end up just creating a bounding box around my test point and do a check and sort them by distance that way

from buntdb.

I just updated the https://github.com/tidwall/rtree project to include kNN support. And I added a Nearby function to BuntDB.

from buntdb.

Oh nice, thank you that is awesome. I had started a kd-tree implementation and then realised it was suited to a curved globe!

from buntdb.

You're welcome. :)

from buntdb.

What value is the distance operator?

I created a real simple example...
https://gist.github.com/leearmstrong/8ff311e5ffb4e6075e24f31737f2c06d

This logs

2018/01/15 10:53:37 Searching from coord [-0.919 50.819]
2018/01/15 10:53:37 aircraft:TEST:pos [-0.919 50.919] 0.009999999999998864

I make the distance 11km.

Is the distance not relative but I can be guaranteed they will be returned in order and I need to calculate the distance myself?

from buntdb.

The distance param could use a little more description, or maybe I should just removed it to avoid confusion.

It's the distance of the bounding boxes. In your case it's the distance of the two 2D points squared. The unit is the same as what was inputed, in your case degrees (lat/lon).

To get the distance on earth in meters (not in degrees) you should ignore the distance and calculate using haversine yourself.

bunt.View(func(tx *buntdb.Tx) error {
	tx.Nearby("locationIndex", locationString, func(key, val string, dist float64) bool {
		meters := haversine(locationString, val)
		return false
	})
	return nil
})

from buntdb.

from buntdb.

You're welcome. I'll just leave it for now and try to come up with a better description.

from buntdb.

I added a description of the dist param to the Nearby function comment.

from buntdb.