Bvh2d<'T> (Euclid.BVH)

Bvh2d<'T> Type

Namespace: Euclid
Assembly: Euclid.BVH.dll
Base Type: obj

A generic static Bounding Volume Hierarchy (BVH) over any 2D items,
 built from Euclid axis aligned bounding rectangles (BRect).
 The tree is built once from an array of items plus a function that returns the bounding rectangle
 of each item, and is then immutable.
 This is a genuinely two dimensional tree: nodes store a BRect, not a BBox with a zero Z range,
 so it needs a third less memory and does a third less work per distance test than the 3D Bvh.
 It is well suited to unevenly distributed input because the tree adapts to the actual
 bounding rectangles of the items instead of subdividing space uniformly (as a quadtree or grid would).
 All queries come in two flavors: rectangle based, where the distance between two items is measured
 as the distance between their bounding rectangles, and exact, where a distance function for the
 actual items is supplied. The bounding rectangle distance is always a valid lower bound of the
 exact distance, so it is used for branch and bound pruning in both cases.

Instance members

Static members

Static member	Description
`Bvh2d.DefaultLeafSize` Full Usage: `Bvh2d.DefaultLeafSize` Returns: `int`	The default maximum amount of items per leaf node. Returns: `int`
`Bvh2d.create (items, getRect, ?leafSize)` Full Usage: `Bvh2d.create (items, getRect, ?leafSize)` Parameters: items : `'T seq` - The items to build the tree from. They are enumerated and copied to an array at build time. getRect : `'T -> BRect` - A function returning the axis aligned bounding rectangle of an item. It is called once per item at build time. ?leafSize : `int` - The maximum amount of items per leaf node. Optional, 4 by default. Returns: `Bvh2d<'T>` A new immutable Bvh2d.	Builds a Bvh2d from the given sequence of items. items : `'T seq` The items to build the tree from. They are enumerated and copied to an array at build time. getRect : `'T -> BRect` A function returning the axis aligned bounding rectangle of an item. It is called once per item at build time. ?leafSize : `int` The maximum amount of items per leaf node. Optional, 4 by default. Returns: `Bvh2d<'T>` A new immutable Bvh2d.
`Bvh2d.create (items, getRect, ?leafSize)` Full Usage: `Bvh2d.create (items, getRect, ?leafSize)` Parameters: items : `ResizeArray<'T>` - The items to build the tree from. They are copied to an array at build time. getRect : `'T -> BRect` - A function returning the axis aligned bounding rectangle of an item. It is called once per item at build time. ?leafSize : `int` - The maximum amount of items per leaf node. Optional, 4 by default. Returns: `Bvh2d<'T>` A new immutable Bvh2d.	Builds a Bvh2d from the given resizable array of items. items : `ResizeArray<'T>` The items to build the tree from. They are copied to an array at build time. getRect : `'T -> BRect` A function returning the axis aligned bounding rectangle of an item. It is called once per item at build time. ?leafSize : `int` The maximum amount of items per leaf node. Optional, 4 by default. Returns: `Bvh2d<'T>` A new immutable Bvh2d.
`Bvh2d.create (items, getRect, ?leafSize)` Full Usage: `Bvh2d.create (items, getRect, ?leafSize)` Parameters: items : `'T[]` - The items to build the tree from. The array is referenced, not copied. Do not mutate it afterwards. getRect : `'T -> BRect` - A function returning the axis aligned bounding rectangle of an item. It is called once per item at build time. ?leafSize : `int` - The maximum amount of items per leaf node. Optional, 4 by default. Returns: `Bvh2d<'T>` A new immutable Bvh2d.	Builds a Bvh2d from the given items. The tree is built top-down by splitting at the median of the item-rectangle centers along the longer axis of the current bounding rectangle. items : `'T[]` The items to build the tree from. The array is referenced, not copied. Do not mutate it afterwards. getRect : `'T -> BRect` A function returning the axis aligned bounding rectangle of an item. It is called once per item at build time. ?leafSize : `int` The maximum amount of items per leaf node. Optional, 4 by default. Returns: `Bvh2d<'T>` A new immutable Bvh2d.

Instance member	Description
`this.ClosePairs` Full Usage: `this.ClosePairs` Parameters: maxDistance : `float` - The maximum distance between two item rectangles for the pair to be reported. Returns: `ResizeArray<BvhPair>` A ResizeArray of BvhPair, each with IdxA less than IdxB. The order of the pairs is not defined.	Finds all pairs of items whose bounding rectangles are closer to each other than the given maximum distance. The distance between two rectangles is 0.0 if they overlap or touch, so a maxDistance of 0.0 finds all pairs of overlapping or touching rectangles. maxDistance : `float` The maximum distance between two item rectangles for the pair to be reported. Returns: `ResizeArray<BvhPair>` A ResizeArray of BvhPair, each with IdxA less than IdxB. The order of the pairs is not defined.
`this.ClosePairs` Full Usage: `this.ClosePairs` Parameters: maxDistance : `float` - The maximum distance between two items for the pair to be reported. sqDistance : `'T -> 'T -> float` - Returns the exact squared distance between two items. Returns: `ResizeArray<BvhPair>` A ResizeArray of BvhPair, each with IdxA less than IdxB. The order of the pairs is not defined.	Finds all pairs of items that are closer to each other than the given maximum distance, measured with the given exact squared distance function. Uses a dual tree traversal: pairs of subtrees whose bounding rectangles are farther apart than the maximum distance are skipped entirely. maxDistance : `float` The maximum distance between two items for the pair to be reported. sqDistance : `'T -> 'T -> float` Returns the exact squared distance between two items. Returns: `ResizeArray<BvhPair>` A ResizeArray of BvhPair, each with IdxA less than IdxB. The order of the pairs is not defined.
`this.ClosestItem` Full Usage: `this.ClosestItem` Parameters: pt : `Pt` - The 2D point to search the closest item for. sqDistanceTo : `'T -> float` - Returns the exact squared distance from the query point to an item. ?skipIdx : `int` - An index into the input items array to exclude from the search. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the closest item in the input array and the distance to it.	Finds the item in the tree closest to the given query point. The distance to an item is measured to the exact geometry via the given squared distance function, while the item bounding rectangles provide lower bounds for branch and bound pruning: subtrees whose bounding rectangle is farther away from the point than the best distance found so far are skipped. pt : `Pt` The 2D point to search the closest item for. sqDistanceTo : `'T -> float` Returns the exact squared distance from the query point to an item. ?skipIdx : `int` An index into the input items array to exclude from the search. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the closest item in the input array and the distance to it.
`this.ClosestItem` Full Usage: `this.ClosestItem` Parameters: queryRect : `BRect` - The axis aligned bounding rectangle of the query geometry. It must fully contain the query geometry that sqDistanceTo measures from, otherwise subtrees may be pruned incorrectly. sqDistanceTo : `'T -> float` - Returns the exact squared distance from the query geometry to an item. ?skipIdx : `int` - An index into the input items array to exclude from the search. Use this to find the nearest neighbor of an item that is part of the tree itself. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the closest item in the input array and the distance to it.	Finds the item in the tree closest to the given query bounding rectangle. The distance to an item is measured to the exact geometry via the given squared distance function, while the query rectangle and the item rectangles provide lower bounds for branch and bound pruning: subtrees whose bounding rectangle is farther away from the query rectangle than the best distance found so far are skipped. queryRect : `BRect` The axis aligned bounding rectangle of the query geometry. It must fully contain the query geometry that sqDistanceTo measures from, otherwise subtrees may be pruned incorrectly. sqDistanceTo : `'T -> float` Returns the exact squared distance from the query geometry to an item. ?skipIdx : `int` An index into the input items array to exclude from the search. Use this to find the nearest neighbor of an item that is part of the tree itself. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the closest item in the input array and the distance to it.
`this.ClosestPair` Full Usage: `this.ClosestPair` Returns: `BvhPair` A BvhPair with the indices of the two items and the distance between their rectangles.	Finds the pair of items whose bounding rectangles are closest to each other. The distance between two rectangles is 0.0 if they overlap or touch. Returns: `BvhPair` A BvhPair with the indices of the two items and the distance between their rectangles.
`this.ClosestPair` Full Usage: `this.ClosestPair` Parameters: sqDistance : `'T -> 'T -> float` - Returns the exact squared distance between two items. Returns: `BvhPair` A BvhPair with the indices of the two closest items and their distance.	Finds the pair of closest items among all items in the tree, measured with the given exact squared distance function. For every item the nearest neighbor is searched with branch and bound pruning on the bounding rectangles. sqDistance : `'T -> 'T -> float` Returns the exact squared distance between two items. Returns: `BvhPair` A BvhPair with the indices of the two closest items and their distance.
`this.ClosestRect` Full Usage: `this.ClosestRect` Parameters: pt : `Pt` - The 2D point to search the closest item rectangle for. ?skipIdx : `int` - An index into the input items array to exclude from the search. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the item with the closest bounding rectangle and the distance from the point to that rectangle.	Finds the item in the tree whose bounding rectangle is closest to the given query point. The distance between a point and a rectangle is 0.0 if the point is inside or on the rectangle. pt : `Pt` The 2D point to search the closest item rectangle for. ?skipIdx : `int` An index into the input items array to exclude from the search. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the item with the closest bounding rectangle and the distance from the point to that rectangle.
`this.ClosestRect` Full Usage: `this.ClosestRect` Parameters: queryRect : `BRect` - The axis aligned bounding rectangle to search the closest item rectangle for. ?skipIdx : `int` - An index into the input items array to exclude from the search. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the item with the closest bounding rectangle and the distance between the rectangles.	Finds the item in the tree whose bounding rectangle is closest to the given query rectangle. The distance between two rectangles is 0.0 if they overlap or touch. queryRect : `BRect` The axis aligned bounding rectangle to search the closest item rectangle for. ?skipIdx : `int` An index into the input items array to exclude from the search. Optional, -1 (skip nothing) by default. Returns: `int * float` The index of the item with the closest bounding rectangle and the distance between the rectangles.
`this.Count` Full Usage: `this.Count` Returns: `int`	The count of items in this Bvh2d. Returns: `int`
`this.Items` Full Usage: `this.Items` Returns: `IList<'T>`	The input items this Bvh2d was built from. Do not mutate this array. Returns: `IList<'T>`
`this.ItemsInRect` Full Usage: `this.ItemsInRect` Parameters: rect : `BRect` - The axis aligned bounding rectangle to search in. ?tolerance : `float` - The tolerance distance around the rectangle. Optional, 0.0 by default. Returns: `ResizeArray<int>` A ResizeArray of the indices of the found items in the input array.	Finds the indices of all items whose bounding rectangle is closer to the given axis aligned bounding rectangle than the given tolerance. rect : `BRect` The axis aligned bounding rectangle to search in. ?tolerance : `float` The tolerance distance around the rectangle. Optional, 0.0 by default. Returns: `ResizeArray<int>` A ResizeArray of the indices of the found items in the input array.
`this.ItemsNearPoint` Full Usage: `this.ItemsNearPoint` Parameters: pt : `Pt` - The 2D point to search around. ?tolerance : `float` - The tolerance distance around the point. Optional, 0.0 by default. Returns: `ResizeArray<int>` A ResizeArray of the indices of the found items in the input array.	Finds the indices of all items whose bounding rectangle is closer to the given 2D point than the given tolerance. The distance between a point and a rectangle is 0.0 if the point is inside or on the rectangle. pt : `Pt` The 2D point to search around. ?tolerance : `float` The tolerance distance around the point. Optional, 0.0 by default. Returns: `ResizeArray<int>` A ResizeArray of the indices of the found items in the input array.
`this.NearestNeighbors` Full Usage: `this.NearestNeighbors` Returns: `BvhPair[]` An array of BvhPair. The entry at index i holds i as IdxA, the index of the item with the nearest bounding rectangle as IdxB and the distance between the rectangles.	For every item in the tree finds the item whose bounding rectangle is nearest to its own. The distance between two rectangles is 0.0 if they overlap or touch. Returns: `BvhPair[]` An array of BvhPair. The entry at index i holds i as IdxA, the index of the item with the nearest bounding rectangle as IdxB and the distance between the rectangles.
`this.NearestNeighbors` Full Usage: `this.NearestNeighbors` Parameters: sqDistance : `'T -> 'T -> float` - Returns the exact squared distance between two items. Returns: `BvhPair[]` An array of BvhPair. The entry at index i holds i as IdxA, the index of the nearest neighbor of item i as IdxB and the distance between them.	For every item in the tree finds its nearest neighbor item, measured with the given exact squared distance function. sqDistance : `'T -> 'T -> float` Returns the exact squared distance between two items. Returns: `BvhPair[]` An array of BvhPair. The entry at index i holds i as IdxA, the index of the nearest neighbor of item i as IdxB and the distance between them.
`this.NodeRectanglesByDepth` Full Usage: `this.NodeRectanglesByDepth` Returns: `BRect[][]`	The bounding rectangles of all tree nodes, grouped by their depth from the root. Returns: `BRect[][]`
`this.Rectangle` Full Usage: `this.Rectangle` Returns: `BRect`	The axis aligned bounding rectangle around all items in this Bvh2d. Returns: `BRect`
`this.Rects` Full Usage: `this.Rects` Returns: `BRect[]`	The bounding rectangle of each input item, in the same order as Items. Do not mutate this array. Returns: `BRect[]`