Shortest Paths

closest_n_vertices(mesh, start, n, targets, weights='length', export_path_mesh=False)

Computes a direct path to the first n vertices of the target list. Paths are the ones computed by BFS order, and are not garanteed to be the shortest. This is done so that traversal of the mesh remains local for performance purposes.

If less than n vertices are provided in the list, will compute the shortest path to all provided targets.

Parameters:

Name	Type	Description	Default
mesh	SurfaceMesh	the mesh.	required
start	int	Vertex index of starting point in the mesh.	required
n	int		required
targets	list	description	required
weights (str | dict | Attribute)		provided weights of each edge. Options are: - "one" : uniform weight = 1 for every edge - "length" : use the length of the edge - any dict or Attribute on edges : custom weights weights are set to 0 for edges on the boundary. Defaults to "length".	required
export_path_mesh	bool	If specified, will also return the path as a Polyline file. Defaults to False.	False

Raises:

Type	Description
Exception	Fails if the target list is empty

shortest_path(mesh, start, targets, weights='length', export_path_mesh=False)

Computes the shortest path from 'start' vertex to all given targets. Uses Dijsktra's algorithm

Parameters:

Name	Type	Description	Default
mesh	Union[Polyline, SurfaceMesh, VolumeMesh]	The mesh	required
start	int	Vertex index of starting point on the mesh	required
targets	int | list | set	Vertex index of the end point on the mesh or list of vertex indexes for ending points on the mesh	required
weights (str | dict)		provided weights of each edge. Options are: - "one" : uniform weight = 1 for every edge - "length" : use the length of the edge - any dict : custom weights Defaults to "length".	required
export_path_mesh	bool	If specified, will also return the path as a Polyline file. Defaults to False.	False

Returns:

Name	Type	Description
dict	dict	target_id -> list of vertices to visit on shortest path from 'start' to 'target_id'
	dict	If export_path_mesh is set to True, also returns a Polyline

shortest_path_to_border(mesh, start, weights='length', export_path_mesh=False)

Computes the shortest path from 'start' vertex to the boundary of the mesh. Call to shortest_path_to_vertex_set with the set of boundary vertices

Parameters:

Name	Type	Description	Default
mesh	SurfaceMesh	The mesh	required
start	int	Vertex index of starting point on the mesh	required
weights (str | dict | Attribute)		provided weights of each edge. Options are: - "one" : uniform weight = 1 for every edge - "length" : use the length of the edge - any dict or Attribute on edges : custom weights weights are set to 0 for edges on the boundary. Defaults to "length".	required
export_path_mesh	bool	If specified, will also return the path as a Polyline file. Defaults to False.	False

Raises:

Type	Description
Exception	"Mesh has no border" raised if the border of the mesh does not exist

Returns:

Name	Type	Description
list	list	The list of vertices on shortest path
	list	If export_path_mesh is set to True, also returns a Polyline

shortest_path_to_vertex_set(mesh, start, targets, weights='length', export_path_mesh=False)

Computes the shortest path from 'start' vertex to the closest vertex in the target set The idea is to add fictionnal edges between all vertices of targets to a representent vertex, with weight 0, and call Dijsktra's algorithm to reach this vertex.

Parameters:

Name	Type	Description	Default
mesh	Union[Polyline, SurfaceMesh, VolumeMesh]	The mesh	required
start	int	Vertex index of starting point on the mesh	required
targets	list	list of vertices to reach	required
weights (str | dict)		provided weights of each edge. Options are: - "one" : uniform weight = 1 for every edge - "length" : use the length of the edge - any dict : custom weights Defaults to "length".	required
export_path_mesh	bool	If specified, will also return the path as a Polyline file. Defaults to False.	False

Raises:

Type	Description
Exception	Fails if the target list is empty

Returns:

Name	Type	Description
int		the index of the closest vertex from the targets set
list		the list of vertices on the closest path
		If export_path_mesh is set to True, also returns a Polyline