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

Commit 225b1f8

Browse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 696b64c commit 225b1f8

File tree

3 files changed

+197
-9
lines changed

3 files changed

+197
-9
lines changed

‎lib/matplotlib/bezier.py

Lines changed: 103 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
@@ -177,27 +185,114 @@ def find_bezier_t_intersecting_with_closedpath(
177185

178186
class BezierSegment:
179187
"""
180-
A D-dimensional Bezier segment.
188+
A d-dimensional Bezier segment.
181189
182190
Parameters
183191
----------
184-
control_points : (N, D) array
192+
control_points : (N, d) array
185193
Location of the *N* control points.
186194
"""
187195

188196
def __init__(self, control_points):
189-
n = len(control_points)
190-
self._orders = np.arange(n)
191-
coeff = [math.factorial(n - 1)
192-
// (math.factorial(i) * math.factorial(n - 1 - i))
193< 8000 /code>-
for i in range(n)]
194-
self._px = np.asarray(control_points).T * coeff
197+
self._cpoints = np.asarray(control_points)
198+
self._N, self._d = self._cpoints.shape
199+
self._orders = np.arange(self._N)
200+
coeff = [math.factorial(self._N - 1)
201+
// (math.factorial(i) * math.factorial(self._N - 1 - i))
202+
for i in range(self._N)]
203+
self._px = self._cpoints.T * coeff
204+
205+
def __call__(self, t):
206+
return self.point_at_t(t)
195207

196208
def point_at_t(self, t):
197209
"""Return the point on the Bezier curve for parameter *t*."""
198210
return tuple(
199211
self._px @ (((1 - t) ** self._orders)[::-1] * t ** self._orders))
200212

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

202297
def split_bezier_intersecting_with_closedpath(
203298
bezier, inside_closedpath, tolerance=0.01):

‎lib/matplotlib/path.py

Lines changed: 88 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +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 split_bezier_intersecting_with_closedpath
20+
from .bezier import BezierSegment, split_bezier_intersecting_with_closedpath
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
2132

2233

2334
class Path:
@@ -421,6 +432,53 @@ def iter_segments(self, transform=None, remove_nans=True, clip=None,
421432
curr_vertices = np.append(curr_vertices, next(vertices))
422433
yield curr_vertices, code
423434

435+
def iter_bezier(self, **kwargs):
436+
"""
437+
Iterate over each bezier curve (lines included) in a Path.
438+
439+
Parameters
440+
----------
441+
kwargs : Dict[str, object]
442+
Forwareded 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 vertices, 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 = vertices
465+
yield BezierSegment(np.array([first_vert])), code
466+
elif code == Path.LINETO: # "CURVE2"
467+
yield BezierSegment(np.array([prev_vert, vertices])), code
468+
elif code == Path.CURVE3:
469+
yield BezierSegment(np.array([prev_vert, vertices[:2],
470+
vertices[2:]])), code
471+
elif code == Path.CURVE4:
472+
yield BezierSegment(np.array([prev_vert, vertices[:2],
473+
vertices[2:4], vertices[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 = vertices[-2:]
481+
424482
@cbook._delete_parameter("3.3", "quantize")
425483
def cleaned(self, transform=None, remove_nans=False, clip=None,
426484
quantize=False, simplify=False, curves=False,
@@ -546,6 +604,35 @@ def get_extents(self, transform=None):
546604
transform = None
547605
return Bbox(_path.get_path_extents(path, transform))
548606

607+
def get_exact_extents(self, **kwargs):
608+
"""Get size of Bbox of curve (instead of Bbox of control points).
609+
610+
Parameters
611+
----------
612+
kwargs : Dict[str, object]
613+
Forwarded to self.iter_bezier.
614+
615+
Returns
616+
-------
617+
extents : (4,) float, array_like
618+
The extents of the path (xmin, ymin, xmax, ymax).
619+
"""
620+
maxi = 2 # [xmin, ymin, *xmax, ymax]
621+
# return value for empty paths to match _path.h
622+
extents = np.array([np.inf, np.inf, -np.inf, -np.inf])
623+
for curve, code in self.iter_bezier(**kwargs):
624+
# start and endpoints can be extrema of the curve
625+
_update_extents(extents, curve(0)) # start point
626+
_update_extents(extents, curve(1)) # end point
627+
# interior extrema where d/ds B(s) == 0
628+
_, dzeros = curve.axis_aligned_extrema
629+
if len(dzeros) == 0:
630+
continue
631+
for zero in dzeros:
632+
potential_extrema = curve.point_at_t(zero)
633+
_update_extents(extents, potential_extrema)
634+
return extents
635+
549636
def intersects_path(self, other, filled=True):
550637
"""
551638
Returns *True* if this path intersects another given path.

‎lib/matplotlib/tests/test_path.py

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

5151

52+
def test_exact_extents_cubic():
53+
hard_curve = Path([[0, 0], [1, 0], [1, 1], [0, 1]],
54+
[Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4])
55+
np.testing.assert_equal(hard_curve.get_exact_extents(), [0., 0., 0.75, 1.])
56+
57+
5258
def test_point_in_path_nan():
5359
box = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]])
5460
p = Path(box)

0 commit comments

Comments
 (0)
0