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
Appearance settings

Commit 9161982

Browse filesBrowse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 1259895 commit 9161982
Copy full SHA for 9161982

File tree

Expand file treeCollapse file tree

5 files changed

+251
-24
lines changed
Filter options
Expand file treeCollapse file tree

5 files changed

+251
-24
lines changed

‎doc/users/next_whats_new/2020-03-31-path-size-methods.rst

Copy file name to clipboard
+27Lines 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

Copy file name to clipboardExpand all lines: lib/matplotlib/bezier.py
+122-11Lines changed: 122 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -3,11 +3,19 @@
33
"""
44

55
import math
6+
import warnings
67

78
import numpy as np
89

910
import matplotlib.cbook as cbook
1011

12+
# same algorithm as 3.8's math.comb
13+
@np.vectorize
14+
def _comb(n, k):
15+
k = min(k, n - k)
16+
i = np.arange(1, k + 1)
17+
return np.prod((n + 1 - i)/i).astype(int)
18+
1119

1220
class NonIntersectingPathException(ValueError):
1321
pass
@@ -168,26 +176,129 @@ def find_bezier_t_intersecting_with_closedpath(
168176

169177
class BezierSegment:
170178
"""
171-
A D-dimensional Bezier segment.
179+
A d-dimensional Bezier segment.
172180
173181
Parameters
174182
----------
175-
control_points : (N, D) array
183+
control_points : (N, d) array
176184
Location of the *N* control points.
177185
"""
178186

179187
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-
for i in range(n)]
185-
self._px = np.asarray(control_points).T * coeff
188+
self._cpoints = np.asarray(control_points)
189+
self._N, self._d = self._cpoints.shape
190+
self._orders = np.arange(self._N)
191+
coeff = [math.factorial(self._N - 1)
192+
// (math.factorial(i) * math.factorial(self._N - 1 - i))
193+
for i in range(self._N)]
194+
self._px = (self._cpoints.T * coeff).T
195+
196+
def __call__(self, t):
197+
"""
198+
Evaluate the Bezier curve at point(s) t in [0, 1].
199+
200+
Parameters
201+
----------
202+
t : float (k,), array_like
203+
Points at which to evaluate the curve.
204+
205+
Returns
206+
-------
207+
float (k, d), array_like
208+
Value of the curve for each point in *t*.
209+
"""
210+
t = np.asarray(t)
211+
return (np.power.outer(1 - t, self._orders[::-1])
212+
* np.power.outer(t, self._orders)) @ self._px
186213

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

192303

193304
def split_bezier_intersecting_with_closedpath(

‎lib/matplotlib/path.py

Copy file name to clipboardExpand all lines: lib/matplotlib/path.py
+69-11Lines changed: 69 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
import matplotlib as mpl
1818
from . import _path, cbook
1919
from .cbook import _to_unmasked_float_array, simple_linear_interpolation
20+
from .bezier import BezierSegment
2021

2122

2223
class Path:
@@ -420,6 +421,53 @@ def iter_segments(self, transform=None, remove_nans=True, clip=None,
420421
curr_vertices = np.append(curr_vertices, next(vertices))
421422
yield curr_vertices, code
422423

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

531-
def get_extents(self, transform=None):
579+
def get_extents(self, transform=None, **kwargs):
532580
"""
533-
Return the extents (*xmin*, *ymin*, *xmax*, *ymax*) of the path.
581+
Get Bbox of the path.
534582
535-
Unlike computing the extents on the *vertices* alone, this
536-
algorithm will take into account the curves and deal with
537-
control points appropriately.
583+
Parameters
584+
----------
585+
transform : matplotlib.transforms.Transform, optional
586+
Transform to apply to path before computing extents, if any.
587+
**kwargs
588+
Forwarded to `.iter_bezier`.
589+
590+
Returns
591+
-------
592+
matplotlib.transforms.Bbox
593+
The extents of the path Bbox([[xmin, ymin], [xmax, ymax]])
538594
"""
539595
from .transforms import Bbox
540-
path = self
541596
if transform is not None:
542-
transform = transform.frozen()
543-
if not transform.is_affine:
544-
path = self.transformed(transform)
545-
transform = None
546-
return Bbox(_path.get_path_extents(path, transform))
597+
self = self.transformed(transform)
598+
bbox = Bbox.null()
599+
for curve, code in self.iter_bezier(**kwargs):
600+
# places where the derivative is zero can be extrema
601+
_, dzeros = curve.axis_aligned_extrema
602+
# as can the ends of the curve
603+
bbox.update_from_data_xy(curve([0, *dzeros, 1]))
604+
return bbox
547605

548606
def intersects_path(self, other, filled=True):
549607
"""

‎lib/matplotlib/tests/test_path.py

Copy file name to clipboardExpand all lines: lib/matplotlib/tests/test_path.py
+31Lines 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+
def test_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+
assert np.all(path.get_extents().extents == extents)
81+
82+
5283
def test_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

Copy file name to clipboardExpand all lines: lib/matplotlib/transforms.py
+2-2Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -775,8 +775,8 @@ def ignore(self, value):
775775

776776
def update_from_path(self, path, ignore=None, updatex=True, updatey=True):
777777
"""
778-
Update the bounds of the `Bbox` based on the passed in
779-
data. After updating, the bounds will have positive *width*
778+
Update the bounds of the `Bbox` to contain the vertices of the
779+
provided path. After updating, the bounds will have positive *width*
780780
and *height*; *x0* and *y0* will be the minimal values.
781781
782782
Parameters

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.