CellTree2d#

class numba_celltree.CellTree2d(vertices: ndarray, faces: ndarray, fill_value: int, n_buckets: int = 4, cells_per_leaf: int = 2)[source]#

Bases: object

Construct a cell tree from 2D vertices and a faces indexing array.

Parameters:

  • vertices (ndarray of floats with shape (n_point, 2)) – Corner coordinates (x, y) of the cells.

  • faces (ndarray of integers with shape (n_face, n_max_vert)) – Index identifying for every face the indices of its corner nodes. If a face has less corner nodes than n_max_vert, its last indices should be equal to fill_value.

  • n_buckets (int, optional, default: 4) – The number of “buckets” used in tree construction. Must be higher or equal to 2. Values over 8 provide diminishing returns.

  • cells_per_leaf (int, optional, default: 2) – The number of cells in the leaf nodes of the cell tree. Can be set to only 1, but this doubles memory footprint for slightly faster lookup. Increase this to reduce memory usage at the cost of lookup performance.

  • fill_value (int, optional, default: -1) – Fill value marking empty nodes in faces.

compute_barycentric_weights(points: ndarray) → Tuple[ndarray, ndarray][source]#

Compute barycentric weights for points located inside of the grid.

Parameters:

points (ndarray of floats with shape (n_point, 2))

Returns:

  • tree_face_indices (ndarray of integers with shape (n_point,)) – For every point, the index of the face it falls in. Points not falling in any faces are marked with a value of -1.

  • barycentric_weights (ndarray of integers with shape (n_point, n_max_vert)) – For every point, the barycentric weights of the vertices of the face in which the point is located. For points not falling in any faces, the weight of all vertices is 0.

intersect_boxes(bbox_coords: ndarray) → Tuple[ndarray, ndarray, ndarray][source]#

Find the index of a box intersecting with a face, and the area of intersection.

Parameters:

bbox_coords (ndarray of floats with shape (n_box, 4)) – Every row containing (xmin, xmax, ymin, ymax).

Returns:

  • bbox_indices (ndarray of integers with shape (n_found,)) – Indices of the bounding box.

  • tree_face_indices (ndarray of integers with shape (n_found,)) – Indices of the tree faces.

  • area (ndarray of floats with shape (n_found,)) – Area of intersection between the two intersecting faces.

intersect_edges(edge_coords: ndarray) → Tuple[ndarray, ndarray, ndarray][source]#

Find the index of a face intersecting with an edge.

Parameters:

edge_coords (ndarray of floats with shape (n_edge, 2, 2)) – Every row containing ((x0, y0), (x1, y1)).

Returns:

  • edge_indices (ndarray of integers with shape (n_found,)) – Indices of the bounding box.

  • tree_face_indices (ndarray of integers with shape (n_found,)) – Indices of the face.

  • intersection_edges (ndarray of floats with shape (n_found, 2, 2)) – The resulting intersected edges, every row containing: ((x0, y0), (x1, y1)). The length of each intersected edge can be computed with: np.linalg.norm(intersections[:, 1] - intersections[:, 0], axis=1).

intersect_faces(vertices: ndarray, faces: ndarray, fill_value: int) → Tuple[ndarray, ndarray, ndarray][source]#

Find the index of a face intersecting with another face, and the area of intersection.

Parameters:

  • vertices (ndarray of floats with shape (n_point, 2)) – Corner coordinates (x, y) of the cells.

  • faces (ndarray of integers with shape (n_face, n_max_vert)) – Index identifying for every face the indices of its corner nodes. If a face has less corner nodes than n_max_vert, its last indices should be equal to fill_value.

  • fill_value (int, optional, default: -1) – Fill value marking empty nodes in faces.

Returns:

  • face_indices (ndarray of integers with shape (n_found,)) – Indices of the faces.

  • tree_face_indices (ndarray of integers with shape (n_found,)) – Indices of the tree faces.

  • area (ndarray of floats with shape (n_found,)) – Area of intersection between the two intersecting faces.

locate_boxes(bbox_coords: ndarray) → Tuple[ndarray, ndarray][source]#

Find the index of a face intersecting with a bounding box.

Parameters:

bbox_coords (ndarray of floats with shape (n_box, 4)) – Every row containing (xmin, xmax, ymin, ymax).

Returns:

  • bbox_indices (ndarray of integers with shape (n_found,)) – Indices of the bounding box.

  • tree_face_indices (ndarray of integers with shape (n_found,)) – Indices of the face.

locate_faces(vertices: ndarray, faces: ndarray) → Tuple[ndarray, ndarray][source]#

Find the index of a face intersecting with another face.

Only sharing an edge also counts as an intersection, due to the use of the separating axis theorem to define intersection. The area of the overlap is zero in such a case.

Parameters:

  • vertices (ndarray of floats with shape (n_point, 2)) – Corner coordinates (x, y) of the cells.

  • faces (ndarray of integers with shape (n_face, n_max_vert)) – Index identifying for every face the indices of its corner nodes. If a face has less corner nodes than n_max_vert, its last indices should be equal to fill_value.

Returns:

  • face_indices (ndarray of integers with shape (n_found,)) – Indices of the faces.

  • tree_face_indices (ndarray of integers with shape (n_found,)) – Indices of the tree faces.

locate_points(points: ndarray) → ndarray[source]#

Find the index of a face that contains a point.

Points that are very close near an edge of a face will also be identified as falling within that face.

Parameters:

points (ndarray of floats with shape (n_point, 2))

Returns:

tree_face_indices – For every point, the index of the face it falls in. Points not falling in any faces are marked with a value of -1.

Return type:

ndarray of integers with shape (n_point,)

property node_bounds#

Return the bounds (xmin, xmax, ymin, ymax) for every node of the tree.

to_dict_of_lists()[source]#

Convert the tree structure to a dict of lists.

Such a dict can be ingested by e.g. NetworkX to produce visualize the tree structure.

Returns:

dict_of_lists – Contains for every node a list with its children.

Return type:

Dict[Int, List[Int]]

Examples

>>> import networkx
>>> from networkx.drawing.nx_pydot import graphviz_layout
>>> d = celltree.to_dict_of_lists()
>>> G = networkx.DiGraph(d)
>>> positions = graphviz_layout(G, prog="dot")
>>> networkx.draw(G, positions, with_labels=True)

Note that computing the graphviz layout may be quite slow!

validate_node_bounds() → ndarray[source]#

Traverse the tree. Check whether all children are contained in the bounding box.

For the leaf nodes, check whether the bounding boxes are contained.

Returns:

node_validity – For each node, whether all children are fully contained by its bounds.

Return type:

np.array of bool

Changelog#

[0.2.2 2024-10-15]#

Fixed#

  • CellTree2d.intersect_edges() could hang indefinitely due to a while loop with faulty logic in numba_celltree.algorithms.cohen_sutherland_line_box_clip(). This issue seems to appears when an edge vertex lies exactly on top of a bounding box vertex of the celltree. The logic has been updated and the while loop exits correctly now.

Changed#