README
¶
QuadTree
Golang implementation of the quadtree algorithm. Includes removal, update and knearest search.
Godoc https://godoc.org/github.com/asim/quadtree
Usage Example
Create a quadtree fitting the world geographic bounds (from [-90,-180] to [90,180])
centerPoint := quadtree.NewPoint(0.0, 0.0, nil)
halfPoint := quadtree.NewPoint(90.0, 180.0, nil)
boundingBox := quadtree.NewAABB(centerPoint, halfPoint)
qtree := quadtree.New(boundingBox, 0, nil)
Insert a point into the tree
point := quadtree.NewPoint(52.5200, 13.4050, "Berlin")
if !qtree.Insert(point) {
log.Fatal("Failed to insert the point")
}
Find the k-nearest points
center := quadtree.NewPoint(lat, lng, nil)
distance := 10000 /* Distance to the center point in meters */
bounds := quadtree.NewAABB(center, center.HalfPoint(distance))
maxPoints := 10
for _, point := range qtree.KNearest(bounds, maxPoints, nil) {
log.Printf("Found point: %s\n", point.Data().(string))
}
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( Capacity = 8 MaxDepth = 6 )
Functions ¶
This section is empty.
Types ¶
type AABB ¶
type AABB struct {
// contains filtered or unexported fields
}
func (*AABB) ContainsPoint ¶
ContainsPoint checks whether the point provided resides within the axis aligned bounding box.
type Point ¶
type Point struct {
// contains filtered or unexported fields
}
func (*Point) Coordinates ¶
Coordinates return the x and y coordinates of a point.
type QuadTree ¶
type QuadTree struct {
// contains filtered or unexported fields
}
func New ¶
New creates a new *QuadTree. It requires a boundary defining the center and half points, depth at which the QuadTree resides and parent node. Depth of 0 and parent as nil implies the root node.
func (*QuadTree) Insert ¶
Insert will attempt to insert the point into the QuadTree. It will recursively search until it finds the leaf node. If the leaf node is at capacity then it will try split the node. If the tree is at max depth then point will be stored in the leaf.
func (*QuadTree) Remove ¶
Remove attemps to remove a point from the QuadTree. It will recurse until the leaf node is found and then try to remove the point.
Source Files