Node3d<T>

[DebuggerDisplay("C:{ChildCount}, I:{ItemCount}, {NodeIndex}")] public sealed class Node3d<T>

Basic node in a Tree3d structure. Nodes in tree structures maintain a local region and either a list of content indices or a list of up to 8 child nodes.

Type parameters:

Constructors

Node3d

public Node3d(Coordinates3d<T> converter, BoundingBox region, int limit)

Create a new spatial tree root.

Parameters:

converter (Coordinates3d<T>)	Converter delegate.
region (BoundingBox)	Bounding box for this node. The region should be big enough to contain all items you're going to insert.
limit (int)	Node subdivision limit.

Node3d

public Node3d(Coordinates3d<T> converter, BoundingBox region)

Create a new spatial tree root.

Parameters:

converter (Coordinates3d<T>)	Converter delegate.
region (BoundingBox)	Bounding box for this node. The region should be big enough to contain all items you're going to insert.

Properties

Center

public Point3d Center { get; }

Gets the center of the spatial region of this node. If the node contains no children the center is always in the middle of the Region. If the node does contain child-nodes, the center may be anywhere within the region.

ChildCount

public int ChildCount { get; }

Gets the number of defined child nodes. Leaf nodes have no children. Root and twig nodes can have anywhere between 1 and 8 children.

ChildNode

public Node3d<T> ChildNode[int index] { get; }

Gets the child node at the given index.

Parameters:

index (int)

Index of child node to retrieve. Valid indices are from 0 to 7 inclusive.

ContentAverage

public Point3d ContentAverage { get; }

Returns the average coordinate of all items in this node. If this node does not contain any items, Point3d.Unset is returned.

ContentBoundingBox

public BoundingBox ContentBoundingBox { get; }

Returns the boundingbox of all items in this node. If this node does not contain any items, BoundingBox.Empty is returned.

IndicesLocal

public List<int> IndicesLocal { get; }

Gets the list of item indices that are contained within this node.

IndicesRecursive

public List<int> IndicesRecursive { get; }

Gets the list of item indices that are contained within this node and any child nodes.

IsLeaf

public bool IsLeaf { get; }

Gets whether this node is a leaf node. Leaf nodes have no child nodes.

IsMutable

public bool IsMutable { get; }

Gets whether this tree is mutable. You can only add items to mutable trees. We don't recommend removing items from unmutable trees, though that shouldn't necessarily lead to problems. Trees become unmutable after a call to ShrinkRegions(), CollapseNodes() or OptimizeTree().

IsRoot

public bool IsRoot { get; }

Gets whether this node is a root node. Root nodes have no parent node and depth zero.

IsTwig

public bool IsTwig { get; }

Gets whether this node is a twig node. Twig nodes have both parents and at least one child.

ItemCount

public int ItemCount { get; }

Gets the total number of items stored directly in this node.

ItemsGlobal

public List<T> ItemsGlobal { get; }

Gets the list of all items stored inside this entire tree. Do not modify this collection unless you know what you are doing.

ItemsLocal

public List<T> ItemsLocal { get; }

Gets a list of all the items stored directly in this node. This list is constructed every time you access this property, so keep it down to a minimum.

Limit

public int Limit { get; }

Gets the subdivision limit for this tree. This limit can only be set once when you create a new tree. It is fixed forever after.

MemoryConsumption

public long MemoryConsumption { get; }

Gets the estimated memory consumption of the (sub)tree structure. Items inside the global list are not included in this estimate.

NextNode

public Node3d<T> NextNode { get; }

Gets the logical neighbour to the right of this node. There is no spatial relationships between logical neighbours, this is purely an iteration aid.

NodeDepth

public int NodeDepth { get; }

Gets the recursive depth of this node. The tree root is at depth zero. The first subdivision is at depth one, and so on and so forth.

ParentNode

public Node3d<T> ParentNode { get; }

Gets the immediate parent of this node. Root nodes have no parent.

Region

public BoundingBox Region { get; }

Gets the spatial region of this node.

RootNode

public Node3d<T> RootNode { get; }

Gets the ultimate root node for this tree.

WeightedSubdivision

public bool WeightedSubdivision { get; set; }

Gets or sets whether subdivision is weighted based on content averages. Setting this value will only affect future subdivisions, not existing ones.

Methods

Add

public void Add(T item)

Insert another item into the tree. The item should be within the region of this node.

Parameters:

item (T)

Item to insert.

AddRange

public void AddRange(IEnumerable<T> items)

Insert a collection of items into the tree. The items should all be within the region of this node.

Parameters:

items (IEnumerable<T>)

Items to add.

AddToRhinoDocument

public void AddToRhinoDocument(RhinoDoc doc)

Parameters:

doc (RhinoDoc)

ChildIndex

protected int ChildIndex(double x, double y, double z)

Find the child index that is associated with a given coordinate.

Parameters:

x (double)
y (double)
z (double)

Returns: Index of twig that would contain the point.

ChildRegion

protected BoundingBox ChildRegion(int index)

Compute the region of a specific child node.

Parameters:

index (int)

Index of twig to compute.

CollapseNodes

public Node3d<T> CollapseNodes()

Collapse the (sub)tree rooted at this node. Collapsing happens when a node only has a single child, in which case the child usurps the position previously held by the parent. Do not collapse a (sub)tree if you still plan to add items later.

Returns: The new root for this (sub)tree. May well be an instance of this node if it cannot be collapsed.

FurthestItem

public Index3d<T> FurthestItem(double x, double y, double z, double minimumDistance, double maximumDistance)

Find the furtest item.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.
minimumDistance (double)	Minimum distance for furtest item. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for furtest item. Items further than maximumDistance will be ignored.

Returns: The index of the furtest item or null if no furtest item could be found.

FurthestItem

public Index3d<T> FurthestItem(double x, double y, double z)

Find the furtest item.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.

Returns: The index of the furtest item or null if no furtest item could be found.

FurthestItem

public Index3d<T> FurthestItem(Point3d locus, double minimumDistance, double maximumDistance)

Find the furtest item.

Parameters:

locus (Point3d)	Location to search from.
minimumDistance (double)	Minimum distance for furtest item. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for furtest item. Items further than maximumDistance will be ignored.

Returns: The index of the furtest item or null if no furtest item could be found.

FurthestItem

public Index3d<T> FurthestItem(Point3d locus)

Find the furtest item.

Parameters:

locus (Point3d)

Location to search from.

Returns: The index of the furtest item or null if no furtest item could be found.

FurthestItem

public Index3d<T> FurthestItem(T locus, double minimumDistance, double maximumDistance)

Find the furtest item.

Parameters:

locus (T)	Location to search from.
minimumDistance (double)	Minimum distance for furtest item. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for furtest item. Items further than maximumDistance will be ignored.

Returns: The index of the furtest item or null if no furtest item could be found.

FurthestItem

public Index3d<T> FurthestItem(T locus)

Find the furtest item.

Parameters:

locus (T)

Location to search from.

Returns: The index of the furtest item or null if no furtest item could be found.

InsertIndexRecursive

protected void InsertIndexRecursive(int index)

Adust this node and all child nodes for the insertion of a single index.

Parameters:

index (int)

Index to insert.

NearestItem

public Index3d<T> NearestItem(double x, double y, double z, double minimumDistance, double maximumDistance)

Find the nearest item.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.
minimumDistance (double)	Minimum distance for nearest item. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for nearest item. Items further than maximumDistance will be ignored.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItem

public Index3d<T> NearestItem(double x, double y, double z, Validation3d<T> validationDelegate)

Find the nearest item using custom validation criteria.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.
validationDelegate (Validation3d<T>)	Item validation delegate.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItem

public Index3d<T> NearestItem(double x, double y, double z)

Find the nearest item.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItem

public Index3d<T> NearestItem(Point3d locus, double minimumDistance, double maximumDistance)

Find the nearest item.

Parameters:

locus (Point3d)	Location to search from.
minimumDistance (double)	Minimum distance for nearest item. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for nearest item. Items further than maximumDistance will be ignored.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItem

public Index3d<T> NearestItem(Point3d locus)

Find the nearest item.

Parameters:

locus (Point3d)

Location to search from.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItem

public Index3d<T> NearestItem(T locus, double minimumDistance, double maximumDistance)

Find the nearest item.

Parameters:

locus (T)	Location to search from.
minimumDistance (double)	Minimum distance for nearest item. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for nearest item. Items further than maximumDistance will be ignored.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItem

public Index3d<T> NearestItem(T locus)

Find the nearest item.

Parameters:

locus (T)

Location to search from.

Returns: The index of the nearest item or null if no nearest item could be found.

NearestItems

public List<Index3d<T>> NearestItems(double x, double y, double z, int groupSize, double minimumDistance, double maximumDistance)

Find the N nearest items.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.
groupSize (int)	Number of nearest items to return.
minimumDistance (double)	Minimum distance for nearest items. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for nearest items. Items further than maximumDistance will be ignored.

Returns: A list of nearest items, sorted from nearest to furthest.

NearestItems

public List<Index3d<T>> NearestItems(double x, double y, double z, int groupSize)

Find the N nearest items.

Parameters:

x (double)	x coordinate to search from.
y (double)	y coordinate to search from.
z (double)	z coordinate to search from.
groupSize (int)	Number of nearest items to return.

Returns: A list of nearest items, sorted from nearest to furthest.

NearestItems

public List<Index3d<T>> NearestItems(T locus, int groupSize, double minimumDistance, double maximumDistance)

Find the N nearest items.

Parameters:

locus (T)	Search locus.
groupSize (int)	Number of nearest items to return.
minimumDistance (double)	Minimum distance for nearest items. Items closer than minimumDistance will be ignored.
maximumDistance (double)	Maximum distance for nearest items. Items further than maximumDistance will be ignored.

Returns: A list of nearest items, sorted from nearest to furthest.

NearestItems

public List<Index3d<T>> NearestItems(T locus, int groupSize)

Find the N nearest items.

Parameters:

locus (T)	Search locus.
groupSize (int)	Number of nearest items to return.

Returns: A list of nearest items, sorted from nearest to furthest.

OptimizeTree

public Node3d<T> OptimizeTree()

Optimize this tree for fast searches. Do not call this method if you still plan to add items in the future. You can no longer modify this tree once it has been optimized.

Returns: The new root of the optimized tree. If the root could not be optimized an instance of this node will be returned.

Rebuild

protected void Rebuild()

Aggregate all points in this node and re-build it.

Remove

public void Remove(Index3d<T> index)

Remove the item with the given index from the entire tree. It doesn't matter on which node you call this function, it is a tree-wide operation.

Parameters:

index (Index3d<T>)

Index of item to remove.

Remove

public void Remove(int index)

Remove the item with the given index from the entire tree. It doesn't matter on which node you call this function, it is a tree-wide operation.

Parameters:

index (int)

Index of item to remove.

RemoveIndexRecursive

protected void RemoveIndexRecursive(int index)

Adjust this node and all child nodes to cater for the removal of a single index. If a node contains the specified index, that item will be removed entirely.

Parameters:

index (int)

Index to remove.

ShrinkRegions

public void ShrinkRegions()

Shrink the region for this node and all child nodes. Do not use this method if you intend to add more items later as it creates spatial gaps in the tree structure. You can shrink nodes if you're done adding items and want to start searching the tree.

SubTree

public IEnumerator<Node3d<T>> SubTree(bool omitStructuralNodes)

Gets an iterator for all nodes in this (sub)tree.

Parameters:

omitStructuralNodes (bool)

If true, nodes that contain other nodes will be skipped. Only nodes containing items will be included.

TrimExcess

public void TrimExcess()

Trim the excess space on all index lists. You can call this method to reduce memory usage. It will not modify the tree in any functional way.