8000 correctly compute bounding box for path · matplotlib/matplotlib@b1732b6 · GitHub
[go: up one dir, main page]
Skip to content

Commit b1732b6

Browse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 1259895 commit b1732b6

File tree

5 files changed

+251
-24
lines changed

5 files changed

+251
-24
lines changed

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

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: 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

Lines 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 = transform.transform_path(self)
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]), ignore=False)
604+
return bbox
547605

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

‎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+
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

Lines 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