compas_cgal.geodesics ¤

Geodesic distance computation using the heat method.

Classes¤

ExactGeodesicSolver ¤

ExactGeodesicSolver(mesh: Mesh)

ExactGeodesicSolver(mesh: VerticesFaces)

ExactGeodesicSolver(mesh: MeshInput)

Exact geodesic solver retaining one mesh across source sets.

Use this when computing exact geodesics from several source sets on the same mesh. What is reused is narrower than for :class:HeatGeodesicSolver, and worth knowing: the CGAL mesh and its index maps are built once, and the AABB tree needed to locate source points is built on the first such query and never again. The wavefront propagation itself belongs to one source set and is redone per solve -- unlike the heat method's factorization, it is not reusable in principle.

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required

Examples:

>>> from compas.geometry import Sphere
>>> from compas_cgal.geodesics import ExactGeodesicSolver
>>> sphere = Sphere(1.0)
>>> mesh = sphere.to_vertices_and_faces(u=32, v=32, triangulated=True)
>>> solver = ExactGeodesicSolver(mesh)
>>> d0 = solver.solve([0])
>>> d1 = solver.solve([1])

Attributes¤

num_vertices `property` ¤

num_vertices: int

Number of vertices in the mesh.

Methods:¤

solve ¤

solve(sources: list[int], *, return_sources: Literal[False] = False) -> NDArray

solve(sources: list[int], *, return_sources: Literal[True]) -> tuple[NDArray, NDArray]

solve(
    sources: list[int], *, return_sources: bool = False
) -> NDArray | tuple[NDArray, NDArray]

Exact geodesic distances from source vertices.

Parameters:

Name	Type	Description	Default
`sources`	`list[int]`	Source vertex indices.	required
`return_sources`	`bool`	If True, also return the ordinal into `sources` of the nearest source per vertex.	`False`

Returns:

Type	Description
`NDArray \| Tuple[NDArray, NDArray]`	Distances of shape (n_vertices,), optionally with nearest-source ordinals.

solve_from_points ¤

solve_from_points(
    points: PointsLike, *, return_sources: Literal[False] = False
) -> NDArray

solve_from_points(
    points: PointsLike, *, return_sources: Literal[True]
) -> tuple[NDArray, NDArray]

solve_from_points(
    points: PointsLike, *, return_sources: bool = False
) -> NDArray | tuple[NDArray, NDArray]

Exact geodesic distances from source points located on the surface.

Parameters:

Name	Type	Description	Default
`points`	:attr:`compas_cgal.geodesics.PointsLike`	Source points, e.g. a list of :class:`compas.geometry.Point`. Duplicates are not collapsed; see :func:`exact_geodesic_distances_from_points`.	required
`return_sources`	`bool`	If True, also return the ordinal into `points` of the nearest source per vertex.	`False`

Returns:

Type	Description
`NDArray \| Tuple[NDArray, NDArray]`	Distances of shape (n_vertices,), optionally with nearest-source ordinals.

HeatGeodesicSolver ¤

HeatGeodesicSolver(mesh: Mesh)

HeatGeodesicSolver(mesh: VerticesFaces)

HeatGeodesicSolver(mesh: MeshInput)

Precomputed heat method solver for repeated geodesic queries.

Use this class when computing geodesic distances from multiple different sources on the same mesh. The expensive precomputation is done once in the constructor, and solve() can be called many times efficiently.

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required

Examples:

>>> from compas.geometry import Sphere
>>> from compas_cgal.geodesics import HeatGeodesicSolver
>>> sphere = Sphere(1.0)
>>> mesh = sphere.to_vertices_and_faces(u=32, v=32, triangulated=True)
>>> solver = HeatGeodesicSolver(mesh)  # precomputation happens here
>>> d0 = solver.solve([0])  # distances from vertex 0
>>> d1 = solver.solve([1])  # distances from vertex 1 (fast, reuses precomputation)

Attributes¤

num_vertices `property` ¤

num_vertices: int

Number of vertices in the mesh.

Methods:¤

solve ¤

solve(sources: list[int]) -> NDArray

Compute geodesic distances from source vertices.

Parameters:

Name	Type	Description	Default
`sources`	`list[int]`	Source vertex indices.	required

Returns:

Type	Description
`NDArray`	Geodesic distances from the nearest source to each vertex. Shape is (n_vertices,).

Functions:¤

exact_geodesic_distances ¤

exact_geodesic_distances(
    mesh: MeshInput, sources: list[int], *, return_sources: Literal[False] = False
) -> NDArray

exact_geodesic_distances(
    mesh: MeshInput, sources: list[int], *, return_sources: Literal[True]
) -> tuple[NDArray, NDArray]

exact_geodesic_distances(
    mesh: MeshInput, sources: list[int], *, return_sources: bool = False
) -> NDArray | tuple[NDArray, NDArray]

Exact polyhedral geodesic distances from a set of source vertices.

Computes the exact polyhedral geodesic (CGAL's Surface_mesh_shortest_path), evaluated in floating-point arithmetic: the algorithm is exact, its constructions are double precision. Distances are exactly 0 at every source vertex and the gradient magnitude is 1 by construction, which is what makes this backend usable as an accuracy reference for :func:heat_geodesic_distances.

With return_sources=False the signature and return match :func:heat_geodesic_distances exactly, so the two backends are interchangeable at a call site.

Cost differs sharply from the heat method even though the interfaces match. The heat method is two sparse solves; this is a whole-surface wavefront propagation, worst case O(n^2 log n) with sequence-tree memory. Measure before swapping one for the other on a large mesh.

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required
`sources`	`list[int]`	Source vertex indices (at least one; out-of-range indices are ignored and duplicates collapse).	required
`return_sources`	`bool`	If True, also return which source each vertex's geodesic came from.	`False`

Returns:

Type	Description
`NDArray \| Tuple[NDArray, NDArray]`	Geodesic distances from the nearest source to each vertex, shape (n_vertices,). If `return_sources` is True, additionally an int array of the same shape holding, for each vertex, the ORDINAL into `sources` of the nearest source, so that `sources[ordinal]` recovers the source vertex index.

Raises:

Type	Description
`ValueError`	If no valid source vertex index is given.
`RuntimeError`	If a connected component of the mesh contains no source.

Examples:

>>> from compas.geometry import Box
>>> from compas_cgal.geodesics import exact_geodesic_distances
>>> box = Box(1)
>>> mesh = box.to_vertices_and_faces(triangulated=True)
>>> distances = exact_geodesic_distances(mesh, [0])

exact_geodesic_distances_from_points ¤

exact_geodesic_distances_from_points(
    mesh: MeshInput, points: PointsLike, *, return_sources: Literal[False] = False
) -> NDArray

exact_geodesic_distances_from_points(
    mesh: MeshInput, points: PointsLike, *, return_sources: Literal[True]
) -> tuple[NDArray, NDArray]

exact_geodesic_distances_from_points(
    mesh: MeshInput, points: PointsLike, *, return_sources: bool = False
) -> NDArray | tuple[NDArray, NDArray]

Exact geodesic distances from source points located on the surface.

Unlike vertex sources, a source point may sit anywhere on a face. This is the entry point to use when the sources are samples of a curve lying on the surface: seeding the samples themselves avoids the error incurred by substituting the nearest mesh vertex for each one, which is bounded below by the edge length.

There is no heat-method counterpart. A heat source is an indicator on vertices, and a face-interior source cannot be expressed without splitting the mesh.

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required
`points`	:attr:`compas_cgal.geodesics.PointsLike`	Source points, e.g. a list of :class:`compas.geometry.Point`. Each is located on the surface, being projected to the closest point on the closest face. Callers that must bound that projection should compose with :func:`compas_cgal.projection.project_points_on_mesh`, which owns point-to-mesh proximity. Unlike vertex sources, duplicate points are not collapsed: doing so would require an equality test on coordinates, that is a positional tolerance, which this module does not own. A repeated point leaves the distance field unchanged and simply consumes an ordinal.	required
`return_sources`	`bool`	If True, also return which source each vertex's geodesic came from.	`False`

Returns:

Type	Description
`NDArray \| Tuple[NDArray, NDArray]`	Geodesic distances from the nearest source point to each vertex, shape (n_vertices,). If `return_sources` is True, additionally the ORDINAL into `points` of the nearest source, per vertex.

Raises:

Type	Description
`ValueError`	If `points` is empty, not (S, 3), or contains non-finite coordinates.
`RuntimeError`	If a connected component of the mesh contains no source.

geodesic_isolines ¤

geodesic_isolines(
    mesh: Mesh, sources: list[int], isovalues: list[float]
) -> PolylinesNumpy

geodesic_isolines(
    mesh: VerticesFaces, sources: list[int], isovalues: list[float]
) -> PolylinesNumpy

geodesic_isolines(
    mesh: MeshInput, sources: list[int], isovalues: list[float]
) -> PolylinesNumpy

Extract isoline polylines from geodesic distance field.

Computes geodesic distances and extracts polylines along specified isovalues.

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required
`sources`	`list[int]`	Source vertex indices for geodesic distance computation.	required
`isovalues`	`list[float]`	Isovalue thresholds for isoline extraction.	required

Returns:

Type	Description
attr:`compas_cgal.types.PolylinesNumpy`	List of polyline segments as Nx3 arrays of points.

geodesic_isolines_split ¤

geodesic_isolines_split(
    mesh: Mesh, sources: list[int], isovalues: list[float]
) -> list[VerticesFacesNumpy]

geodesic_isolines_split(
    mesh: VerticesFaces, sources: list[int], isovalues: list[float]
) -> list[VerticesFacesNumpy]

geodesic_isolines_split(
    mesh: MeshInput, sources: list[int], isovalues: list[float]
) -> list[VerticesFacesNumpy]

Split mesh into components along geodesic isolines.

Computes geodesic distances from sources, refines the mesh along specified isovalue thresholds, and splits into connected components.

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required
`sources`	`list[int]`	Source vertex indices for geodesic distance computation.	required
`isovalues`	`list[float]`	Isovalue thresholds for splitting. The mesh will be refined along curves where the geodesic distance equals each isovalue, then split into connected components.	required

Returns:

Type	Description
List[:attr:`compas_cgal.types.VerticesFacesNumpy`]	List of mesh components as (vertices, faces) tuples.

Examples:

>>> from compas.geometry import Sphere
>>> from compas_cgal.geodesics import geodesic_isolines_split
>>> sphere = Sphere(1.0)
>>> mesh = sphere.to_vertices_and_faces(u=32, v=32, triangulated=True)
>>> components = geodesic_isolines_split(mesh, [0], [0.5, 1.0, 1.5])
>>> len(components)  # Number of mesh strips

heat_geodesic_distances ¤

heat_geodesic_distances(mesh: Mesh, sources: list[int]) -> NDArray

heat_geodesic_distances(mesh: VerticesFaces, sources: list[int]) -> NDArray

heat_geodesic_distances(mesh: MeshInput, sources: list[int]) -> NDArray

Compute geodesic distances from source vertices using the heat method.

Heat method (Crane et al. 2017) with a Dirichlet-constrained Poisson step: the distance is exactly 0 at every source vertex and remains accurate for multi-vertex source sets (e.g. all boundary vertices of an open mesh).

Parameters:

Name	Type	Description	Default
`mesh`	:attr:`compas_cgal.geodesics.MeshInput`	A triangulated mesh, either a :class:`compas.datastructures.Mesh` or a :attr:`compas_cgal.types.VerticesFaces` tuple of vertices and faces.	required
`sources`	`list[int]`	Source vertex indices (at least one; out-of-range indices are ignored).	required

Returns:

Type	Description
`NDArray`	Geodesic distances from the nearest source to each vertex. Shape is (n_vertices,).

Raises:

Type	Description
`ValueError`	If no valid source vertex index is given.
`RuntimeError`	If a connected component of the mesh contains no source vertex.

Examples:

>>> from compas.geometry import Box
>>> from compas_cgal.geodesics import heat_geodesic_distances
>>> box = Box(1)
>>> mesh = box.to_vertices_and_faces(triangulated=True)
>>> distances = heat_geodesic_distances(mesh, [0])  # distances from vertex 0

compas_cgal.geodesics ¤

Classes¤

ExactGeodesicSolver ¤

Attributes¤

num_vertices property ¤

Methods:¤

solve ¤

solve_from_points ¤

HeatGeodesicSolver ¤

Attributes¤

num_vertices property ¤

Methods:¤

solve ¤

Functions:¤

exact_geodesic_distances ¤

exact_geodesic_distances_from_points ¤

geodesic_isolines ¤

geodesic_isolines_split ¤

heat_geodesic_distances ¤

num_vertices `property` ¤

num_vertices `property` ¤