Coverage for trimesh/path/segments.py: 96%
142 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1"""
2segments.py
3--------------
5Deal with (n, 2, 3) line segments.
6"""
8import numpy as np
10from .. import geometry, transformations, util
11from ..constants import tol
12from ..grouping import group_rows, unique_rows
13from ..interval import union
14from ..typed import ArrayLike, Integer, NDArray, Number, float64
17def segments_to_parameters(segments: ArrayLike):
18 """
19 For 3D line segments defined by two points, turn
20 them in to an origin defined as the closest point along
21 the line to the zero origin as well as a direction vector
22 and start and end parameter.
24 Parameters
25 ------------
26 segments : (n, 2, 3) float
27 Line segments defined by start and end points
29 Returns
30 --------------
31 origins : (n, 3) float
32 Point on line closest to [0, 0, 0]
33 vectors : (n, 3) float
34 Unit line directions
35 parameters : (n, 2) float
36 Start and end distance pairs for each line
37 """
38 segments = np.asanyarray(segments, dtype=np.float64)
39 if not util.is_shape(segments, (-1, 2, (2, 3))):
40 raise ValueError("incorrect segment shape!", segments.shape)
42 # make the initial origin one of the end points
43 endpoint = segments[:, 0]
44 vectors = segments[:, 1] - endpoint
45 vectors_norm = util.row_norm(vectors)
46 vectors /= vectors_norm.reshape((-1, 1))
48 # find the point along the line nearest the origin
49 offset = util.diagonal_dot(endpoint, vectors)
50 # points nearest [0, 0, 0] will be our new origin
51 origins = endpoint + (offset.reshape((-1, 1)) * -vectors)
53 # parametric start and end of line segment
54 parameters = np.column_stack((offset, offset + vectors_norm))
55 # make sure signs are consistent
56 vectors, signs = util.vector_hemisphere(vectors, return_sign=True)
57 parameters *= signs.reshape((-1, 1))
59 return origins, vectors, parameters
62def parameters_to_segments(
63 origins: NDArray[float64], vectors: ArrayLike, parameters: NDArray[float64]
64):
65 """
66 Convert a parametric line segment representation to
67 a two point line segment representation
69 Parameters
70 ------------
71 origins : (n, 3) float
72 Line origin point
73 vectors : (n, 3) float
74 Unit line directions
75 parameters : (n, 2) float
76 Start and end distance pairs for each line
78 Returns
79 --------------
80 segments : (n, 2, 3) float
81 Line segments defined by start and end points
82 """
83 # don't copy input
84 origins = np.asanyarray(origins, dtype=np.float64)
85 vectors = np.asanyarray(vectors, dtype=np.float64)
86 parameters = np.asanyarray(parameters, dtype=np.float64)
88 # turn the segments into a reshapable 2D array
89 segments = np.hstack(
90 (origins + vectors * parameters[:, :1], origins + vectors * parameters[:, 1:])
91 )
93 return segments.reshape((-1, 2, origins.shape[1]))
96def colinear_pairs(
97 segments: ArrayLike,
98 radius: Number = 0.01,
99 angle: Number = 0.01,
100 length: Number | None = None,
101) -> NDArray[np.int64]:
102 """
103 Find pairs of segments which are colinear.
105 Parameters
106 -------------
107 segments : (n, 2, (2, 3)) float
108 Two or three dimensional line segments
109 radius
110 Maximum radius line origins can differ
111 and be considered colinear
112 angle
113 Maximum angle in radians segments can
114 differ and still be considered colinear
115 length
116 If specified, will additionally require
117 that pairs have a *vertex* within this distance.
119 Returns
120 ------------
121 pairs : (m, 2) int
122 Indexes of segments which are colinear
123 """
124 from scipy import spatial
126 # convert segments to parameterized origins
127 # which are the closest point on the line to
128 # the actual zero- origin
129 origins, vectors, _param = segments_to_parameters(segments)
131 # create a kdtree for origins
132 tree = spatial.cKDTree(origins)
134 # find origins closer than specified radius
135 pairs = tree.query_pairs(r=radius, output_type="ndarray")
137 # calculate angles between pairs
138 angles = geometry.vector_angle(vectors[pairs])
140 # angles can be within tolerance of 180 degrees or 0.0 degrees
141 angle_ok = np.logical_or(
142 util.isclose(angles, np.pi, atol=angle), util.isclose(angles, 0.0, atol=angle)
143 )
145 # apply angle threshold
146 colinear = pairs[angle_ok]
148 # if length is specified check endpoint proximity
149 if length is not None:
150 # `segments` index of colinear pairs
151 a, b = colinear.T
153 # we want the minimum distance of any of these pairs:
154 # a[0] - b[0]
155 # a[1] - b[0]
156 # a[0] - b[1]
157 # a[1] - b[1]
158 # do it in the most confusing possible vectorized way
159 min_vertex = np.linalg.norm(
160 segments[a][:, [0, 1, 0, 1], :] - segments[b][:, [0, 0, 1, 1], :], axis=2
161 ).min(axis=1)
163 # remove pairs that don't meet the distance metric
164 colinear = colinear[min_vertex < length]
166 return colinear
169def clean(segments: ArrayLike, digits: Integer = 10) -> NDArray[float64]:
170 """
171 Clean up line segments by unioning the ranges of colinear segments.
173 Parameters
174 ------------
175 segments : (n, 2, 2) or (n, 2, 3)
176 Line segments in space.
177 digits
178 How many digits to consider.
180 Returns
181 -----------
182 cleaned : (m, 2, 2) or (m, 2, 3)
183 Where `m <= n`
184 """
185 # convert segments to parameterized origins
186 # which are the closest point on the line to
187 # the actual zero- origin
188 origins, vectors, param = segments_to_parameters(segments)
190 # make sure parameters are in min-max order
191 param.sort(axis=1)
193 # find the groups of values with identical origins and vectors
194 groups = group_rows(np.column_stack((origins, vectors)), digits=digits)
196 # get the union of every interval range for colinear segments
197 unions = [union(param[g][param[g][:, 0].argsort()], sort=False) for g in groups]
198 # reconstruct indexes for the origins and vectors
199 indexes = np.concatenate([g[: len(u)] for g, u in zip(groups, unions)])
201 # convert parametric form back into vertex-segment form
202 return parameters_to_segments(
203 origins=origins[indexes], vectors=vectors[indexes], parameters=np.vstack(unions)
204 )
207def split(segments: ArrayLike, points: ArrayLike, atol: Number = 1e-5):
208 """
209 Find any points that lie on a segment (not an endpoint)
210 and then split that segment into two segments.
212 We are basically going to find the distance between
213 point and both segment vertex, and see if it is with
214 tolerance of the segment length.
216 Parameters
217 --------------
218 segments : (n, 2, (2, 3) float
219 Line segments in space
220 points : (n, (2, 3)) float
221 Points in space
222 atol : float
223 Absolute tolerance for distances
225 Returns
226 -------------
227 split : (n, 2, (3 | 3) float
228 Line segments in space, split at vertices
229 """
231 points = np.asanyarray(points, dtype=np.float64)
232 segments = np.asanyarray(segments, dtype=np.float64)
233 # reshape to a flat 2D (n, dimension) array
234 seg_flat = segments.reshape((-1, segments.shape[2]))
236 # find the length of every segment
237 length = ((segments[:, 0, :] - segments[:, 1, :]) ** 2).sum(axis=1) ** 0.5
239 # a mask to remove segments we split at the end
240 keep = np.ones(len(segments), dtype=bool)
241 # append new segments to a list
242 new_seg = []
244 # loop through every point
245 for p in points:
246 # note that you could probably get a speedup
247 # by using scipy.spatial.distance.cdist here
249 # find the distance from point to every segment endpoint
250 pair = ((seg_flat - p) ** 2).sum(axis=1).reshape((-1, 2)) ** 0.5
251 # point is on a segment if it is not on a vertex
252 # and the sum length is equal to the actual segment length
253 on_seg = np.logical_and(
254 util.isclose(length, pair.sum(axis=1), atol=atol),
255 ~util.isclose(pair, 0.0, atol=atol).any(axis=1),
256 )
258 # if we have any points on the segment split it in twain
259 if on_seg.any():
260 # remove the original segment
261 keep = np.logical_and(keep, ~on_seg)
262 # split every segment that this point lies on
263 for seg in segments[on_seg]:
264 new_seg.append([p, seg[0]])
265 new_seg.append([p, seg[1]])
267 if len(new_seg) > 0:
268 return np.vstack((segments[keep], new_seg))
269 else:
270 return segments
273def unique(segments: ArrayLike, digits: Integer = 5):
274 """
275 Find unique non-zero line segments.
277 Parameters
278 ------------
279 segments : (n, 2, (2|3)) float
280 Line segments in space
281 digits : int
282 How many digits to consider when merging vertices
284 Returns
285 -----------
286 unique : (m, 2, (2|3)) float
287 Segments with duplicates merged
288 """
289 segments = np.asanyarray(segments, dtype=np.float64)
291 # find segments as unique indexes so we can find duplicates
292 inverse = unique_rows(segments.reshape((-1, segments.shape[2])), digits=digits)[
293 1
294 ].reshape((-1, 2))
295 # make sure rows are sorted
296 inverse.sort(axis=1)
297 # remove segments where both indexes are the same
298 mask = np.zeros(len(segments), dtype=bool)
299 # only include the first occurrence of a segment
300 mask[unique_rows(inverse)[0]] = True
301 # remove segments that are zero-length
302 mask[inverse[:, 0] == inverse[:, 1]] = False
303 # apply the unique mask
304 unique = segments[mask]
306 return unique
309def extrude(segments: ArrayLike, height: Number, double_sided: bool = False):
310 """
311 Extrude 2D line segments into 3D triangles.
313 Parameters
314 -------------
315 segments : (n, 2, 2) float
316 2D line segments
317 height : float
318 Distance to extrude along Z
319 double_sided : bool
320 If true, return 4 triangles per segment
322 Returns
323 -------------
324 vertices : (n, 3) float
325 Vertices in space
326 faces : (n, 3) int
327 Indices of vertices forming triangles
328 """
329 segments = np.asanyarray(segments, dtype=np.float64)
330 if not util.is_shape(segments, (-1, 2, 2)):
331 raise ValueError("segments shape incorrect")
333 # we are creating two vertices triangles for every 2D line segment
334 # on the segments of the 2D triangulation
335 vertices = np.column_stack(
336 (
337 np.tile(segments.reshape((-1, 2)), 2).reshape((-1, 2)),
338 np.tile([0, height, 0, height], len(segments)),
339 )
340 )
341 faces = (
342 np.tile([3, 1, 2, 2, 1, 0], (len(segments), 1))
343 + np.arange(len(segments)).reshape((-1, 1)) * 4
344 ).reshape((-1, 3))
346 if double_sided:
347 # stack so they will render from the back
348 faces = np.vstack((faces, np.fliplr(faces)))
350 return vertices, faces
353def length(segments: ArrayLike, summed: bool = True) -> np.float64 | NDArray[np.float64]:
354 """
355 Return the lengths of an array of line segments.
357 Parameters
358 -------------
359 segments : (n, 2, 2) float
360 2D line segments
361 summed
362 Return the total length, not the per-segment length.
364 Returns
365 -------------
366 length
367 Either total length or per-segment length.
368 """
369 segments = np.asanyarray(segments, dtype=np.float64)
370 norms = util.row_norm(segments[:, 0, :] - segments[:, 1, :])
371 if summed:
372 return norms.sum()
373 return norms
376def resample(
377 segments: ArrayLike,
378 maxlen: Number,
379 return_index: bool = False,
380 return_count: bool = False,
381):
382 """
383 Resample line segments until no segment
384 is longer than maxlen.
386 Parameters
387 -------------
388 segments : (n, 2, 2|3) float
389 2D line segments
390 maxlen : float
391 The maximum length of a line segment
392 return_index : bool
393 Return the index of the source segment
394 return_count : bool
395 Return how many segments each original was split into
397 Returns
398 -------------
399 resampled : (m, 2, 2|3) float
400 Line segments where no segment is longer than maxlen
401 index : (m,) int
402 [OPTIONAL] The index of segments resampled came from
403 count : (n,) int
404 [OPTIONAL] The count of the original segments
405 """
406 # check arguments
407 maxlen = float(maxlen)
408 segments = np.array(segments, dtype=np.float64)
409 if len(segments.shape) != 3:
410 raise ValueError(f"{segments.shape} != (n, 2, 2|3)")
412 dimension = segments.shape[2]
414 # shortcut for endpoints
415 pt1 = segments[:, 0]
416 pt2 = segments[:, 1]
417 # vector between endpoints
418 vec = pt2 - pt1
419 # the integer number of times a segment needs to be split
420 splits = np.ceil(util.row_norm(vec) / maxlen).astype(np.int64)
422 # save resulting segments
423 result = []
424 # save index of original segment
425 index = []
427 tile = np.tile
428 # generate the line indexes ahead of time
429 stacks = util.stack_lines(np.arange(splits.max() + 1))
431 # loop through each count of unique splits needed
432 for split in np.unique(splits):
433 # get a mask of which segments need to be split
434 mask = splits == split
435 # the vector for each incremental length
436 increment = vec[mask] / split
437 # stack the increment vector into the shape needed
438 v = tile(increment, split + 1).reshape((-1, dimension)) * tile(
439 np.arange(split + 1), len(increment)
440 ).reshape((-1, 1))
441 # stack the origin points correctly
442 o = tile(pt1[mask], split + 1).reshape((-1, dimension))
443 # now get each segment as an (split, 3) polyline
444 poly = (o + v).reshape((-1, split + 1, dimension))
445 # save the resulting segments
446 # magical slicing is equivalent to:
447 # > [p[stack] for p in poly]
448 result.extend(poly[:, stacks[:split]])
450 if return_index:
451 # get the original index from the mask
452 index_original = np.nonzero(mask)[0].reshape((-1, 1))
453 # save one entry per split segment
454 index.append(
455 (np.ones((len(poly), split), dtype=np.int64) * index_original).ravel()
456 )
457 if tol.strict:
458 # check to make sure every start and end point
459 # from the reconstructed result corresponds
460 for original, recon in zip(segments[mask], poly):
461 assert np.allclose(original[0], recon[0])
462 assert np.allclose(original[-1], recon[-1])
463 # make sure stack slicing was OK
464 assert np.allclose(util.stack_lines(np.arange(split + 1)), stacks[:split])
466 # stack into (n, 2, 3) segments
467 result = [np.concatenate(result)]
469 if tol.strict:
470 # make sure resampled segments have the same length as input
471 assert np.isclose(length(segments), length(result[0]), atol=1e-3)
473 # stack additional return options
474 if return_index:
475 # stack original indexes
476 index = np.concatenate(index)
477 if tol.strict:
478 # index should correspond to result
479 assert len(index) == len(result[0])
480 # every segment should be represented
481 assert set(index) == set(range(len(segments)))
482 result.append(index)
484 if return_count:
485 result.append(splits)
487 if len(result) == 1:
488 return result[0]
489 return result
492def to_svg(
493 segments: ArrayLike,
494 digits: Integer = 4,
495 matrix: ArrayLike | None = None,
496 merge: bool = True,
497) -> str:
498 """
499 Convert (n, 2, 2) line segments to an SVG path string.
501 Parameters
502 ------------
503 segments : (n, 2, 2) float
504 Line segments to convert
505 digits : int
506 Number of digits to include in SVG string
507 matrix : None or (3, 3) float
508 Homogeneous 2D transformation to apply before export
510 Returns
511 -----------
512 path : str
513 SVG path string with one line per segment
514 IE: 'M 0.1 0.2 L 10 12'
515 """
516 segments = np.array(segments, copy=True)
517 if not util.is_shape(segments, (-1, 2, 2)):
518 raise ValueError("only for (n, 2, 2) segments!")
520 # create the array to export
521 # apply 2D transformation if passed
522 if matrix is not None:
523 segments = transformations.transform_points(
524 segments.reshape((-1, 2)), matrix=matrix
525 ).reshape((-1, 2, 2))
527 if merge:
528 # remove duplicate and zero-length segments
529 segments = unique(segments, digits=digits)
531 # create the format string for a single line segment
532 base = "M_ _L_ _".replace("_", "{:0." + str(int(digits)) + "f}")
533 # create one large format string then apply points
534 result = (base * len(segments)).format(*segments.ravel())
535 return result