README
¶
microspace 
Microspace is a spatial index that's optimized for very fast building and nearest-n lookups.
Performance Characteristics
- Inserting
npoints ultimately runs inO(n log n)time. - In the worse case, querying for the nearest neighbor runs in
O(n)time. - But in practice it runs much faster. In the benchmark random distribution, querying for nearest neighbors in a set size of 10000 took ~10 nanoseconds longer than querying in a set size of 10.
# Generating a tree with `n` elements:
BenchmarkIndexCreate10 200000 6010 ns/op
BenchmarkIndexCreate100 20000 64149 ns/op
BenchmarkIndexCreate1000 2000 839679 ns/op
BenchmarkIndexCreate10000 200 8848370 ns/op
# Querying for 3 nearest neighbors in a random set of `n` elements:
BenchmarkIndexNearest10 5000000 294 ns/op
BenchmarkIndexNearest100 5000000 287 ns/op
BenchmarkIndexNearest1000 5000000 286 ns/op
BenchmarkIndexNearest10000 5000000 305 ns/op
# Querying for 3 nearest neighbors in the worst-case set of `n` elements:
BenchmarkIndexNearestWorstCase10 3000000 485 ns/op
BenchmarkIndexNearestWorstCase100 500000 2642 ns/op
BenchmarkIndexNearestWorstCase1000 100000 23939 ns/op
BenchmarkIndexNearestWorstCase10000 5000 240544 ns/op
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Axdex ¶
type Axdex struct {
// contains filtered or unexported fields
}
func NewAxdex ¶
NewAxdex returns a new axis-based index with the provided capacity. It's assumed that you will insert exactly `capacity` points before running queries against the index.
type Index ¶
type Index interface {
// NearestN returns up the `n` nearest neighbors of the point, with
// a `max` search distance. `n` May be set to -1 to search for all
// neighbors in the distance.8
NearestN(p *Point, n int, max float32) []*Point
// Points returns all points contained in the spatial index.
Points() []*Point
}
Index describes a spatial index that can look up a point's nearest neighbors.
type Point ¶
type Point struct{ X, Y float32 }
Point represents a point in two-dimensional space.
func (*Point) DistanceToSqr ¶
DistanceToSqr returns the squared distance to the `other` point.
Source Files
Click to show internal directories.
Click to hide internal directories.