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 ad22228

Browse filesBrowse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 348e9fe commit ad22228
Copy full SHA for ad22228

File tree

Expand file treeCollapse file tree

4 files changed

+229
-19
lines changed
Filter options
Expand file treeCollapse file tree

4 files changed

+229
-19
lines changed

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

Copy file name to clipboard
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
2+
Path extents now computed correctly
3+
-----------------------------------
4+
5+
Historically, `~.path.Path.get_extents` has always simply returned the Bbox of
6+
its control points. While this is a correct upper bound for the path's extents,
7+
it can differ dramatically from the Path's actual extents for non-linear Bezier
8+
curves.
9+
10+
In addition, `~.bezier.BezierSegment` has gained more documentation and
11+
usability improvements, including properties that contain its dimension, degree,
12+
control_points, and more.

‎lib/matplotlib/bezier.py

Copy file name to clipboardExpand all lines: lib/matplotlib/bezier.py
+102-8Lines changed: 102 additions & 8 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,27 +176,113 @@ 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
186195

187196
def point_at_t(self, t):
188197
"""Return the point on the Bezier curve for parameter *t*."""
189198
return tuple(
190199
self._px @ (((1 - t) ** self._orders)[::-1] * t ** self._orders))
191200

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

193287
def split_bezier_intersecting_with_closedpath(
194288
bezier, inside_closedpath, tolerance=0.01):

‎lib/matplotlib/path.py

Copy file name to clipboardExpand all lines: lib/matplotlib/path.py
+87-11Lines changed: 87 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,18 @@
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
21+
22+
23+
def _update_extents(extents, point):
24+
dim = len(point)
25+
for i, xi in enumerate(point):
26+
if xi < extents[i]:
27+
extents[i] = xi
28+
# elif here would fail to correctly update from "null" extents of
29+
# np.array([np.inf, np.inf, -np.inf, -np.inf])
30+
if extents[i+dim] < xi:
31+
extents[i+dim] = xi
2032

2133

2234
class Path:
@@ -420,6 +432,53 @@ def iter_segments(self, transform=None, remove_nans=True, clip=None,
420432
curr_vertices = np.append(curr_vertices, next(vertices))
421433
yield curr_vertices, code
422434

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

531-
def get_extents(self, transform=None):
590+
def get_extents(self, transform=None, **kwargs):
532591
"""
533-
Return the extents (*xmin*, *ymin*, *xmax*, *ymax*) of the path.
592+
Get Bbox of the path.
534593
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.
594+
Parameters
595+
----------
596+
transform : matplotlib.transforms.Transform, optional
597+
Transform to apply to path before computing extents, if any.
598+
**kwargs
599+
Forwarded to `.iter_bezier`.
600+
601+
Returns
602+
-------
603+
matplotlib.transforms.Bbox
604+
The extents of the path Bbox([[xmin, ymin], [xmax, ymax]])
538605
"""
539606
from .transforms import Bbox
540-
path = self
541607
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))
608+
self = transform.transform_path(self)
609+
# return value for empty paths to match what used to be done in _path.h
610+
extents = np.array([np.inf, np.inf, -np.inf, -np.inf])
611+
for curve, code in self.iter_bezier(**kwargs):
612+
# start and endpoints can be extrema of the curve
613+
_update_extents(extents, curve.point_at_t(0)) # start point
614+
_update_extents(extents, curve.point_at_t(1)) # end point
615+
# interior extrema where d/ds B(s) == 0
616+
_, dzeros = curve.axis_aligned_extrema
617+
if len(dzeros) == 0:
618+
continue
619+
for ti in dzeros:
620+
potential_extrema = curve.point_at_t(ti)
621+
_update_extents(extents, potential_extrema)
622+
return Bbox.from_extents(extents)
547623

548624
def intersects_path(self, other, filled=True):
549625
"""

‎lib/matplotlib/tests/test_path.py

Copy file name to clipboardExpand all lines: lib/matplotlib/tests/test_path.py
+28Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,21 @@
1313
from matplotlib import transforms
1414
from matplotlib.backend_bases import MouseEvent
1515

16+
# (extents, Path) pairs
17+
_test_curves = [
18+
# interior extrema determine extents and degenerate derivative
19+
((0., 0., 0.75, 1.),
20+
Path([[0, 0], [1, 0], [1, 1], [0, 1]],
21+
[Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4])),
22+
# a quadratic curve
23+
((0., 0., 1., 0.5),
24+
Path([[0, 0], [0, 1], [1, 0]], [Path.MOVETO, Path.CURVE3, Path.CURVE3])),
25+
# a linear curve, degenerate vertically
26+
((0., 1., 1., 1.), Path([[0, 1], [1, 1]], [Path.MOVETO, Path.LINETO])),
27+
# a point
28+
((1., 2., 1., 2.), Path([[1, 2]], [Path.MOVETO])),
29+
]
30+
1631

1732
def test_empty_closed_path():
1833
path = Path(np.zeros((0, 2)), closed=True)
@@ -49,6 +64,19 @@ def test_contains_points_negative_radius():
4964
np.testing.assert_equal(result, [True, False, False])
5065

5166

67+
def test_exact_extents_cubic():
68+
# notice that if we just looked at the control points to get the bounding
69+
# box of each curve, we would get the wrong answers. For example, for
70+
# hard_curve = Path([[0, 0], [1, 0], [1, 1], [0, 1]],
71+
# [Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4])
72+
# we would get that the extents area (0, 0, 1, 1). This code takes into
73+
# account the curved part of the path, which does not typically extend all
74+
# the way out to the control points
75+
for extents, path in _test_curves:
76+
# historically, path.get_extents() returns a Bbox
77+
assert np.all(path.get_extents().extents == extents)
78+
79+
5280
def test_point_in_path_nan():
5381
box = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]])
5482
p = Path(box)

0 commit comments

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