geoindex

README

geoindex

Simplified interface and extension utilities for a geospatial indexes.

Documentation

Index

• Variables
• type Index
  • func Wrap(tree Interface) *Index
  • func (index *Index) Bounds() (min, max [2]float64)
  • func (index *Index) Children(parent interface{}, reuse []child.Child) (children []child.Child)
  • func (index *Index) Delete(min, max [2]float64, data interface{})
  • func (index *Index) Insert(min, max [2]float64, data interface{})
  • func (index *Index) Len() int
  • func (index *Index) Nearby(algo func(min, max [2]float64, data interface{}, item bool) (dist float64), ...)
  • func (index *Index) SVG() string
  • func (index *Index) Scan(iter func(min, max [2]float64, data interface{}) bool)
  • func (index *Index) Search(min, max [2]float64, iter func(min, max [2]float64, data interface{}) bool)
• type Interface

Variables

var Tests = struct {
	TestBenchVarious      func(t *testing.T, tr Interface, numPointOrRects int)
	TestRandomPoints      func(t *testing.T, tr Interface, numPoints int)
	TestRandomRects       func(t *testing.T, tr Interface, numRects int)
	TestCitiesSVG         func(t *testing.T, tr Interface)
	TestRandomSVG         func(t *testing.T, tr Interface)
	TestZeroPoints        func(t *testing.T, tr Interface)
	BenchmarkRandomInsert func(b *testing.B, tr Interface)
}{
	benchVarious,
	func(t *testing.T, tr Interface, numRects int) {
		testBoxesVarious(t, tr, randBoxes(numRects), "boxes")
	},
	func(t *testing.T, tr Interface, numPoints int) {
		testBoxesVarious(t, tr, randPoints(numPoints), "points")
	},
	testCitiesSVG,
	testRandomSVG,
	testZeroPoints,
	benchmarkRandomInsert,
}

Tests is a set of tests for running against an object that conforms to geoindex.Interface. These functions are intended to be included in a `_test.go` file. A complete test file might look something like:

package myrtree

import (
	"math/rand"
	"testing"
	"time"

	"github.com/tidwall/geoindex"
)

func init() {
	seed := time.Now().UnixNano()
	println("seed:", seed)
	rand.Seed(seed)
}

func TestGeoIndex(t *testing.T) {
	t.Run("BenchInsert", func(t *testing.T) {
		geoindex.Tests.TestBenchInsert(t, &RTree{}, 100000)
	})
	t.Run("RandomRects", func(t *testing.T) {
		geoindex.Tests.TestRandomRects(t, &RTree{}, 10000)
	})
	t.Run("RandomPoints", func(t *testing.T) {
		geoindex.Tests.TestRandomPoints(t, &RTree{}, 10000)
	})
	t.Run("ZeroPoints", func(t *testing.T) {
		geoindex.Tests.TestZeroPoints(t, &RTree{})
	})
	t.Run("CitiesSVG", func(t *testing.T) {
		geoindex.Tests.TestCitiesSVG(t, &RTree{})
	})
}

func BenchmarkRandomInsert(b *testing.B) {
	geoindex.Tests.BenchmarkRandomInsert(b, &RTree{})
}

Types

type Index

type Index struct {
	// contains filtered or unexported fields
}

Index is a wrapper around Interface that provides extra features like a Nearby (kNN) function. This can be created like such:

var tree = &rtree.RTree{}
var index = index.Index{tree}

Now you can use `index` just like tree but with the extra features.

func Wrap

func Wrap(tree Interface) *Index

Wrap a tree-like geospatial interface.

func (*Index) Bounds

func (index *Index) Bounds() (min, max [2]float64)

Bounds returns the minimum bounding box

func (*Index) Children

func (index *Index) Children(parent interface{}, reuse []child.Child) (
	children []child.Child,
)

Children returns all children for parent node. If parent node is nil then the root nodes should be returned. The reuse buffer is an empty length slice that can optionally be used to avoid extra allocations.

func (*Index) Delete

func (index *Index) Delete(min, max [2]float64, data interface{})

Delete an item from the index

func (*Index) Insert

func (index *Index) Insert(min, max [2]float64, data interface{})

Insert an item into the index

func (*Index) Len

func (index *Index) Len() int

Len returns the number of items in tree

func (*Index) Nearby

func (index *Index) Nearby(
	algo func(min, max [2]float64, data interface{}, item bool) (dist float64),
	iter func(min, max [2]float64, data interface{}, dist float64) bool,
)

Nearby performs a kNN-type operation on the index. It's expected that the caller provides its own the `algo` function, which is used to calculate a distance to data. The `add` function should be called by the caller to "return" the data item along with a distance. The `iter` function will return all items from the smallest dist to the largest dist. Take a look at the SimpleBoxAlgo function for a usage example.

func (*Index) SVG

func (index *Index) SVG() string

SVG prints 2D rtree in wgs84 coordinate space

func (*Index) Scan

func (index *Index) Scan(
	iter func(min, max [2]float64, data interface{}) bool,
)

Scan iterates through all data in tree in no specified order.

func (*Index) Search

func (index *Index) Search(
	min, max [2]float64,
	iter func(min, max [2]float64, data interface{}) bool,
)

Search the index for items that intersects the rect param

type Interface

type Interface interface {
	// Insert an item into the structure
	Insert(min, max [2]float64, data interface{})
	// Delete an item from the structure
	Delete(min, max [2]float64, data interface{})
	// Replace an item in the structure. This is effectively just a Delete
	// followed by an Insert. But for some structures it may be possible to
	// optimize the operation to avoid multiple passes
	Replace(
		oldMin, oldMax [2]float64, oldData interface{},
		newMin, newMax [2]float64, newData interface{},
	)
	// Search the structure for items that intersects the rect param
	Search(
		min, max [2]float64,
		iter func(min, max [2]float64, data interface{}) bool,
	)
	// Scan iterates through all data in tree in no specified order.
	Scan(iter func(min, max [2]float64, data interface{}) bool)
	// Len returns the number of items in tree
	Len() int
	// Bounds returns the minimum bounding box
	Bounds() (min, max [2]float64)
	// Children returns all children for parent node. If parent node is nil
	// then the root nodes should be returned.
	// The reuse buffer is an empty length slice that can optionally be used
	// to avoid extra allocations.
	Children(parent interface{}, reuse []child.Child) (children []child.Child)
}

Interface is a tree-like structure that contains geospatial data