rtreego: github.com/dhconnelly/rtreego Index | Files

package rtreego

import "github.com/dhconnelly/rtreego"

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

Index

Package Files

filter.go geom.go rtree.go

type Comparator Uses

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

Comparator compares two spatials and returns whether they are equal.

type DimError Uses

type DimError struct {
    Expected int
    Actual   int
}

DimError represents a failure due to mismatched dimensions.

func (DimError) Error Uses

func (err DimError) Error() string

type DistError Uses

type DistError float64

DistError is an improper distance measurement. It implements the error and is generated when a distance-related assertion fails.

func (DistError) Error Uses

func (err DistError) Error() string

type Filter Uses

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 Uses

func LimitFilter(limit int) Filter

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

type Point Uses

type Point []float64

Point represents a point in n-dimensional Euclidean space.

func (Point) ToRect Uses

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

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

type Rect Uses

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 NewRect Uses

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

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 Uses

func NewRectFromPoints(minPoint, maxPoint Point) (r *Rect, err error)

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

func (*Rect) Equal Uses

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

Equal returns true if the two rectangles are equal

func (*Rect) LengthsCoord Uses

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

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

func (*Rect) PointCoord Uses

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

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

func (*Rect) Size Uses

func (r *Rect) Size() float64

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

func (*Rect) String Uses

func (r *Rect) String() string

type Rtree Uses

type Rtree struct {
    Dim         int
    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 NewTree Uses

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

NewTree 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 Uses

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 Uses

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 Uses

func (tree *Rtree) Depth() int

Depth returns the maximum depth of tree.

func (*Rtree) GetAllBoundingBoxes Uses

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 Uses

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 Uses

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 Uses

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

NearestNeighbors gets the closest Spatials to the Point.

func (*Rtree) SearchIntersect Uses

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 Uses

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 Uses

func (tree *Rtree) Size() int

Size returns the number of objects currently stored in tree.

func (*Rtree) String Uses

func (tree *Rtree) String() string

type Spatial Uses

type Spatial interface {
    Bounds() *Rect
}

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

Package rtreego imports 4 packages (graph) and is imported by 29 packages. Updated 2020-03-31. Refresh now. Tools for package owners.