# dolfinx.geometry

Methods for geometric searches and operations.

Functions

`bb_tree`(mesh, dim, *[, padding, entities]) | Create a bounding box tree for use in collision detection.
`compute_closest_entity`(tree, midpoint_tree, ...) | Compute closest mesh entity to a point.
`compute_colliding_cells`(mesh, candidates, x) | From a mesh, find which cells collide with a set of points.
`compute_collisions_points`(tree, x) | Compute collisions between points and leaf bounding boxes.
`compute_collisions_trees`(tree0, tree1) | Compute all collisions between two bounding box trees.
`compute_distance_gjk`(p, q) | Compute the distance between two convex bodies p and q, each defined by a set of points.
`create_midpoint_tree`(mesh, dim, entities) | Create a bounding box tree for the midpoints of a subset of entities.
`determine_point_ownership`(mesh, points, padding) | Build point ownership data for a mesh-points pair.
`squared_distance`(mesh, dim, entities, points) | Compute the squared distance between a point and a mesh entity.

Classes

`BoundingBoxTree`(tree) | Bounding box trees used in collision detection.
`PointOwnershipData`(ownership_data) | Convenience class for storing data related to the ownership of points.

class dolfinx.geometry.BoundingBoxTree(tree)

  Bases: `object`

  Bounding box trees used in collision detection.

  Wrap a C++ BoundingBoxTree.

  Note

  This initializer should not be used in user code. Use

    `bb_tree`.

  property bbox_coordinates: ndarray[tuple[Any, ...], dtype[float32]] | ndarray[tuple[Any, ...], dtype[float64]]

    Coordinates of lower and upper corners of bounding boxes.

    Note

    Rows 2*ibbox and 2*ibbox+1 correspond to the lower and upper corners of bounding box ibbox, respectively.

  create_global_tree(comm) → BoundingBoxTree
  get_bbox(i) → ndarray[tuple[Any, ...], dtype[floating]]

    Get lower and upper corners of the ith bounding box.

    Parameters:

      i – Index of the box.

    Returns:

      The ‘lower’ and ‘upper’ points of the bounding box. Shape is `(2, 3)`,

  property num_bboxes: int

    Number of bounding boxes.

class dolfinx.geometry.PointOwnershipData(ownership_data)

  Bases: `object`

  Convenience class for storing data related to the ownership of points.

  Wrap a C++ PointOwnershipData.

  property dest_cells: ndarray[tuple[Any, ...], dtype[int32]]

    Cell indices (local to process) where each entry of `dest_points` is located.

  property dest_owner: ndarray[tuple[Any, ...], dtype[int32]]

    Ranks that sent `dest_points` to current process.

  property dest_points: ndarray[tuple[Any, ...], dtype[floating]]

    Points owned by current rank.

  property src_owner: ndarray[tuple[Any, ...], dtype[int32]]

    Ranks owning each point sent into ownership determination for current process.

dolfinx.geometry.bb_tree(mesh: Mesh, dim: int, *, padding: float = 0.0, entities: npt.NDArray[np.int32] | None = None) → BoundingBoxTree

  Create a bounding box tree for use in collision detection.

  Parameters:

    - mesh – The mesh.

    - dim – Dimension of the mesh entities to build bounding box for.

    - padding – Padding for each bounding box.

    - entities – List of entity indices (local to process). If not supplied, all owned and ghosted entities are used.

  Returns:

    Bounding box tree.

dolfinx.geometry.compute_closest_entity(tree: BoundingBoxTree, midpoint_tree: BoundingBoxTree, mesh: Mesh, points: npt.NDArray[np.floating]) → npt.NDArray[np.int32]

  Compute closest mesh entity to a point.

  Parameters:

    - tree – bounding box tree for the entities.

    - midpoint_tree – A bounding box tree with the midpoints of all the mesh entities. This is used to accelerate the search.

    - mesh – The mesh.

    - points – The points to check for collision, `shape=(num_points,3)`.

  Returns:

    Mesh entity index for each point in `points`. Returns -1 for a point if the bounding box tree is empty.

dolfinx.geometry.compute_colliding_cells(mesh: Mesh, candidates: AdjacencyList, x: npt.NDArray[np.floating]) → AdjacencyList

  From a mesh, find which cells collide with a set of points.

  Parameters:

    - mesh – The mesh.

    - candidate_cells – Adjacency list of candidate colliding cells for the ith point in `x`.

    - points – The points to check for collision `shape=(num_points, 3)`,

  Returns:

    Adjacency list where the ith node is the list of entities that collide with the ith point.

dolfinx.geometry.compute_collisions_points(tree: BoundingBoxTree, x: ndarray[tuple[Any, ...], dtype[floating]]) → AdjacencyList

  Compute collisions between points and leaf bounding boxes.

  Bounding boxes can overlap, therefore points can collide with more than one box.

  Parameters:

    - tree – Bounding box tree.

    - x – Points (`shape=(num_points, 3)`).

  Returns:

    For each point, the bounding box leaves that collide with the point.

dolfinx.geometry.compute_collisions_trees(tree0: BoundingBoxTree, tree1: BoundingBoxTree) → ndarray[tuple[Any, ...], dtype[int32]]

  Compute all collisions between two bounding box trees.

  Parameters:

    - tree0 – First bounding box tree.

    - tree1 – Second bounding box tree.

  Returns:

    List of pairs of intersecting box indices from each tree. Shape is `(num_collisions, 2)`.

dolfinx.geometry.compute_distance_gjk(p: ndarray[tuple[Any, ...], dtype[floating]], q: ndarray[tuple[Any, ...], dtype[floating]]) → ndarray[tuple[Any, ...], dtype[floating]]

  Compute the distance between two convex bodies p and q, each defined by a set of points.

  Uses the Gilbert-Johnson-Keerthi (GJK) distance algorithm.

  Parameters:

    - p – Body 1 list of points (`shape=(num_points, gdim)`).

    - q – Body 2 list of points (`shape=(num_points, gdim)`).

  Returns:

    Shortest vector between the two bodies.

dolfinx.geometry.create_midpoint_tree(mesh: Mesh, dim: int, entities: npt.NDArray[np.int32]) → BoundingBoxTree

  Create a bounding box tree for the midpoints of a subset of entities.

  Parameters:

    - mesh – The mesh.

    - dim – Topological dimension of the entities.

    - entities – Indices of mesh entities to include.

  Returns:

    Bounding box tree for midpoints of cell entities.

dolfinx.geometry.determine_point_ownership(mesh: Mesh, points: npt.NDArray[np.floating], padding: float, cells: npt.NDArray[np.int32] | None = None) → PointOwnershipData

  Build point ownership data for a mesh-points pair.

  First, potential collisions are found by computing intersections between the bounding boxes of the cells and the set of points. Then, actual containment pairs are determined using the GJK algorithm.

  Parameters:

    - mesh – The mesh

    - points – Points to check for collision, `shape=(num_points, gdim)`

    - padding – Amount of absolute padding of bounding boxes of the mesh. Each bounding box of the mesh is padded with this amount, to increase the number of candidates, avoiding rounding errors in determining the owner of a point if the point is on the surface of a cell in the mesh.

    - cells – Cells to check for ownership If `None` then all cells are considered.

  Returns:

    Point ownership data

  Note

  `dest_owner` is sorted

  `src_owner` is -1 if no colliding process is found

  A large padding value will increase the run-time of the code

    by orders of magnitude. General advice is to use a padding on the scale of the cell size.

dolfinx.geometry.squared_distance(mesh: Mesh, dim: int, entities: npt.NDArray[np.int32], points: npt.NDArray[np.floating]) → npt.NDArray[np.floating]

  Compute the squared distance between a point and a mesh entity.

  The distance is computed between the ith input points and the ith input entity.

  Parameters:

    - mesh – Mesh containing the entities.

    - dim – Topological dimension of the mesh entities.

    - entities – Indices of the mesh entities (local to process).

    - points – Points to compute the shortest distance from (`shape=(num_points, 3)`).

  Returns:

    Squared shortest distance from `points[i]` to `entities[i]`.