Coverage for trimesh/path/arc.py: 91%
89 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-10-02 20:54 +0000
1from dataclasses import dataclass
3import numpy as np
5from .. import util
6from ..constants import res_path as res
7from ..constants import tol_path as tol
8from ..typed import ArrayLike, NDArray, Number, float64
10# floating point zero
11_TOL_ZERO = 1e-12
14@dataclass
15class ArcInfo:
16 # What is the radius of the circular arc?
17 radius: float
19 # what is the center of the circular arc
20 # it is either 2D or 3D depending on input.
21 center: NDArray[float64]
23 # what is the 3D normal vector of the plane the arc lies on
24 normal: NDArray[float64] | None = None
26 # what is the starting and ending angle of the arc.
27 angles: NDArray[float64] | None = None
29 # what is the angular span of this circular arc.
30 span: Number | None = None
32 def __getitem__(self, item):
33 # add for backwards compatibility
34 return getattr(self, item)
37def arc_center(
38 points: ArrayLike, return_normal: bool = True, return_angle: bool = True
39) -> ArcInfo:
40 """
41 Given three points on a 2D or 3D arc find the center,
42 radius, normal, and angular span.
44 Parameters
45 ---------
46 points : (3, dimension) float
47 Points in space, where dimension is either 2 or 3
48 return_normal : bool
49 If True calculate the 3D normal unit vector
50 return_angle : bool
51 If True calculate the start and stop angle and span
53 Returns
54 ---------
55 info
56 Arc center, radius, and other information.
57 """
58 points = np.asanyarray(points, dtype=np.float64)
60 # get the non-unit vectors of the three points
61 vectors = points[[2, 0, 1]] - points[[1, 2, 0]]
62 # we need both the squared row sum and the non-squared
63 abc2 = np.dot(vectors**2, [1] * points.shape[1])
64 # same as np.linalg.norm(vectors, axis=1)
65 abc = np.sqrt(abc2)
67 # perform radius calculation scaled to shortest edge
68 # to avoid precision issues with small or large arcs
69 scale = abc.min()
70 # get the edge lengths scaled to the smallest
71 edges = abc / scale
72 # half the total length of the edges
73 half = edges.sum() / 2.0
74 # check the denominator for the radius calculation
75 denom = half * np.prod(half - edges)
76 if denom < tol.merge:
77 raise ValueError("arc is colinear!")
78 # find the radius and scale back after the operation
79 radius = scale * ((np.prod(edges) / 4.0) / np.sqrt(denom))
81 # use a barycentric approach to get the center
82 ba2 = (abc2[[1, 2, 0, 0, 2, 1, 0, 1, 2]] * [1, 1, -1, 1, 1, -1, 1, 1, -1]).reshape(
83 (3, 3)
84 ).sum(axis=1) * abc2
85 center = points.T.dot(ba2) / ba2.sum()
87 if tol.strict:
88 # all points should be at the calculated radius from center
89 assert util.allclose(np.linalg.norm(points - center, axis=1), radius)
91 # start with initial results
92 result = {"center": center, "radius": radius}
93 if return_normal:
94 if points.shape == (3, 2):
95 # for 2D arcs still use the cross product so that
96 # the sign of the normal vector is consistent
97 result["normal"] = util.unitize(
98 np.cross(np.append(-vectors[1], 0), np.append(vectors[2], 0))
99 )
100 else:
101 # otherwise just take the cross product
102 result["normal"] = util.unitize(np.cross(-vectors[1], vectors[2]))
104 if return_angle:
105 # vectors from points on arc to center point
106 vector = util.unitize(points - center)
107 edge_direction = np.diff(points, axis=0)
108 # find the angle between the first and last vector
109 dot = np.dot(*vector[[0, 2]])
110 if dot < (_TOL_ZERO - 1):
111 angle = np.pi
112 elif dot > 1 - _TOL_ZERO:
113 angle = 0.0
114 else:
115 angle = np.arccos(dot)
116 # if the angle is nonzero and vectors are opposite direction
117 # it means we have a long arc rather than the short path
118 if abs(angle) > _TOL_ZERO and np.dot(*edge_direction) < 0.0:
119 angle = (np.pi * 2) - angle
120 # convoluted angle logic
121 angles = np.arctan2(*vector[:, :2].T[::-1]) + np.pi * 2
122 angles_sorted = np.sort(angles[[0, 2]])
123 reverse = angles_sorted[0] < angles[1] < angles_sorted[1]
124 angles_sorted = angles_sorted[:: (1 - int(not reverse) * 2)]
125 result["angles"] = angles_sorted
126 result["span"] = angle
128 return ArcInfo(**result)
131def discretize_arc(points, close=False, scale=1.0):
132 """
133 Returns a version of a three point arc consisting of
134 line segments.
136 Parameters
137 ---------
138 points : (3, d) float
139 Points on the arc where d in [2,3]
140 close : boolean
141 If True close the arc into a circle
142 scale : float
143 What is the approximate overall drawing scale
144 Used to establish order of magnitude for precision
146 Returns
147 ---------
148 discrete : (m, d) float
149 Connected points in space
150 """
151 # make sure points are (n, 3)
152 points, is_2D = util.stack_3D(points, return_2D=True)
153 # find the center of the points
154 try:
155 # try to find the center from the arc points
156 center_info = arc_center(points)
157 except BaseException:
158 # if we hit an exception return a very bad but
159 # technically correct discretization of the arc
160 if is_2D:
161 return points[:, :2]
162 return points
164 center, R, N, angle = (
165 center_info.center,
166 center_info.radius,
167 center_info.normal,
168 center_info.span,
169 )
171 # if requested, close arc into a circle
172 if close:
173 angle = np.pi * 2
175 # the number of facets for the arc
176 # which is the maximum of angle and linear criteria
177 count = max(angle / res.seg_angle, (R * angle) / (res.seg_frac * scale))
179 # force at LEAST 4 points for the arc
180 # otherwise the endpoints will diverge
181 count = int(np.ceil(np.clip(count, 4, np.inf)))
183 V1 = util.unitize(points[0] - center)
184 V2 = util.unitize(np.cross(-N, V1))
185 # angle spacing
186 t = np.linspace(0.0, angle, count).reshape((-1, 1))
188 # apply the vector formula
189 discrete = (np.cos(t) * V1 + np.sin(t) * V2) * R + center
191 if close:
192 # snap closed circles to exactly float-equal
193 discrete[-1] = discrete[0]
194 else:
195 # snap the discrete result to exact control points
196 discrete[[0, -1]] = points[[0, -1]]
198 # clip to the dimension of input
199 discrete = discrete[:, : (3 - is_2D)]
201 return discrete
204def to_threepoint(center, radius, angles=None):
205 """
206 For 2D arcs, given a center and radius convert them to three
207 points on the arc.
209 Parameters
210 -----------
211 center : (2,) float
212 Center point on the plane
213 radius : float
214 Radius of arc
215 angles : (2,) float
216 Angles in radians for start and end angle
217 if not specified, will default to (0.0, pi)
219 Returns
220 ----------
221 three : (3, 2) float
222 Arc control points
223 """
224 # if no angles provided assume we want a half circle
225 if angles is None:
226 angles = [0.0, np.pi]
227 # force angles to float64
228 angles = np.asanyarray(angles, dtype=np.float64)
229 if angles.shape != (2,):
230 raise ValueError("angles must be (2,)!")
231 # provide the wrap around
232 if angles[1] < angles[0]:
233 angles[1] += np.pi * 2
235 center = np.asanyarray(center, dtype=np.float64)
236 if center.shape != (2,):
237 raise ValueError("only valid on 2D arcs!")
239 # turn the angles of [start, end]
240 # into [start, middle, end]
241 angles = np.array([angles[0], angles.mean(), angles[1]], dtype=np.float64)
242 # turn angles into (3, 2) points
243 three = (np.column_stack((np.cos(angles), np.sin(angles))) * radius) + center
245 return three