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

Commite841b51

Browse files
authored
Merge pull request#16832 from brunobeltran/path_size_calc
Correctly compute path extents
2 parents005c7a6 +95a530c commite841b51

File tree

5 files changed

+253
-24
lines changed

5 files changed

+253
-24
lines changed
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
2+
Functions to compute a Path's size
3+
----------------------------------
4+
5+
Various functions were added to `~.bezier.BezierSegment` and `~.path.Path` to
6+
allow computation of the shape/size of a `~.path.Path` and its composite Bezier
7+
curves.
8+
9+
In addition to the fixes below, `~.bezier.BezierSegment` has gained more
10+
documentation and usability improvements, including properties that contain its
11+
dimension, degree, control_points, and more.
12+
13+
Better interface for Path segment iteration
14+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
15+
16+
`~.path.Path.iter_bezier` iterates through the `~.bezier.BezierSegment`'s that
17+
make up the Path. This is much more useful typically than the existing
18+
`~.path.Path.iter_segments` function, which returns the absolute minimum amount
19+
of information possible to reconstruct the Path.
20+
21+
Fixed bug that computed a Path's Bbox incorrectly
22+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
23+
24+
Historically, `~.path.Path.get_extents` has always simply returned the Bbox of
25+
a curve's control points, instead of the Bbox of the curve itself. While this is
26+
a correct upper bound for the path's extents, it can differ dramatically from
27+
the Path's actual extents for non-linear Bezier curves.

‎lib/matplotlib/bezier.py

Lines changed: 124 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2,12 +2,24 @@
22
A module providing some utility functions regarding Bezier path manipulation.
33
"""
44

5+
fromfunctoolsimportlru_cache
56
importmath
7+
importwarnings
68

79
importnumpyasnp
810

911
importmatplotlib.cbookascbook
1012

13+
# same algorithm as 3.8's math.comb
14+
@np.vectorize
15+
@lru_cache(maxsize=128)
16+
def_comb(n,k):
17+
ifk>n:
18+
return0
19+
k=min(k,n-k)
20+
i=np.arange(1,k+1)
21+
returnnp.prod((n+1-i)/i).astype(int)
22+
1123

1224
classNonIntersectingPathException(ValueError):
1325
pass
@@ -168,26 +180,127 @@ def find_bezier_t_intersecting_with_closedpath(
168180

169181
classBezierSegment:
170182
"""
171-
AD-dimensional Bezier segment.
183+
Ad-dimensional Bezier segment.
172184
173185
Parameters
174186
----------
175-
control_points : (N,D) array
187+
control_points : (N,d) array
176188
Location of the *N* control points.
177189
"""
178190

179191
def__init__(self,control_points):
180-
n=len(control_points)
181-
self._orders=np.arange(n)
182-
coeff= [math.factorial(n-1)
183-
// (math.factorial(i)*math.factorial(n-1-i))
184-
foriinrange(n)]
185-
self._px=np.asarray(control_points).T*coeff
192+
self._cpoints=np.asarray(control_points)
193+
self._N,self._d=self._cpoints.shape
194+
self._orders=np.arange(self._N)
195+
coeff= [math.factorial(self._N-1)
196+
// (math.factorial(i)*math.factorial(self._N-1-i))
197+
foriinrange(self._N)]
198+
self._px= (self._cpoints.T*coeff).T
199+
200+
def__call__(self,t):
201+
"""
202+
Evaluate the Bezier curve at point(s) t in [0, 1].
203+
204+
Parameters
205+
----------
206+
t : float (k,), array_like
207+
Points at which to evaluate the curve.
208+
209+
Returns
210+
-------
211+
float (k, d), array_like
212+
Value of the curve for each point in *t*.
213+
"""
214+
t=np.asarray(t)
215+
return (np.power.outer(1-t,self._orders[::-1])
216+
*np.power.outer(t,self._orders)) @self._px
186217

187218
defpoint_at_t(self,t):
188-
"""Return the point on the Bezier curve for parameter *t*."""
189-
returntuple(
190-
self._px @ (((1-t)**self._orders)[::-1]*t**self._orders))
219+
"""Evaluate curve at a single point *t*. Returns a Tuple[float*d]."""
220+
returntuple(self(t))
221+
222+
@property
223+
defcontrol_points(self):
224+
"""The control points of the curve."""
225+
returnself._cpoints
226+
227+
@property
228+
defdimension(self):
229+
"""The dimension of the curve."""
230+
returnself._d
231+
232+
@property
233+
defdegree(self):
234+
"""Degree of the polynomial. One less the number of control points."""
235+
returnself._N-1
236+
237+
@property
238+
defpolynomial_coefficients(self):
239+
r"""
240+
The polynomial coefficients of the Bezier curve.
241+
242+
.. warning:: Follows opposite convention from `numpy.polyval`.
243+
244+
Returns
245+
-------
246+
float, (n+1, d) array_like
247+
Coefficients after expanding in polynomial basis, where :math:`n`
248+
is the degree of the bezier curve and :math:`d` its dimension.
249+
These are the numbers (:math:`C_j`) such that the curve can be
250+
written :math:`\sum_{j=0}^n C_j t^j`.
251+
252+
Notes
253+
-----
254+
The coefficients are calculated as
255+
256+
.. math::
257+
258+
{n \choose j} \sum_{i=0}^j (-1)^{i+j} {j \choose i} P_i
259+
260+
where :math:`P_i` are the control points of the curve.
261+
"""
262+
n=self.degree
263+
# matplotlib uses n <= 4. overflow plausible starting around n = 15.
264+
ifn>10:
265+
warnings.warn("Polynomial coefficients formula unstable for high "
266+
"order Bezier curves!",RuntimeWarning)
267+
P=self.control_points
268+
j=np.arange(n+1)[:,None]
269+
i=np.arange(n+1)[None, :]# _comb is non-zero for i <= j
270+
prefactor= (-1)**(i+j)*_comb(j,i)# j on axis 0, i on axis 1
271+
return_comb(n,j)*prefactor @P# j on axis 0, self.dimension on 1
272+
273+
defaxis_aligned_extrema(self):
274+
"""
275+
Return the dimension and location of the curve's interior extrema.
276+
277+
The extrema are the points along the curve where one of its partial
278+
derivatives is zero.
279+
280+
Returns
281+
-------
282+
dims : int, array_like
283+
Index :math:`i` of the partial derivative which is zero at each
284+
interior extrema.
285+
dzeros : float, array_like
286+
Of same size as dims. The :math:`t` such that :math:`d/dx_i B(t) =
287+
0`
288+
"""
289+
n=self.degree
290+
Cj=self.polynomial_coefficients
291+
dCj=np.arange(1,n+1)[:,None]*Cj[1:]
292+
iflen(dCj)==0:
293+
returnnp.array([]),np.array([])
294+
dims= []
295+
roots= []
296+
fori,piinenumerate(dCj.T):
297+
r=np.roots(pi[::-1])
298+
roots.append(r)
299+
dims.append(np.full_like(r,i))
300+
roots=np.concatenate(roots)
301+
dims=np.concatenate(dims)
302+
in_range=np.isreal(roots)& (roots>=0)& (roots<=1)
303+
returndims[in_range],np.real(roots)[in_range]
191304

192305

193306
defsplit_bezier_intersecting_with_closedpath(

‎lib/matplotlib/path.py

Lines changed: 69 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
importmatplotlibasmpl
1818
from .import_path,cbook
1919
from .cbookimport_to_unmasked_float_array,simple_linear_interpolation
20+
from .bezierimportBezierSegment
2021

2122

2223
classPath:
@@ -421,6 +422,53 @@ def iter_segments(self, transform=None, remove_nans=True, clip=None,
421422
curr_vertices=np.append(curr_vertices,next(vertices))
422423
yieldcurr_vertices,code
423424

425+
defiter_bezier(self,**kwargs):
426+
"""
427+
Iterate over each bezier curve (lines included) in a Path.
428+
429+
Parameters
430+
----------
431+
**kwargs
432+
Forwarded to `.iter_segments`.
433+
434+
Yields
435+
------
436+
B : matplotlib.bezier.BezierSegment
437+
The bezier curves that make up the current path. Note in particular
438+
that freestanding points are bezier curves of order 0, and lines
439+
are bezier curves of order 1 (with two control points).
440+
code : Path.code_type
441+
The code describing what kind of curve is being returned.
442+
Path.MOVETO, Path.LINETO, Path.CURVE3, Path.CURVE4 correspond to
443+
bezier curves with 1, 2, 3, and 4 control points (respectively).
444+
Path.CLOSEPOLY is a Path.LINETO with the control points correctly
445+
chosen based on the start/end points of the current stroke.
446+
"""
447+
first_vert=None
448+
prev_vert=None
449+
forverts,codeinself.iter_segments(**kwargs):
450+
iffirst_vertisNone:
451+
ifcode!=Path.MOVETO:
452+
raiseValueError("Malformed path, must start with MOVETO.")
453+
ifcode==Path.MOVETO:# a point is like "CURVE1"
454+
first_vert=verts
455+
yieldBezierSegment(np.array([first_vert])),code
456+
elifcode==Path.LINETO:# "CURVE2"
457+
yieldBezierSegment(np.array([prev_vert,verts])),code
458+
elifcode==Path.CURVE3:
459+
yieldBezierSegment(np.array([prev_vert,verts[:2],
460+
verts[2:]])),code
461+
elifcode==Path.CURVE4:
462+
yieldBezierSegment(np.array([prev_vert,verts[:2],
463+
verts[2:4],verts[4:]])),code
464+
elifcode==Path.CLOSEPOLY:
465+
yieldBezierSegment(np.array([prev_vert,first_vert])),code
466+
elifcode==Path.STOP:
467+
return
468+
else:
469+
raiseValueError("Invalid Path.code_type: "+str(code))
470+
prev_vert=verts[-2:]
471+
424472
@cbook._delete_parameter("3.3","quantize")
425473
defcleaned(self,transform=None,remove_nans=False,clip=None,
426474
quantize=False,simplify=False,curves=False,
@@ -529,22 +577,32 @@ def contains_path(self, path, transform=None):
529577
transform=transform.frozen()
530578
return_path.path_in_path(self,None,path,transform)
531579

532-
defget_extents(self,transform=None):
580+
defget_extents(self,transform=None,**kwargs):
533581
"""
534-
Return the extents (*xmin*, *ymin*, *xmax*, *ymax*) of the path.
582+
Get Bbox of the path.
535583
536-
Unlike computing the extents on the *vertices* alone, this
537-
algorithm will take into account the curves and deal with
538-
control points appropriately.
584+
Parameters
585+
----------
586+
transform : matplotlib.transforms.Transform, optional
587+
Transform to apply to path before computing extents, if any.
588+
**kwargs
589+
Forwarded to `.iter_bezier`.
590+
591+
Returns
592+
-------
593+
matplotlib.transforms.Bbox
594+
The extents of the path Bbox([[xmin, ymin], [xmax, ymax]])
539595
"""
540596
from .transformsimportBbox
541-
path=self
542597
iftransformisnotNone:
543-
transform=transform.frozen()
544-
ifnottransform.is_affine:
545-
path=self.transformed(transform)
546-
transform=None
547-
returnBbox(_path.get_path_extents(path,transform))
598+
self=transform.transform_path(self)
599+
bbox=Bbox.null()
600+
forcurve,codeinself.iter_bezier(**kwargs):
601+
# places where the derivative is zero can be extrema
602+
_,dzeros=curve.axis_aligned_extrema()
603+
# as can the ends of the curve
604+
bbox.update_from_data_xy(curve([0,*dzeros,1]),ignore=False)
605+
returnbbox
548606

549607
defintersects_path(self,other,filled=True):
550608
"""

‎lib/matplotlib/tests/test_path.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,37 @@ def test_contains_points_negative_radius():
4949
np.testing.assert_equal(result, [True,False,False])
5050

5151

52+
_test_paths= [
53+
# interior extrema determine extents and degenerate derivative
54+
Path([[0,0], [1,0], [1,1], [0,1]],
55+
[Path.MOVETO,Path.CURVE4,Path.CURVE4,Path.CURVE4]),
56+
# a quadratic curve
57+
Path([[0,0], [0,1], [1,0]], [Path.MOVETO,Path.CURVE3,Path.CURVE3]),
58+
# a linear curve, degenerate vertically
59+
Path([[0,1], [1,1]], [Path.MOVETO,Path.LINETO]),
60+
# a point
61+
Path([[1,2]], [Path.MOVETO]),
62+
]
63+
64+
65+
_test_path_extents= [(0.,0.,0.75,1.), (0.,0.,1.,0.5), (0.,1.,1.,1.),
66+
(1.,2.,1.,2.)]
67+
68+
69+
@pytest.mark.parametrize('path, extents',zip(_test_paths,_test_path_extents))
70+
deftest_exact_extents(path,extents):
71+
# notice that if we just looked at the control points to get the bounding
72+
# box of each curve, we would get the wrong answers. For example, for
73+
# hard_curve = Path([[0, 0], [1, 0], [1, 1], [0, 1]],
74+
# [Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4])
75+
# we would get that the extents area (0, 0, 1, 1). This code takes into
76+
# account the curved part of the path, which does not typically extend all
77+
# the way out to the control points.
78+
# Note that counterintuitively, path.get_extents() returns a Bbox, so we
79+
# have to get that Bbox's `.extents`.
80+
assertnp.all(path.get_extents().extents==extents)
81+
82+
5283
deftest_point_in_path_nan():
5384
box=np.array([[0,0], [1,0], [1,1], [0,1], [0,0]])
5485
p=Path(box)

‎lib/matplotlib/transforms.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -847,8 +847,8 @@ def ignore(self, value):
847847

848848
defupdate_from_path(self,path,ignore=None,updatex=True,updatey=True):
849849
"""
850-
Update the bounds of the `Bbox`based on thepassed in
851-
data. After updating, the bounds will have positive *width*
850+
Update the bounds of the `Bbox`to contain thevertices of the
851+
provided path. After updating, the bounds will have positive *width*
852852
and *height*; *x0* and *y0* will be the minimal values.
853853
854854
Parameters

0 commit comments

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