porepy.utils.adtree module
Module containing the implementation of an alternating digital tree (ADT) for 3D geometric searching and intersection problems.
See the following works: 10.1002/nme.1620310102 and 10.1201/9781420050349 section 14.
Let [a, b) be the interval that contains the points that we want to insert in a binary tree. We then divide the interval into two equal parts: all the points in the interval [a, (a+b)/2) will be inserted in the left subtree, while the points in the interval [(a+b)/2, b ) will be placed in the right subtree. The reasoning is then iterated to the next level for each subtree.
[0, 1) / / / [0, 0.5) [0.5, 1)
/ | | / | | / | | [0, 0.25) [0.25, 0.5) [0.5, 0.75) [0.75, 1)
When inserting the following nodes A = 0.1, B = 0.6, C = 0.7, D = 0.8, E = 0.2 and F = 0.1 in the tree, we get the following
A
/ / E B
/ / / / F -1 C D
The first element A is added as the root. The second element B check if its coordinate (in this case is a single value) is smaller than 0.5. If so, it goes on the left part of the tree starting from the root otherwise on the right part. Now, since B = 0.6 it goes on the right part. Now are with the node C, we need to check as before if its coordinate is smaller than 0.5 (so it goes on the left) or bigger than 0.5 (so it goes on the right). Since it is 0.7 it goes on the right and being already taken by B we need to go one level down. We check now if its coordinate is smaller (left) or bigger (right) than 0.75. Since it’s smaller we proceed on the left part and being empty we add it. The insertion is not related to the parent but to which level and coordinate a node has. For the multi-dimension case we alternate the dimension by each level, so first we check the abscissa (again with left and right decided as before) and then the ordinate and so on. We detail a bit more here in the sequel.
In the multi-dimensional case, the ADT is organized in the same way, but the subdivision takes place alternately for the various coordinates: if the structure must contain n-dimensional points, at the i-th level of the tree the subdivision is carried out with respect to the j-th coordinate, where j is the remainder of the i / n division. We immediately observe that the n-dimensional “points”, the structure contains true points in 2 or 3 dimensions, and rectangles or parallelepipeds, which can be represented by “points” in 4 and 6 dimensions, with the writing (xmin, ymin, zmin, xmax, ymax, zmax). Other geometrical objects are represented by their bounding box. To avoid floating point problems, all the “points” are rescaled in [0, 1].
A search in the tree gives a list of all possible nodes that may intersect the given one.
- class ADTNode(key, box)[source]
Bases:
objectSimple bookkeeping class that contains the basic information of a tree node.
- key
any key related to the node
- Type
Any
- box
the bounding box associated to the node
- Type
np.ndarray
- child
list of identification of right and left children, if a children is not present is marked as -1.
- Type
- class ADTree(tree_dim, phys_dim)[source]
Bases:
objectADT structure, it is possible to fill the tree by giving a PorePy grid and then search for possible intersections. The implementation does not include some features, like removing a node, that are not used so far. Possible extensions in the future.
- tree_dim
search dimension of the tree, typically (e.g., when a pp.Grid is given) the double of the phys_dim
- Type
- region_min
to scale the bounding box of all the elements in [0, 1]^phys_dim we need the minimum corner point of the all region
- Type
- delta
a parameter to scale and get all the bounding box of the elements in [0, 1]^phys_dim
- Type
- add_node(node)[source]
Add a new node to the tree. We traverse the tree as previously specified and assign the new node accordingly.
- Parameters
node (
ADTNode) – the new node to be added.- Return type
None
- from_grid(g, only_cells=None)[source]
Function that constructs the tree from a grid by adding one cell at a time.
- Parameters
g (
pp.Grid) – The grid to be used to construct the treeonly_cells (
np.ndarray, optional) – Consider only a portion of the cells due to some a-priori estimates of the searching elements.
- Return type
None
- search(node, tol=2.0e-6)[source]
Search all possible nodes in the tree that might intersect with the input node. The node is not added to the tree.
- Parameters
node (
ADTNode) – Input nodetol (
float, optional) – Geometrical tolerance to avoid floating point problems
- Returns
Sorted, by id, list of nodes id that might intersect the node
- Return type
nodes (np.ndarray)