flatbush

flatbush-go

flatbush-go is a packed Hilbert R-tree adapted from mourner/flatbush and inspired by tidwall/rtree.

Usage

Installing

To start using flatbush-go, install Go and run go get:

$ go get -u github.com/invisiblefunnel/flatbush-go

Basic Operations

// Build index
builder := flatbush.NewBuilder()
for _, item := range items {
    builder.Add(item.MinX, item.MinY, item.MaxX, item.MaxY)
}

// A lower degree (node size) may improve search speed
// at the cost of increased time to build the index
index, err := builder.Finish(flatbush.DefaultDegree)
if err != nil {
    log.Fatalln(err)
}

var results []int

// Query for items intersecting a bounding box
index.Search(minX, minY, maxX, maxY, func(i int) bool {
    results = append(results, i)
    return true // return false to terminate the search early
})

// Find the k nearest neighbors using Euclidean distance
k := 5
results = results[:0]
index.Neighbors(x, y, flatbush.BoxDist, func (i int, dist float64) (next bool) {
    results = append(results, i)
    return len(results) < k
})

// Find the k nearest neighbors using geographic distance
// `flatbush.GeoBoxDist` will account for Earth's curvature and antimeridian wrapping.
results = results[:0]
index.Neighbors(lon, lat, flatbush.GeoBoxDist, func (i int, meters float64) (next bool) {
    results = append(results, i)
    return len(results) < k
})

// Find the k nearest neighbors using a custom item distance function. Use item distance
// to account for the difference between the distance to an item's bounding box and the
// actual distance to the item.
itemDist := func(pX, pY float64, i int) float64 {
    // units must match the box dist function
    return items[i].Distance(pX, pY)
}

results = results[:0]
index.NeighborsByItemDist(lon, lat, flatbush.GeoBoxDist, itemDist, func (i int, meters float64) (next bool) {
    results = append(results, i)
    return len(results) < k
})

for _, i := range results {
    fmt.Println(i, items[i].Name)
}

// Serialize the index to bytes for storage or transport.
var data []byte
data, err = flatbush.Marshal(index)

// Read the index from bytes
index, err = flatbush.Unmarshal(data)

Should you use this library?

You should probably just use tidwall/rtree, but let's talk it through. Do you need a serializable rtree? Are you sure? It’s usually fast to build one on-demand, have you benchmarked? Do you need to update the rtree after you begin querying? No? So, you're working with effectively static datasets? Ok, great, consider using this library.