Coverage for trimesh/path/simplify.py: 86%
158 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1import collections
2import copy
4import numpy as np
6from .. import util
7from ..constants import log
8from ..constants import tol_path as tol
9from ..nsphere import fit_nsphere
10from . import arc, entities
13def fit_circle_check(points, scale, prior=None, final=False, verbose=False):
14 """
15 Fit a circle, and reject the fit if:
16 * the radius is larger than tol.radius_min*scale or tol.radius_max*scale
17 * any segment spans more than tol.seg_angle
18 * any segment is longer than tol.seg_frac*scale
19 * the fit deviates by more than tol.radius_frac*radius
20 * the segments on the ends deviate from tangent by more than tol.tangent
22 Parameters
23 ---------
24 points : (n, d)
25 List of points which represent a path
26 prior : (center, radius) tuple
27 Best guess or None if unknown
28 scale : float
29 What is the overall scale of the set of points
30 verbose : bool
31 Output log.debug messages for the reasons
32 for fit rejection only suggested for manual debugging
34 Returns
35 -----------
36 if fit is acceptable:
37 (center, radius) tuple
38 else:
39 None
40 """
41 # an arc needs at least three points
42 if len(points) < 3:
43 return None
44 # make sure our points are a numpy array
45 points = np.asanyarray(points, dtype=np.float64)
47 # do a least squares fit on the points
48 C, R, r_deviation = fit_nsphere(points, prior=prior)
50 # check to make sure radius is between min and max allowed
51 if not tol.radius_min < (R / scale) < tol.radius_max:
52 if verbose:
53 log.debug("circle fit error: R %f", R / scale)
54 return None
56 # check point radius error
57 r_error = r_deviation / R
58 if r_error > tol.radius_frac:
59 if verbose:
60 log.debug("circle fit error: fit %s", str(r_error))
61 return None
63 vectors = np.diff(points, axis=0)
64 segment = util.row_norm(vectors)
66 # approximate angle in radians, segments are linear length
67 # not arc length but this is close and avoids a cosine
68 angle = segment / R
69 if (angle > tol.seg_angle).any():
70 if verbose:
71 log.debug("circle fit error: angle %s", str(angle))
72 return None
74 if final and (angle > tol.seg_angle_min).sum() < 3:
75 log.debug("final: angle %s", str(angle))
76 return None
78 # check segment length as a fraction of drawing scale
79 scaled = segment / scale
81 if (scaled > tol.seg_frac).any():
82 if verbose:
83 log.debug("circle fit error: segment %s", str(scaled))
84 return None
86 # check to make sure the line segments on the ends are actually
87 # tangent with the candidate circle fit
88 mid_pt = points[[0, -2]] + (vectors[[0, -1]] * 0.5)
89 radial = util.unitize(mid_pt - C)
90 ends = util.unitize(vectors[[0, -1]])
91 tangent = np.abs(np.arccos(util.diagonal_dot(radial, ends)))
92 tangent = np.abs(tangent - np.pi / 2).max()
94 if tangent > tol.tangent:
95 if verbose:
96 log.debug("circle fit error: tangent %f", np.degrees(tangent))
97 return None
99 result = {"center": C, "radius": R}
101 return result
104def is_circle(points, scale, verbose=False):
105 """
106 Given a set of points, quickly determine if they represent
107 a circle or not.
109 Parameters
110 -------------
111 points : (n,2 ) float
112 Points in space
113 scale : float
114 Scale of overall drawing
115 verbose : bool
116 Print all fit messages or not
118 Returns
119 -------------
120 control: (3,2) float, points in space, OR
121 None, if not a circle
122 """
124 # make sure input is a numpy array
125 points = np.asanyarray(points)
126 scale = float(scale)
128 # can only be a circle if the first and last point are the
129 # same (AKA is a closed path)
130 if np.linalg.norm(points[0] - points[-1]) > tol.merge:
131 return None
133 box = np.ptp(points, axis=0)
134 # the bounding box size of the points
135 # check aspect ratio as an early exit if the path is not a circle
136 aspect = np.divide(*box)
137 if np.abs(aspect - 1.0) > tol.aspect_frac:
138 return None
140 # fit a circle with tolerance checks
141 CR = fit_circle_check(points, scale=scale)
142 if CR is None:
143 return None
145 # return the circle as three control points
146 control = arc.to_threepoint(**CR)
147 return control
150def merge_colinear(points, scale):
151 """
152 Given a set of points representing a path in space,
153 merge points which are colinear.
155 Parameters
156 ----------
157 points : (n, dimension) float
158 Points in space
159 scale : float
160 Scale of drawing for precision
162 Returns
163 ----------
164 merged : (j, d) float
165 Points with colinear and duplicate
166 points merged, where (j < n)
167 """
168 points = np.asanyarray(points, dtype=np.float64)
169 scale = float(scale)
171 if len(points.shape) != 2 or points.shape[1] != 2:
172 raise ValueError("only for 2D points!")
174 # if there's less than 3 points nothing to merge
175 if len(points) < 3:
176 return points.copy()
178 # the vector from one point to the next
179 direction = points[1:] - points[:-1]
180 # the length of the direction vector
181 direction_norm = util.row_norm(direction)
182 # make sure points don't have zero length
183 direction_ok = direction_norm > tol.merge
185 # remove duplicate points
186 points = np.vstack((points[0], points[1:][direction_ok]))
187 direction = direction[direction_ok]
188 direction_norm = direction_norm[direction_ok]
190 # create a vector between every other point, then turn it perpendicular
191 # if we have points A B C D
192 # and direction vectors A-B, B-C, etc
193 # these will be perpendicular to the vectors A-C, B-D, etc
194 perp = (points[2:] - points[:-2]).T[::-1].T
195 perp[:, 0] *= -1
196 perp_norm = util.row_norm(perp)
197 perp_nonzero = perp_norm > tol.merge
198 perp[perp_nonzero] /= perp_norm[perp_nonzero].reshape((-1, 1))
200 # find the projection of each direction vector
201 # onto the perpendicular vector
202 projection = np.abs(util.diagonal_dot(perp, direction[:-1]))
204 projection_ratio = np.max(
205 (projection / direction_norm[1:], projection / direction_norm[:-1]), axis=0
206 )
208 mask = np.ones(len(points), dtype=bool)
209 # since we took diff, we need to offset by one
210 mask[1:-1][projection_ratio < 1e-4 * scale] = False
212 merged = points[mask]
213 return merged
216def resample_spline(points, smooth=0.001, count=None, degree=3):
217 """
218 Resample a path in space, smoothing along a b-spline.
220 Parameters
221 -----------
222 points : (n, dimension) float
223 Points in space
224 smooth : float
225 Smoothing distance
226 count : int or None
227 Number of samples desired in output
228 degree : int
229 Degree of spline polynomial
231 Returns
232 ---------
233 resampled : (count, dimension) float
234 Points in space
235 """
236 from scipy.interpolate import splev, splprep
238 if count is None:
239 count = len(points)
240 points = np.asanyarray(points)
241 closed = np.linalg.norm(points[0] - points[-1]) < tol.merge
243 tpl = splprep(points.T, s=smooth, k=degree)[0]
244 i = np.linspace(0.0, 1.0, count)
245 resampled = np.column_stack(splev(i, tpl))
247 if closed:
248 shared = resampled[[0, -1]].mean(axis=0)
249 resampled[0] = shared
250 resampled[-1] = shared
252 return resampled
255def points_to_spline_entity(points, smooth=None, count=None):
256 """
257 Create a spline entity from a curve in space
259 Parameters
260 -----------
261 points : (n, dimension) float
262 Points in space
263 smooth : float
264 Smoothing distance
265 count : int or None
266 Number of samples desired in result
268 Returns
269 ---------
270 entity : entities.BSpline
271 Entity object with points indexed at zero
272 control : (m, dimension) float
273 New vertices for entity
274 """
276 from scipy.interpolate import splprep
278 if count is None:
279 count = len(points)
280 if smooth is None:
281 smooth = 0.002
283 points = np.asanyarray(points, dtype=np.float64)
284 closed = np.linalg.norm(points[0] - points[-1]) < tol.merge
286 knots, control, _degree = splprep(points.T, s=smooth)[0]
287 control = np.transpose(control)
288 index = np.arange(len(control))
290 if closed:
291 control[0] = control[[0, -1]].mean(axis=0)
292 control = control[:-1]
293 index[-1] = index[0]
295 entity = entities.BSpline(points=index, knots=knots, closed=closed)
297 return entity, control
300def simplify_basic(drawing, process=False, **kwargs):
301 """
302 Merge colinear segments and fit circles.
304 Parameters
305 -----------
306 drawing : Path2D
307 Source geometry, will not be modified
309 Returns
310 -----------
311 simplified : Path2D
312 Original path but with some closed line-loops converted to circles
313 """
315 if any(entity.__class__.__name__ != "Line" for entity in drawing.entities):
316 log.debug("Skipping path containing entities other than `Line`")
317 return drawing
319 # we are going to do a bookkeeping to avoid having
320 # to recompute literally everything when simplification is ran
321 cache = copy.deepcopy(drawing._cache)
323 # store new values
324 vertices_new = collections.deque()
325 entities_new = collections.deque()
327 # avoid thrashing cache in loop
328 scale = drawing.scale
330 # loop through (n, 2) closed paths
331 for discrete in drawing.discrete:
332 # check to see if the closed entity is a circle
333 circle = is_circle(discrete, scale=scale)
334 if circle is not None:
335 # the points are circular enough for our high standards
336 # so replace them with a closed Arc entity
337 entities_new.append(
338 entities.Arc(points=np.arange(3) + len(vertices_new), closed=True)
339 )
340 vertices_new.extend(circle)
341 else:
342 # not a circle, so clean up colinear segments
343 # then save it as a single line entity
344 points = merge_colinear(discrete, scale=scale)
345 # references for new vertices
346 indexes = np.arange(len(points)) + len(vertices_new)
347 # discrete curves are always closed
348 indexes[-1] = indexes[0]
349 # append new vertices and entity
350 entities_new.append(entities.Line(points=indexes))
351 vertices_new.extend(points)
353 # create the new drawing object
354 simplified = type(drawing)(
355 entities=entities_new,
356 vertices=vertices_new,
357 metadata=copy.deepcopy(drawing.metadata),
358 process=process,
359 )
360 # we have changed every path to a single closed entity
361 # either a closed arc, or a closed line
362 # so all closed paths are now represented by a single entity
363 cache.cache.update(
364 {
365 "paths": np.arange(len(entities_new)).reshape((-1, 1)),
366 "path_valid": np.ones(len(entities_new), dtype=bool),
367 "dangling": np.array([]),
368 }
369 )
371 # force recompute of exact bounds
372 if "bounds" in cache.cache:
373 cache.cache.pop("bounds")
375 simplified._cache = cache
376 # set the cache ID so it won't dump when a value is requested
377 simplified._cache.id_set()
379 return simplified
382def simplify_spline(path, smooth=None, verbose=False):
383 """
384 Replace discrete curves with b-spline or Arc and
385 return the result as a new Path2D object.
387 Parameters
388 ------------
389 path : trimesh.path.Path2D
390 Input geometry
391 smooth : float
392 Distance to smooth
394 Returns
395 ------------
396 simplified : Path2D
397 Consists of Arc and BSpline entities
398 """
400 new_vertices = []
401 new_entities = []
402 scale = path.scale
404 for discrete in path.discrete:
405 circle = is_circle(discrete, scale=scale, verbose=verbose)
406 if circle is not None:
407 # the points are circular enough for our high standards
408 # so replace them with a closed Arc entity
409 new_entities.append(
410 entities.Arc(points=np.arange(3) + len(new_vertices), closed=True)
411 )
412 new_vertices.extend(circle)
413 continue
415 # entities for this path
416 entity, vertices = points_to_spline_entity(discrete, smooth=smooth)
417 # reindex returned control points
418 entity.points += len(new_vertices)
419 # save entity and vertices
420 new_vertices.extend(vertices)
421 new_entities.append(entity)
423 # create the Path2D object for the result
424 simplified = type(path)(entities=new_entities, vertices=new_vertices)
426 return simplified