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 63ec774

Browse filesBrowse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 09f98da commit 63ec774
Copy full SHA for 63ec774

File tree

Expand file treeCollapse file tree

3 files changed

+197
-9
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+197
-9
lines changed

‎lib/matplotlib/bezier.py

Copy file name to clipboardExpand all lines: lib/matplotlib/bezier.py
+103-8Lines 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-
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 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

Copy file name to clipboardExpand all lines: lib/matplotlib/path.py
+88-1Lines 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

Copy file name to clipboardExpand all lines: lib/matplotlib/tests/test_path.py
+6Lines 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)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.