flatbush

README

Flatbush (Go port)

This is a Go port of https://github.com/mourner/flatbush.

Usage

// Create a new flatbush spatial index (type must be one of int8,int16,int32,int64,float32,float64)
// The type parameter defines the type of the box coordinates.
f := flatbush.NewFlatbush[float64]()

// Populate the tree
for _, b := range boxes {
	f.Add(b.MinX, b.MinY, b.MaxX, b.MaxY)
}

// Finish creation of the spatial index
f.Finish()

// Find all boxes that overlap the given bounding box
results := f.Search(minX, minY, maxX, maxY)

// Results is an []int, containing zero-based indices of the objects in the tree,
// according to their insertion order.

Times

Measurements taken on Intel Core i7-11850H @ 2.50GHz

• Time to insert 1000000 elements: 91 milliseconds
• Time per query, returning average of 25 elements: 400 nanoseconds

Documentation

Index

• func MinMaxValueOfType[T Coord](min, max *T)
• type Box
  • func InvertedBox[T Coord]() Box[T]
  • func (a *Box[T]) PositiveUnion(b *Box[T]) bool
• type Coord
• type Flatbush
  • func NewFlatbush[T Coord]() *Flatbush[T]
  • func (f *Flatbush[T]) Add(minX, minY, maxX, maxY T) int
  • func (f *Flatbush[T]) Finish()
  • func (f *Flatbush[T]) Reserve(size int)
  • func (f *Flatbush[T]) Search(minX, minY, maxX, maxY T) []int
  • func (f *Flatbush[T]) SearchFast(minX, minY, maxX, maxY T, results []int) []int
• type MinMaxFloat32
• type MinMaxFloat64
• type MinMaxInt16
• type MinMaxInt32
• type MinMaxInt64
• type MinMaxInt8

Functions

func MinMaxValueOfType

func MinMaxValueOfType[T Coord](min, max *T)

MinMaxValueOfType returns the minimum and maximum value for the given numeric type T.

Types

type Box

type Box[T Coord] struct {
	MinX  T
	MinY  T
	MaxX  T
	MaxY  T
	Index int
}

func InvertedBox

func InvertedBox[T Coord]() Box[T]

func (*Box[T]) PositiveUnion

func (a *Box[T]) PositiveUnion(b *Box[T]) bool

type Coord

type Coord interface {
	int8 | int16 | int32 | int64 | float32 | float64
}

Define a type constraint for all numeric types we're interested in

type Flatbush

type Flatbush[T Coord] struct {
	NodeSize int // Minimum 2. Default 16
	// contains filtered or unexported fields
}

Flatbush is a spatial index for efficient 2D queries. The coordinates are one of *Coord*

func NewFlatbush

func NewFlatbush[T Coord]() *Flatbush[T]

Create a new Flatbush with one *Coord* type

func (*Flatbush[T]) Add

func (f *Flatbush[T]) Add(minX, minY, maxX, maxY T) int

Add a new box, and return its index. The index of the box is zero based, and corresponds 1:1 with the insertion of order of the boxes. You must add all boxes before calling Finish().

func (*Flatbush[T]) Finish

func (f *Flatbush[T]) Finish()

Finish builds the spatial index, so that it can be queried.

func (*Flatbush[T]) Reserve

func (f *Flatbush[T]) Reserve(size int)

Reserve enough boxes for the given number of items

func (*Flatbush[T]) Search

func (f *Flatbush[T]) Search(minX, minY, maxX, maxY T) []int

Search for all boxes that overlap the given query box.

func (*Flatbush[T]) SearchFast

func (f *Flatbush[T]) SearchFast(minX, minY, maxX, maxY T, results []int) []int

SearchFast accepts a 'results' as input. If you are performing millions of queries, then reusing a 'results' slice will reduce the number of allocations.

type MinMaxFloat32

type MinMaxFloat32 struct {
	Min float32
	Max float32
}

type MinMaxFloat64

type MinMaxFloat64 struct {
	Min float64
	Max float64
}

type MinMaxInt16

type MinMaxInt16 struct {
	Min int16
	Max int16
}

type MinMaxInt32

type MinMaxInt32 struct {
	Min int32
	Max int32
}

type MinMaxInt64

type MinMaxInt64 struct {
	Min int64
	Max int64
}

type MinMaxInt8

type MinMaxInt8 struct {
	Min int8
	Max int8
}

This method of using structs was a workaround for a bug in the Go 1.22 compiler/linker.