math

Documentation

Overview

Package rtree is a library for efficiently storing and querying spatial data.

Index

• func Intersect(r1, r2 *Rect) bool
• type Comparator
• type DistError
  • func (err DistError) Error() string
• type Filter
  • func LimitFilter(limit int) Filter
• type Point
  • func NewPoint(x, y, z float64) Point
  • func (p Point) Dist(q Point) float64
  • func (p Point) MinDist(r *Rect) float64
  • func (p Point) MinMaxDist(r *Rect) float64
  • func (p Point) SubScalar(num float64) Point
  • func (p Point) ToRect(tol float64) *Rect
  • func (p Point) X() float64
  • func (p Point) Y() float64
  • func (p Point) Z() float64
• type Rect
  • func BoundingBox(r1, r2 *Rect) (bb *Rect)
  • func BoundingBoxN(rects ...*Rect) (bb *Rect)
  • func NewRect(p Point, lengths [3]float64) (r *Rect)
  • func NewRectFromPoints(minPoint, maxPoint Point) *Rect
  • func (r *Rect) ContainsPoint(p Point) bool
  • func (r *Rect) ContainsRect(r2 *Rect) bool
  • func (r *Rect) Equal(other *Rect) bool
  • func (r *Rect) LengthsCoord(i int) float64
  • func (r *Rect) Margin() float64
  • func (r *Rect) PointCoord(i int) float64
  • func (r *Rect) Size() float64
  • func (r *Rect) String() string
• type Rtree
  • func NewRTree(min, max int, objs ...Spatial) *Rtree
  • func (tree *Rtree) Delete(obj Spatial) bool
  • func (tree *Rtree) DeleteWithComparator(obj Spatial, cmp Comparator) bool
  • func (tree *Rtree) Depth() int
  • func (tree *Rtree) GetAllBoundingBoxes() []*Rect
  • func (tree *Rtree) Insert(obj Spatial)
  • func (tree *Rtree) NearestNeighbor(p Point) Spatial
  • func (tree *Rtree) NearestNeighbors(k int, p Point, filters ...Filter) []Spatial
  • func (tree *Rtree) SearchIntersect(bb *Rect, filters ...Filter) []Spatial
  • func (tree *Rtree) SearchIntersectWithLimit(k int, bb *Rect) []Spatial
  • func (tree *Rtree) Size() int
  • func (tree *Rtree) String() string
• type Spatial

Functions

func Intersect

func Intersect(r1, r2 *Rect) bool

Intersect computes the intersection of two rectangles. If no intersection exists, the intersection is nil.

Types

type Comparator

type Comparator func(obj1, obj2 Spatial) (equal bool)

Comparator compares two spatials and returns whether they are equal.

type DistError

type DistError float64

func (DistError) Error

func (err DistError) Error() string

type Filter

type Filter func(results []Spatial, object Spatial) (refuse, abort bool)

Filter is an interface for filtering leaves during search. The parameters should be treated as read-only. If refuse is true, the current entry will not be added to the result set. If abort is true, the search is aborted and the current result set will be returned.

func LimitFilter

func LimitFilter(limit int) Filter

LimitFilter checks if the results have reached the limit size and aborts if so.

type Point

type Point [3]float64

Point represents a point in n-dimensional Euclidean space.

func NewPoint

func NewPoint(x, y, z float64) Point

func (Point) Dist

func (p Point) Dist(q Point) float64

Dist computes the Euclidean distance between two points p and q.

func (Point) MinDist

func (p Point) MinDist(r *Rect) float64

MinDist computes the square of the distance from a point to a rectangle. If the point is contained in the rectangle then the distance is zero.

Implemented per Definition 2 of "Nearest Neighbor Queries" by N. Roussopoulos, S. Kelley and F. Vincent, ACM SIGMOD, pages 71-79, 1995.

func (Point) MinMaxDist

func (p Point) MinMaxDist(r *Rect) float64

MinMaxDist computes the minimum of the maximum distances from p to points on r. If r is the bounding box of some geometric objects, then there is at least one object contained in r within MinMaxDist(p, r) of p.

Implemented per Definition 4 of "Nearest Neighbor Queries" by N. Roussopoulos, S. Kelley and F. Vincent, ACM SIGMOD, pages 71-79, 1995.

func (Point) SubScalar

func (p Point) SubScalar(num float64) Point

func (Point) ToRect

func (p Point) ToRect(tol float64) *Rect

ToRect constructs a rectangle containing p with side lengths 2*tol.

func (Point) X

func (p Point) X() float64

func (Point) Y

func (p Point) Y() float64

func (Point) Z

func (p Point) Z() float64

type Rect

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

Rect represents a subset of n-dimensional Euclidean space of the form [a1, b1] x [a2, b2] x ... x [an, bn], where ai < bi for all 1 <= i <= n.

func BoundingBox

func BoundingBox(r1, r2 *Rect) (bb *Rect)

BoundingBox constructs the smallest rectangle containing both r1 and r2.

func BoundingBoxN

func BoundingBoxN(rects ...*Rect) (bb *Rect)

BoundingBoxN constructs the smallest rectangle containing all of r...

func NewRect

func NewRect(p Point, lengths [3]float64) (r *Rect)

NewRect constructs and returns a pointer to a Rect given a corner point and the lengths of each dimension. The point p should be the most-negative point on the rectangle (in every dimension) and every length should be positive.

func NewRectFromPoints

func NewRectFromPoints(minPoint, maxPoint Point) *Rect

NewRectFromPoints constructs and returns a pointer to a Rect given a corner points.

func (*Rect) ContainsPoint

func (r *Rect) ContainsPoint(p Point) bool

ContainsPoint tests whether p is located inside or on the boundary of r.

func (*Rect) ContainsRect

func (r *Rect) ContainsRect(r2 *Rect) bool

ContainsRect tests whether r2 is is located inside r1.

func (*Rect) Equal

func (r *Rect) Equal(other *Rect) bool

Equal returns true if the two rectangles are equal

func (*Rect) LengthsCoord

func (r *Rect) LengthsCoord(i int) float64

LengthsCoord returns the coordinate of the lengths of the rectangle at i

func (*Rect) Margin

func (r *Rect) Margin() float64

Margin computes the sum of the edge lengths of a rectangle.

func (*Rect) PointCoord

func (r *Rect) PointCoord(i int) float64

PointCoord returns the coordinate of the point of the rectangle at i

func (*Rect) Size

func (r *Rect) Size() float64

Size computes the measure of a rectangle (the product of its side lengths).

func (*Rect) String

func (r *Rect) String() string

type Rtree

type Rtree struct {
	MinChildren int
	MaxChildren int
	// contains filtered or unexported fields
}

Rtree represents an R-tree, a balanced search tree for storing and querying spatial objects. Dim specifies the number of spatial dimensions and MinChildren/MaxChildren specify the minimum/maximum branching factors.

func NewRTree

func NewRTree(min, max int, objs ...Spatial) *Rtree

NewRTree returns an Rtree. If the number of objects given on initialization is larger than max, the Rtree will be initialized using the Overlap Minimizing Top-down bulk-loading algorithm.

func (*Rtree) Delete

func (tree *Rtree) Delete(obj Spatial) bool

Delete removes an object from the tree. If the object is not found, returns false, otherwise returns true. Uses the default comparator when checking equality.

Implemented per Section 3.3 of "R-trees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 47-57, 1984.

func (*Rtree) DeleteWithComparator

func (tree *Rtree) DeleteWithComparator(obj Spatial, cmp Comparator) bool

DeleteWithComparator removes an object from the tree using a custom comparator for evaluating equalness. This is useful when you want to remove an object from a tree but don't have a pointer to the original object anymore.

func (*Rtree) Depth

func (tree *Rtree) Depth() int

Depth returns the maximum depth of tree.

func (*Rtree) GetAllBoundingBoxes

func (tree *Rtree) GetAllBoundingBoxes() []*Rect

GetAllBoundingBoxes returning slice of bounding boxes by traversing tree. Slice includes bounding boxes from all non-leaf nodes.

func (*Rtree) Insert

func (tree *Rtree) Insert(obj Spatial)

Insert inserts a spatial object into the tree. If insertion causes a leaf node to overflow, the tree is rebalanced automatically.

Implemented per Section 3.2 of "R-trees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 47-57, 1984.

func (*Rtree) NearestNeighbor

func (tree *Rtree) NearestNeighbor(p Point) Spatial

NearestNeighbor returns the closest object to the specified point. Implemented per "Nearest Neighbor Queries" by Roussopoulos et al

func (*Rtree) NearestNeighbors

func (tree *Rtree) NearestNeighbors(k int, p Point, filters ...Filter) []Spatial

NearestNeighbors gets the closest Spatials to the Point.

func (*Rtree) SearchIntersect

func (tree *Rtree) SearchIntersect(bb *Rect, filters ...Filter) []Spatial

SearchIntersect returns all objects that intersect the specified rectangle. Implemented per Section 3.1 of "R-trees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 47-57, 1984.

func (*Rtree) SearchIntersectWithLimit

func (tree *Rtree) SearchIntersectWithLimit(k int, bb *Rect) []Spatial

SearchIntersectWithLimit is similar to SearchIntersect, but returns immediately when the first k results are found. A negative k behaves exactly like SearchIntersect and returns all the results.

Kept for backwards compatibility, please use SearchIntersect with a LimitFilter.

func (*Rtree) Size

func (tree *Rtree) Size() int

Size returns the number of objects currently stored in tree.

func (*Rtree) String

func (tree *Rtree) String() string

type Spatial

type Spatial interface {
	Bounds() *Rect
}

Spatial is an interface for objects that can be stored in an Rtree and queried.