Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbf53eaf

Browse files
brunobeltrangreglucas
authored andcommitted
code to compute bezier segment / path lengths
1 parent40275b8 commitbf53eaf

File tree

6 files changed

+146
-7
lines changed

6 files changed

+146
-7
lines changed

‎lib/matplotlib/bezier.py

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44

55
importmath
66
importwarnings
7+
fromcollectionsimportdeque
78

89
importnumpyasnp
910

@@ -220,6 +221,93 @@ def point_at_t(self, t):
220221
"""
221222
returntuple(self(t))
222223

224+
defsplit_at_t(self,t):
225+
"""
226+
Split into two Bezier curves using de casteljau's algorithm.
227+
228+
Parameters
229+
----------
230+
t : float
231+
Point in [0,1] at which to split into two curves
232+
233+
Returns
234+
-------
235+
B1, B2 : BezierSegment
236+
The two sub-curves.
237+
"""
238+
new_cpoints=split_de_casteljau(self._cpoints,t)
239+
returnBezierSegment(new_cpoints[0]),BezierSegment(new_cpoints[1])
240+
241+
defcontrol_net_length(self):
242+
"""Sum of lengths between control points"""
243+
L=0
244+
N,d=self._cpoints.shape
245+
foriinrange(N-1):
246+
L+=np.linalg.norm(self._cpoints[i+1]-self._cpoints[i])
247+
returnL
248+
249+
defarc_length(self,rtol=1e-4,atol=1e-6):
250+
"""
251+
Estimate the length using iterative refinement.
252+
253+
Our estimate is just the average between the length of the chord and
254+
the length of the control net.
255+
256+
Since the chord length and control net give lower and upper bounds
257+
(respectively) on the length, this maximum possible error is tested
258+
against an absolute tolerance threshold at each subdivision.
259+
260+
However, sometimes this estimator converges much faster than this error
261+
estimate would suggest. Therefore, the relative change in the length
262+
estimate between subdivisions is compared to a relative error tolerance
263+
after each set of subdivisions.
264+
265+
Parameters
266+
----------
267+
rtol : float, default 1e-4
268+
If :code:`abs(est[i+1] - est[i]) <= rtol * est[i+1]`, we return
269+
:code:`est[i+1]`.
270+
atol : float, default 1e-6
271+
If the distance between chord length and control length at any
272+
point falls below this number, iteration is terminated.
273+
"""
274+
chord=np.linalg.norm(self._cpoints[-1]-self._cpoints[0])
275+
net=self.control_net_length()
276+
max_err= (net-chord)/2
277+
curr_est=chord+max_err
278+
# early exit so we don't try to "split" paths of zero length
279+
ifmax_err<atol:
280+
returncurr_est
281+
282+
prev_est=np.inf
283+
curves=deque([self])
284+
errs=deque([max_err])
285+
lengths=deque([curr_est])
286+
whilenp.abs(curr_est-prev_est)>rtol*curr_est:
287+
# subdivide the *whole* curve before checking relative convergence
288+
# again
289+
prev_est=curr_est
290+
num_curves=len(curves)
291+
foriinrange(num_curves):
292+
curve=curves.popleft()
293+
new_curves=curve.split_at_t(0.5)
294+
max_err-=errs.popleft()
295+
curr_est-=lengths.popleft()
296+
forncurveinnew_curves:
297+
chord=np.linalg.norm(
298+
ncurve._cpoints[-1]-ncurve._cpoints[0])
299+
net=ncurve.control_net_length()
300+
nerr= (net-chord)/2
301+
nlength=chord+nerr
302+
max_err+=nerr
303+
curr_est+=nlength
304+
curves.append(ncurve)
305+
errs.append(nerr)
306+
lengths.append(nlength)
307+
ifmax_err<atol:
308+
returncurr_est
309+
returncurr_est
310+
223311
@property
224312
defarc_area(self):
225313
r"""

‎lib/matplotlib/bezier.pyi

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,9 @@ class BezierSegment:
3535
def__init__(self,control_points:ArrayLike)->None: ...
3636
def__call__(self,t:ArrayLike)->np.ndarray: ...
3737
defpoint_at_t(self,t:float)->tuple[float, ...]: ...
38+
defsplit_at_t(self,t:float)->tuple[BezierSegment,BezierSegment]: ...
39+
defcontrol_net_length(self)->float: ...
40+
defarc_length(self,rtol:float,atol:float)->float: ...
3841
@property
3942
defarc_area(self)->float: ...
4043
@classmethod

‎lib/matplotlib/path.py

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -666,6 +666,28 @@ def intersects_bbox(self, bbox, filled=True):
666666
return_path.path_intersects_rectangle(
667667
self,bbox.x0,bbox.y0,bbox.x1,bbox.y1,filled)
668668

669+
deflength(self,rtol=None,atol=None,**kwargs):
670+
r"""
671+
Get length of Path.
672+
673+
Equivalent to (but not computed as)
674+
675+
.. math::
676+
677+
\sum_{j=1}^N \int_0^1 ||B'_j(t)|| dt
678+
679+
where the sum is over the :math:`N` Bezier curves that comprise the
680+
Path. Notice that this measure of length will assign zero weight to all
681+
isolated points on the Path.
682+
683+
Returns
684+
-------
685+
length : float
686+
The path length.
687+
"""
688+
returnnp.sum([B.arc_length(rtol,atol)
689+
forB,codeinself.iter_bezier(**kwargs)])
690+
669691
defsigned_area(self):
670692
"""
671693
Get signed area of the filled path.

‎lib/matplotlib/path.pyi

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -90,6 +90,7 @@ class Path:
9090
defget_extents(self,transform:Transform|None= ...,**kwargs)->Bbox: ...
9191
defintersects_path(self,other:Path,filled:bool= ...)->bool: ...
9292
defintersects_bbox(self,bbox:Bbox,filled:bool= ...)->bool: ...
93+
deflength(self,rtol:float|None,atol:float|None,**kwargs)->float: ...
9394
defsigned_area(self)->float: ...
9495
definterpolated(self,steps:int)->Path: ...
9596
defto_polygons(

‎lib/matplotlib/tests/test_bezier.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,15 @@ def test_split_bezier_with_large_values():
2626
_test_curves= [list(tc.path.iter_bezier())[-1][0]fortcin_test_curves]
2727

2828

29+
def_integral_arc_length(B):
30+
dB=B.differentiate(B)
31+
defintegrand(t):
32+
returnnp.linalg.norm(dB(t),axis=1)
33+
x=np.linspace(0,1,1000)
34+
y=integrand(x)
35+
returnnp.trapz(y,x)
36+
37+
2938
def_integral_arc_area(B):
3039
"""(Signed) area swept out by ray from origin to curve."""
3140
dB=B.differentiate(B)
@@ -39,3 +48,10 @@ def integrand(t):
3948
@pytest.mark.parametrize("B",_test_curves)
4049
deftest_area_formula(B):
4150
assertnp.isclose(_integral_arc_area(B),B.arc_area)
51+
52+
53+
@pytest.mark.parametrize("B",_test_curves)
54+
deftest_length_iteration(B):
55+
assertnp.isclose(_integral_arc_length(B),
56+
B.arc_length(rtol=1e-5,atol=1e-8),
57+
rtol=1e-5,atol=1e-8)

‎lib/matplotlib/tests/test_path.py

Lines changed: 16 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -88,22 +88,24 @@ def test_contains_points_negative_radius():
8888
np.testing.assert_equal(result, [True,False,False])
8989

9090

91-
_ExampleCurve=namedtuple('_ExampleCurve', ['path','extents','area'])
91+
_ExampleCurve=namedtuple('_ExampleCurve',
92+
['path','extents','area','length'])
9293
_test_curves= [
9394
# interior extrema determine extents and degenerate derivative
9495
_ExampleCurve(Path([[0,0], [1,0], [1,1], [0,1]],
9596
[Path.MOVETO,Path.CURVE4,Path.CURVE4,Path.CURVE4]),
96-
extents=(0.,0.,0.75,1.),area=0.6),
97+
extents=(0.,0.,0.75,1.),area=0.6,length=2.0),
9798
# a quadratic curve, clockwise
98-
_ExampleCurve(Path([[0,0], [0,1], [1,0]],
99-
[Path.MOVETO,Path.CURVE3,Path.CURVE3]),
100-
extents=(0.,0.,1.,0.5),area=-1/3),
99+
_ExampleCurve(Path([[0,0], [0,1], [1,0]], [Path.MOVETO,Path.CURVE3,
100+
Path.CURVE3]),extents=(0.,0.,1.,0.5),area=-1/3,
101+
length=(1/25)*(10+15*np.sqrt(2)+np.sqrt(5)
102+
* (np.arcsinh(2)+np.arcsinh(3)))),
101103
# a linear curve, degenerate vertically
102104
_ExampleCurve(Path([[0,1], [1,1]], [Path.MOVETO,Path.LINETO]),
103-
extents=(0.,1.,1.,1.),area=0.),
105+
extents=(0.,1.,1.,1.),area=0.,length=1.0),
104106
# a point
105107
_ExampleCurve(Path([[1,2]], [Path.MOVETO]),extents=(1.,2.,1.,2.),
106-
area=0.),
108+
area=0.,length=0.0),
107109
]
108110

109111

@@ -154,6 +156,13 @@ def test_signed_area_unit_circle():
154156
assertnp.isclose(circ.signed_area(),np.pi)
155157

156158

159+
@pytest.mark.parametrize('precomputed_curve',_test_curves)
160+
deftest_length_curve(precomputed_curve):
161+
path,length=precomputed_curve.path,precomputed_curve.length
162+
assertnp.isclose(path.length(rtol=1e-5,atol=1e-8),length,rtol=1e-5,
163+
atol=1e-8)
164+
165+
157166
deftest_point_in_path_nan():
158167
box=np.array([[0,0], [1,0], [1,1], [0,1], [0,0]])
159168
p=Path(box)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp