Coverage for trimesh/path/traversal.py: 84%
164 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1import copy
2import itertools
4import numpy as np
6from .. import constants, grouping, util
7from ..typed import ArrayLike, Integer, NDArray, Number
8from .util import is_ccw
10try:
11 import networkx as nx
12except BaseException as E:
13 # create a dummy module which will raise the ImportError
14 # or other exception only when someone tries to use networkx
15 from ..exceptions import ExceptionWrapper
17 nx = ExceptionWrapper(E)
20def vertex_graph(entities):
21 """
22 Given a set of entity objects generate a networkx.Graph
23 that represents their vertex nodes.
25 Parameters
26 --------------
27 entities : list
28 Objects with 'closed' and 'nodes' attributes
30 Returns
31 -------------
32 graph : networkx.Graph
33 Graph where node indexes represent vertices
34 closed : (n,) int
35 Indexes of entities which are 'closed'
36 """
37 graph = nx.Graph()
38 closed = []
39 for index, entity in enumerate(entities):
40 if entity.closed:
41 closed.append(index)
42 else:
43 # or `entity.end_points`
44 graph.add_edges_from(entity.nodes, entity_index=index)
45 return graph, np.array(closed)
48def vertex_to_entity_path(vertex_path, graph, entities, vertices=None):
49 """
50 Convert a path of vertex indices to a path of entity indices.
52 Parameters
53 ----------
54 vertex_path : (n,) int
55 Ordered list of vertex indices representing a path
56 graph : nx.Graph
57 Vertex connectivity
58 entities : (m,) list
59 Entity objects
60 vertices : (p, dimension) float
61 Vertex points in space
63 Returns
64 ----------
65 entity_path : (q,) int
66 Entity indices which make up vertex_path
67 """
69 def edge_direction(a, b):
70 """
71 Given two edges, figure out if the first needs to be
72 reversed to keep the progression forward.
74 [1,0] [1,2] -1 1
75 [1,0] [2,1] -1 -1
76 [0,1] [1,2] 1 1
77 [0,1] [2,1] 1 -1
79 Parameters
80 ------------
81 a : (2,) int
82 b : (2,) int
84 Returns
85 ------------
86 a_direction : int
87 b_direction : int
88 """
89 if a[0] == b[0]:
90 return -1, 1
91 elif a[0] == b[1]:
92 return -1, -1
93 elif a[1] == b[0]:
94 return 1, 1
95 elif a[1] == b[1]:
96 return 1, -1
97 else:
98 constants.log.debug(
99 "\n".join(
100 [
101 "edges not connected!",
102 "vertex path %s",
103 "entity path: %s",
104 "entity[a]: %s,",
105 "entity[b]: %s",
106 ]
107 ),
108 vertex_path,
109 entity_path,
110 entities[ea].points,
111 entities[eb].points,
112 )
114 return None, None
116 if vertices is None or vertices.shape[1] != 2:
117 ccw_direction = 1
118 else:
119 ccw_check = is_ccw(vertices[np.append(vertex_path, vertex_path[0])])
120 ccw_direction = (ccw_check * 2) - 1
122 # make sure vertex path is correct type
123 vertex_path = np.asanyarray(vertex_path, dtype=np.int64)
124 # we will be saving entity indexes
125 entity_path = []
126 # loop through pairs of vertices
127 for i in np.arange(len(vertex_path) + 1):
128 # get two wrapped vertex positions
129 vertex_path_pos = np.mod(np.arange(2) + i, len(vertex_path))
130 vertex_index = vertex_path[vertex_path_pos]
131 entity_index = graph.get_edge_data(*vertex_index)["entity_index"]
132 entity_path.append(entity_index)
133 # remove duplicate entities and order CCW
134 entity_path = grouping.unique_ordered(entity_path)[::ccw_direction]
135 # check to make sure there is more than one entity
136 if len(entity_path) == 1:
137 # apply CCW reverse in place if necessary
138 if ccw_direction < 0:
139 index = entity_path[0]
140 entities[index].reverse()
142 return entity_path
143 # traverse the entity path and reverse entities in place to
144 # align with this path ordering
145 round_trip = np.append(entity_path, entity_path[0])
146 round_trip = itertools.pairwise(round_trip)
147 for ea, eb in round_trip:
148 da, db = edge_direction(entities[ea].end_points, entities[eb].end_points)
149 if da is not None:
150 entities[ea].reverse(direction=da)
151 entities[eb].reverse(direction=db)
153 entity_path = np.array(entity_path)
155 return entity_path
158def closed_paths(entities, vertices):
159 """
160 Paths are lists of entity indices.
161 We first generate vertex paths using graph cycle algorithms,
162 and then convert them to entity paths.
164 This will also change the ordering of entity.points in place
165 so a path may be traversed without having to reverse the entity.
167 Parameters
168 -------------
169 entities : (n,) entity objects
170 Entity objects
171 vertices : (m, dimension) float
172 Vertex points in space
174 Returns
175 -------------
176 entity_paths : sequence of (n,) int
177 Ordered traversals of entities
178 """
179 # get a networkx graph of entities
180 graph, closed = vertex_graph(entities)
181 # add entities that are closed as single- entity paths
182 entity_paths = np.reshape(closed, (-1, 1)).tolist()
183 # look for cycles in the graph, or closed loops
184 vertex_paths = nx.cycles.cycle_basis(graph)
186 # loop through every vertex cycle
187 for vertex_path in vertex_paths:
188 # a path has no length if it has fewer than 2 vertices
189 if len(vertex_path) < 2:
190 continue
191 # convert vertex indices to entity indices
192 entity_paths.append(vertex_to_entity_path(vertex_path, graph, entities, vertices))
194 return entity_paths
197def discretize_path(entities, vertices, path, scale=1.0):
198 """
199 Turn a list of entity indices into a path of connected points.
201 Parameters
202 -----------
203 entities : (j,) entity objects
204 Objects like 'Line', 'Arc', etc.
205 vertices: (n, dimension) float
206 Vertex points in space.
207 path : (m,) int
208 Indexes of entities
209 scale : float
210 Overall scale of drawing used for
211 Number tolerances in certain cases
213 Returns
214 -----------
215 discrete : (p, dimension) float
216 Connected points in space that lie on the
217 path and can be connected with line segments.
218 """
219 # make sure vertices are numpy array
220 vertices = np.asanyarray(vertices)
221 path_len = len(path)
222 if path_len == 0:
223 raise ValueError("Cannot discretize empty path!")
224 if path_len == 1:
225 # case where we only have one entity
226 discrete = np.asanyarray(entities[path[0]].discrete(vertices, scale=scale))
227 else:
228 # run through path appending each entity
229 discrete = []
230 for i, entity_id in enumerate(path):
231 # the current (n, dimension) discrete curve of an entity
232 current = entities[entity_id].discrete(vertices, scale=scale)
233 # check if we are on the final entity
234 if i >= (path_len - 1):
235 # if we are on the last entity include the last point
236 discrete.append(current)
237 else:
238 # slice off the last point so we don't get duplicate
239 # points from the end of one entity and the start of another
240 discrete.append(current[:-1])
241 # stack all curves to one nice (n, dimension) curve
242 discrete = np.vstack(discrete)
243 # make sure 2D curves are are counterclockwise
244 if vertices.shape[1] == 2 and not is_ccw(discrete):
245 # reversing will make array non c- contiguous
246 discrete = np.ascontiguousarray(discrete[::-1])
248 return discrete
251class PathSample:
252 def __init__(self, points: ArrayLike):
253 # make sure input array is numpy
254 self._points = np.array(points)
255 # find the direction of each segment
256 self._vectors = np.diff(self._points, axis=0)
257 # find the length of each segment
258 self._norms = util.row_norm(self._vectors)
259 # unit vectors for each segment
260 nonzero = self._norms > constants.tol_path.zero
261 self._unit_vec = self._vectors.copy()
262 self._unit_vec[nonzero] /= self._norms[nonzero].reshape((-1, 1))
263 # total distance in the path
264 self.length = self._norms.sum()
265 # cumulative sum of section length
266 # note that this is sorted
267 self._cum_norm = np.cumsum(self._norms)
269 def sample(
270 self, distances: ArrayLike, include_original: bool = False
271 ) -> NDArray[np.float64]:
272 """
273 Return points at the distances along the path requested.
275 Parameters
276 ----------
277 distances
278 Distances along the path to sample at.
279 include_original
280 Include the original vertices even if they are not
281 specified in `distance`. Useful as this will return
282 a result with identical area and length, however
283 indexes of `distance` will not correspond with result.
285 Returns
286 --------
287 samples : (n, dimension)
288 Samples requested.
289 `n==len(distances)` if not `include_original`
290 """
291 # return the indices in cum_norm that each sample would
292 # need to be inserted at to maintain the sorted property
293 positions = np.searchsorted(self._cum_norm, distances)
294 positions = np.clip(positions, 0, len(self._unit_vec) - 1)
295 offsets = np.append(0, self._cum_norm)[positions]
296 # the distance past the reference vertex we need to travel
297 projection = distances - offsets
298 # find out which direction we need to project
299 direction = self._unit_vec[positions]
300 # find out which vertex we're offset from
301 origin = self._points[positions]
303 # just the parametric equation for a line
304 resampled = origin + (direction * projection.reshape((-1, 1)))
306 if include_original:
307 # find the original positions that were not inserted
308 # note that this checks *exact float equal*
309 uninserted = ~np.isin(np.append(self._cum_norm, 0.0), projection)
311 if uninserted.any():
312 # find the index of the uninserted original points in the new sampling
313 index = np.searchsorted(positions, np.nonzero(uninserted)[0])
314 # insert the original points at the index
315 resampled = np.insert(resampled, index, self._points[uninserted], axis=0)
317 return resampled
319 def truncate(self, distance: Number) -> NDArray[np.float64]:
320 """
321 Return a truncated version of the path.
322 Only one vertex (at the endpoint) will be added.
324 Parameters
325 ----------
326 distance
327 Distance along the path to truncate at.
329 Returns
330 ----------
331 path
332 Path clipped to `distance` requested.
333 """
334 position = np.searchsorted(self._cum_norm, distance)
335 offset = distance - self._cum_norm[position - 1]
337 if offset < constants.tol_path.merge:
338 truncated = self._points[: position + 1]
339 else:
340 vector = util.unitize(
341 np.diff(self._points[np.arange(2) + position], axis=0).reshape(-1)
342 )
343 vector *= offset
344 endpoint = self._points[position] + vector
345 truncated = np.vstack((self._points[: position + 1], endpoint))
346 assert (
347 util.row_norm(np.diff(truncated, axis=0)).sum() - distance
348 ) < constants.tol_path.merge
350 return truncated
353def resample_path(
354 points: ArrayLike,
355 count: Integer | None = None,
356 step: Number | None = None,
357 step_round: bool = True,
358 include_original: bool = False,
359) -> NDArray[np.float64]:
360 """
361 Given a path along (n,d) points, resample them such that the
362 distance traversed along the path is constant in between each
363 of the resampled points. Note that this can produce clipping at
364 corners, as the original vertices are NOT guaranteed to be in the
365 new, resampled path.
367 ONLY ONE of count or step can be specified
368 Result can be uniformly distributed (np.linspace) by specifying count
369 Result can have a specific distance (np.arange) by specifying step
372 Parameters
373 ----------
374 points: (n, d) float
375 Points in space
376 count : int,
377 Number of points to sample evenly (aka np.linspace)
378 step : float
379 Distance each step should take along the path (aka np.arange)
380 step_round
381 Alter `step` to the nearest integer division of overall length.
382 include_original
383 Include the exact original points in the output.
385 Returns
386 ----------
387 resampled : (j,d) float
388 Points on the path
389 """
390 points = np.array(points, dtype=np.float64)
391 # generate samples along the perimeter from kwarg count or step
392 if (count is not None) and (step is not None):
393 raise ValueError("Only step OR count can be specified")
394 if (count is None) and (step is None):
395 raise ValueError("Either step or count must be specified")
397 sampler = PathSample(points)
398 if step is not None and step_round:
399 if step >= sampler.length:
400 return points[[0, -1]]
402 count = int(np.ceil(sampler.length / step))
404 if count is not None:
405 samples = np.linspace(0, sampler.length, count)
406 elif step is not None:
407 samples = np.arange(0, sampler.length, step)
409 resampled = sampler.sample(samples, include_original=include_original)
411 if constants.tol.strict:
412 check = util.row_norm(points[[0, -1]] - resampled[[0, -1]])
413 assert check[0] < constants.tol_path.merge
414 if count is not None:
415 assert check[1] < constants.tol_path.merge
417 return resampled
420def split(path):
421 """
422 Split a Path2D into multiple Path2D objects where each
423 one has exactly one root curve.
425 Parameters
426 --------------
427 path : trimesh.path.Path2D
428 Input geometry
430 Returns
431 -------------
432 split : list of trimesh.path.Path2D
433 Original geometry as separate paths
434 """
435 # avoid a circular import by referencing class of path
436 Path2D = type(path)
438 # save the results of the split to an array
439 split = []
441 # get objects from cache to avoid a bajillion
442 # cache checks inside the tight loop
443 paths = path.paths
444 discrete = path.discrete
445 polygons_closed = path.polygons_closed
446 enclosure_directed = path.enclosure_directed
448 for root_index, root in enumerate(path.root):
449 # get a list of the root curve's children
450 connected = list(enclosure_directed[root].keys())
451 # add the root node to the list
452 connected.append(root)
454 # store new paths and entities
455 new_paths = []
456 new_entities = []
458 for index in connected:
459 nodes = paths[index]
460 # add a path which is just sequential indexes
461 new_paths.append(np.arange(len(nodes)) + len(new_entities))
462 # save the entity indexes
463 new_entities.extend(nodes)
465 # store the root index from the original drawing
466 metadata = copy.deepcopy(path.metadata)
467 metadata["split_2D"] = root_index
468 # we made the root path the last index of connected
469 new_root = np.array([len(new_paths) - 1])
471 # prevents the copying from nuking our cache
472 with path._cache:
473 # create the Path2D
474 split.append(
475 Path2D(
476 entities=copy.deepcopy(path.entities[new_entities]),
477 vertices=copy.deepcopy(path.vertices),
478 metadata=metadata,
479 )
480 )
482 # add back expensive things to the cache
483 split[-1]._cache.update(
484 {
485 "paths": new_paths,
486 "polygons_closed": polygons_closed[connected],
487 "discrete": [discrete[c] for c in connected],
488 "root": new_root,
489 }
490 )
491 # set the cache ID
492 split[-1]._cache.id_set()
494 return np.array(split)