# Geometry (`dolfinx::geometry`)

namespace dolfinx::geometry

Geometry data structures and algorithms.

Tools for geometric data structures and operations, e.g. searching.

Functions

xt::xtensor_fixed<double, xt::xshape<3>> compute_distance_gjk(const xt::xtensor<double, 2> &p, const xt::xtensor<double, 2> &q)

Calculate the distance between two convex bodies p and q, each defined by a set of points, using the Gilbert–Johnson–Keerthi (GJK) distance algorithm.

Parameters
• p[in] Body 1 list of points, shape (num_points, 3)

• q[in] Body 2 list of points, shape (num_points, 3)

Returns

shortest vector between bodies

BoundingBoxTree create_midpoint_tree(const mesh::Mesh &mesh, int tdim, const xtl::span<const std::int32_t> &entity_indices)

Create a bounding box tree for a subset of entities (local to process) based on the entity midpoints.

Parameters
• mesh[in] The mesh

• tdim[in] The topological dimension of the entity

• entity_indices[in] List of local entity indices

Returns

Bounding box tree for midpoints of mesh entities

std::vector<std::array<int, 2>> compute_collisions(const BoundingBoxTree &tree0, const BoundingBoxTree &tree1)

Compute all collisions between two BoundingBoxTrees (local to process)

Parameters
Returns

List of pairs of intersecting box indices from each tree

graph::AdjacencyList<std::int32_t> compute_collisions(const BoundingBoxTree &tree, const xt::xtensor<double, 2> &points)

Compute all collisions between bounding boxes and for a set of points.

Parameters
• tree[in] The bounding box tree

• points[in] The points (shape=(num_points, 3))

Returns

An adjacency list where the ith node corresponds to the bounding box leaves that contain the ith point

std::vector<std::int32_t> compute_closest_entity(const BoundingBoxTree &tree, const BoundingBoxTree &midpoint_tree, const mesh::Mesh &mesh, const xt::xtensor<double, 2> &points)

Compute closest mesh entity to a point.

Note

Returns index -1 if the bounding box tree is empty

Parameters
• tree[in] The bounding box tree for the entities

• midpoint_tree[in] A bounding box tree with the midpoints of all the mesh entities. This is used to accelerate the search

• mesh[in] The mesh

• points[in] The set of points (shape=(num_points, 3))

Returns

Index of the closest mesh entity to a point. The ith entry is the index of the closest entity to the ith input point.

double compute_squared_distance_bbox(const xt::xtensor_fixed<double, xt::xshape<2, 3>> &b, const xt::xtensor_fixed<double, xt::xshape<3>> &x)

Compute squared distance between point and bounding box.

Parameters
• b[in] Bounding box coordinates

• x[in] A point

Returns

The shortest distance between the bounding box `b` and the point `x`. Returns zero if `x` is inside box.

xt::xtensor<double, 2> shortest_vector(const mesh::Mesh &mesh, int dim, const xtl::span<const std::int32_t> &entities, const xt::xtensor<double, 2> &points)

Compute the shortest vector from a mesh entity to a point.

Parameters
• mesh[in] The mesh

• dim[in] The topological dimension of the mesh entity

• entities[in] The list of entities (local to process)

• points[in] The set of points (shape=(num_points, 3))

Returns

An array of vectors where the ith row is the shortest vector from the ith entity and the ith point

xt::xtensor<double, 1> squared_distance(const mesh::Mesh &mesh, int dim, const xtl::span<const std::int32_t> &entities, const xt::xtensor<double, 2> &points)

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.

Note

Uses the GJK algorithm, see geometry::compute_distance_gjk for details.

Note

Uses a convex hull approximation of linearized geometry

Parameters
• mesh[in] Mesh containing the entities

• dim[in] The topological dimension of the mesh entities

• entities[in] The indices of the mesh entities (local to process)

• points[in] The set points from which to computed the shortest (shape=(num_points, 3))

Returns

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

graph::AdjacencyList<int> compute_colliding_cells(const mesh::Mesh &mesh, const graph::AdjacencyList<std::int32_t> &candidate_cells, const xt::xtensor<double, 2> &points)

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

Note

Uses the GJK algorithm, see geometry::compute_distance_gjk for details

Note

There may be nodes with no entries in the adjacency list

Parameters
• mesh[in] The mesh

• candidate_cells[in] List of candidate colliding cells for the ith point in `points`

• points[in] 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

class BoundingBoxTree
#include <BoundingBoxTree.h>

Axis-Aligned bounding box binary tree. It is used to find entities in a collection (often a mesh::Mesh).