treenode

Documentation

Overview

Package treenode .

Package treenode .

Package treenode .

Package treenode provides the implementation of a tree node used in spatial indexing.

Index

• type D2
  • func NewD2() *D2
  • func (d *D2) ChildrenCount() int
  • func (d *D2) Clear()
  • func (d *D2) Contains(n *TreeNode, spatial siface.ISpatial) bool
  • func (d *D2) Divide(parent *TreeNode, depth int)
  • func (d *D2) GetChild(index int) *TreeNode
  • func (d *D2) Intersects(n *TreeNode, bound bounds.Bound) bool
• type D3
  • func NewD3() *D3
  • func (d *D3) ChildrenCount() int
  • func (d *D3) Clear()
  • func (d *D3) Contains(n *TreeNode, spatial siface.ISpatial) bool
  • func (d *D3) Divide(parent *TreeNode, depth int)
  • func (d *D3) GetChild(index int) *TreeNode
  • func (d *D3) Intersects(n *TreeNode, bound bounds.Bound) bool
• type IDimensionNode
• type TreeNode
  • func NewTreeNode(dim consts.Dim, parent *TreeNode, bound bounds.Bound, ...) (*TreeNode, error)
  • func (n *TreeNode) Add(spatial siface.ISpatial) bool
  • func (n *TreeNode) Bound() bounds.Bound
  • func (n *TreeNode) Capacity() int
  • func (n *TreeNode) Children() IDimensionNode
  • func (n *TreeNode) Clear()
  • func (n *TreeNode) ClearChildren()
  • func (n *TreeNode) Contains(spatial siface.ISpatial) bool
  • func (n *TreeNode) Depth() int
  • func (n *TreeNode) DivideIf() bool
  • func (n *TreeNode) FindEntities(center geo.Vec3Int, radius float32, ...) []siface.ISpatial
  • func (n *TreeNode) FindEntitiesInBound(bound bounds.Bound, radius float32, ...) []siface.ISpatial
  • func (n *TreeNode) GetEntityList() *list.List
  • func (n *TreeNode) Index() int
  • func (n *TreeNode) Intersects(bound bounds.Bound) bool
  • func (n *TreeNode) IsLeaf() bool
  • func (n *TreeNode) MaxDepth() int
  • func (n *TreeNode) MergeIf() bool
  • func (n *TreeNode) Parent() *TreeNode
  • func (n *TreeNode) Range(f func(n *TreeNode) bool)
  • func (n *TreeNode) RangeEntities(f func(entity siface.ISpatial) bool)
  • func (n *TreeNode) Remove(spatialId int64, merge ...bool) bool
  • func (n *TreeNode) Size() int

Types

type D2

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

D2 .

func NewD2

func NewD2() *D2

NewD2 .

func (*D2) ChildrenCount

func (d *D2) ChildrenCount() int

ChildrenCount returns the number of children.

func (*D2) Clear

func (d *D2) Clear()

Clear removes all children.

func (*D2) Contains

func (d *D2) Contains(n *TreeNode, spatial siface.ISpatial) bool

Contains checks if the spatial entity is within the bounds of the node.

Parameters: - spatial: The spatial entity to check.

Returns: - true if the entity is within the bounds, false otherwise.

func (*D2) Divide

func (d *D2) Divide(parent *TreeNode, depth int)

Divide the node into 4 children and move entities to children.

func (*D2) GetChild

func (d *D2) GetChild(index int) *TreeNode

GetChild returns the child at the specified index.

func (*D2) Intersects

func (d *D2) Intersects(n *TreeNode, bound bounds.Bound) bool

Intersects checks if the bound intersects with the node.

type D3

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

D3 .

func NewD3

func NewD3() *D3

NewD3 .

func (*D3) ChildrenCount

func (d *D3) ChildrenCount() int

ChildrenCount return the number of children.

func (*D3) Clear

func (d *D3) Clear()

Clear the children.

func (*D3) Contains

func (d *D3) Contains(n *TreeNode, spatial siface.ISpatial) bool

Contains checks if the spatial entity is within the bounds of the node.

Parameters: - spatial: The spatial entity to check.

Returns: - true if the entity is within the bounds, false otherwise.

func (*D3) Divide

func (d *D3) Divide(parent *TreeNode, depth int)

Divide the node into 8 children and move entities to children.

func (*D3) GetChild

func (d *D3) GetChild(index int) *TreeNode

GetChild return the child at the given index.

func (*D3) Intersects

func (d *D3) Intersects(n *TreeNode, bound bounds.Bound) bool

Intersects checks if the bound intersects with the node.

type IDimensionNode

type IDimensionNode interface {
	Divide(parent *TreeNode, depth int)
	ChildrenCount() int
	GetChild(index int) *TreeNode
	Clear()
	Contains(n *TreeNode, spatial siface.ISpatial) bool
	Intersects(n *TreeNode, bound bounds.Bound) bool
}

type TreeNode

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

TreeNode is a node in the tree.

Not thread-safe, only works in a single thread(goroutine).

func NewTreeNode

func NewTreeNode(dim consts.Dim, parent *TreeNode, bound bounds.Bound, index, depth, maxDepth, capacity int) (*TreeNode, error)

NewTreeNode creates a new tree node.

Parameters: - dim: The dimension of the tree (e.g., 2D, 3D). - bound: The spatial boundaries of the node. - capacity: The maximum number of entities that the node can hold.

Returns: - A pointer to the newly created TreeNode.

func (*TreeNode) Add

func (n *TreeNode) Add(spatial siface.ISpatial) bool

Add adds a spatial entity to the node.

Parameters: - spatial: The spatial entity to add.

Returns: - true if the entity was added successfully, false otherwise.

func (*TreeNode) Bound

func (n *TreeNode) Bound() bounds.Bound

Bound returns the spatial boundaries of the node.

func (*TreeNode) Capacity

func (n *TreeNode) Capacity() int

Capacity returns the maximum number of entities the node can hold.

func (*TreeNode) Children

func (n *TreeNode) Children() IDimensionNode

Children returns the children of the node.

func (*TreeNode) Clear

func (n *TreeNode) Clear()

Clear removes all entities from the node.

func (*TreeNode) ClearChildren

func (n *TreeNode) ClearChildren()

func (*TreeNode) Contains

func (n *TreeNode) Contains(spatial siface.ISpatial) bool

Contains checks if the spatial entity is within the bounds of the node.

Parameters: - spatial: The spatial entity to check.

Returns: - true if the entity is within the bounds, false otherwise.

func (*TreeNode) Depth

func (n *TreeNode) Depth() int

func (*TreeNode) DivideIf

func (n *TreeNode) DivideIf() bool

DivideIf divides the node into 8 children if the number of entities exceeds the capacity. if the depth of the node exceeds the maximum depth, the node will not be divided.

Returns: - true if the node was divided, false otherwise.

func (*TreeNode) FindEntities

func (n *TreeNode) FindEntities(center geo.Vec3Int, radius float32, filters ...func(entity siface.ISpatial) bool) []siface.ISpatial

FindEntities finds entities within a radius of a center point.

func (*TreeNode) FindEntitiesInBound

func (n *TreeNode) FindEntitiesInBound(bound bounds.Bound, radius float32, filters ...func(entity siface.ISpatial) bool) []siface.ISpatial

FindEntitiesInBound finds entities within a bound.

func (*TreeNode) GetEntityList

func (n *TreeNode) GetEntityList() *list.List

GetEntityList returns the list of entities in the node.

Returns: - A pointer to the list of entities.

func (*TreeNode) Index

func (n *TreeNode) Index() int

func (*TreeNode) Intersects

func (n *TreeNode) Intersects(bound bounds.Bound) bool

Intersects checks if the bound intersects with the node.

func (*TreeNode) IsLeaf

func (n *TreeNode) IsLeaf() bool

IsLeaf checks if the node is a leaf node.

func (*TreeNode) MaxDepth

func (n *TreeNode) MaxDepth() int

MaxDepth returns the maximum depth of the tree.

func (*TreeNode) MergeIf

func (n *TreeNode) MergeIf() bool

MergeIf merges the node with its children if the number of entities in the node is less than the capacity. not suggested to use this method, it's not efficient.

func (*TreeNode) Parent

func (n *TreeNode) Parent() *TreeNode

Parent returns the parent node.

func (*TreeNode) Range

func (n *TreeNode) Range(f func(n *TreeNode) bool)

Range .

func (*TreeNode) RangeEntities

func (n *TreeNode) RangeEntities(f func(entity siface.ISpatial) bool)

RangeEntities ranges the entities in the node.

func (*TreeNode) Remove

func (n *TreeNode) Remove(spatialId int64, merge ...bool) bool

Remove removes a spatial entity from the node by its ID.

Parameters: - spatialId: The ID of the spatial entity to remove. - merge: Whether to merge the node with its children after removing the entity.

Returns: - true if the entity was removed successfully, false otherwise.

func (*TreeNode) Size

func (n *TreeNode) Size() int

Size returns the number of entities in the node.