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

Commit b29f403

Browse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 348e9fe commit b29f403

File tree

4 files changed

+232
-19
lines changed

4 files changed

+232
-19
lines changed

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

Lines 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

Lines 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

Lines 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+
< 10000 span class=pl-s> ----------
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

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)

0 commit comments

Comments
 (0)
0