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 97c748f

Browse filesBrowse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent fbc95f8 commit 97c748f
Copy full SHA for 97c748f

File tree

Expand file treeCollapse file tree

3 files changed

+200
-10
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+200
-10
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
@@ -216,27 +224,114 @@ def find_bezier_t_intersecting_with_closedpath(
216224

217225
class BezierSegment:
218226
"""
219-
A D-dimensional Bezier segment.
227+
A d-dimensional Bezier segment.
220228
221229
Parameters
222230
----------
223-
control_points : (N, D) array
231+
control_points : (N, d) array
224232
Location of the *N* control points.
225233
"""
226234

227235
def __init__(self, control_points):
228-
n = len(control_points)
229-
self._orders = np.arange(n)
230-
coeff = [math.factorial(n - 1)
231-
// (math.factorial(i) * math.factorial(n - 1 - i))
232-
for i in range(n)]
233-
self._px = np.asarray(control_points).T * coeff
236+
self._cpoints = np.asarray(control_points)
237+
self._N, self._d = self._cpoints.shape
238+
self._orders = np.arange(self._N)
239+
coeff = [math.factorial(self._N - 1)
240+
// (math.factorial(i) * math.factorial(self._N - 1 - i))
241+
for i in range(self._N)]
242+
self._px = self._cpoints.T * coeff
243+
244+
def __call__(self, t):
245+
return self.point_at_t(t)
234246

235247
def point_at_t(self, t):
236248
"""Return the point on the Bezier curve for parameter *t*."""
237249
return tuple(
238250
self._px @ (((1 - t) ** self._orders)[::-1] * t ** self._orders))
239251

252+
@property
253+
def control_points(self):
254+
"""The control points of the curve."""
255+
return self._cpoints
256+
257+
@property
258+
def dimension(self):
259+
"""The dimension of the curve."""
260+
return self._d
261+
262+
@property
263+
def degree(self):
264+
"""The number of control points in the curve."""
265+
return self._N - 1
266+
267+
@property
268+
def polynomial_coefficients(self):
269+
r"""The polynomial coefficients of the Bezier curve.
270+
271+
Returns
272+
-------
273+
coefs : float, (n+1, d) array_like
274+
Coefficients after expanding in polynomial basis, where :math:`n`
275+
is the degree of the bezier curve and :math:`d` its dimension.
276+
These are the numbers (:math:`C_j`) such that the curve can be
277+
written :math:`\sum_{j=0}^n C_j t^j`.
278+
279+
Notes
280+
-----
281+
The coefficients are calculated as
282+
283+
.. math::
284+
285+
{n \choose j} \sum_{i=0}^j (-1)^{i+j} {j \choose i} P_i
286+
287+
where :math:`P_i` are the control points of the curve.
288+
"""
289+
n = self.degree
290+
# matplotlib uses n <= 4. overflow plausible starting around n = 15.
291+
if n > 10:
292+
warnings.warn("Polynomial coefficients formula unstable for high "
293+
"order Bezier curves!", RuntimeWarning)
294+
d = self.dimension
295+
P = self.control_points
296+
coefs = np.zeros((n+1, d))
297+
for j in range(n+1):
298+
i = np.arange(j+1)
299+
prefactor = np.power(-1, i + j) * _comb(j, i)
300+
prefactor = np.tile(prefactor, (d, 1)).T
301+
coefs[j] = _comb(n, j) * np.sum(prefactor*P[i], axis=0)
302+
return coefs
303+
304+
@property
305+
def axis_aligned_extrema(self):
306+
"""
307+
Return the location along the curve's interior where its partial
308+
derivative is zero, along with the dimension along which it is zero for
309+
each such instance.
310+
311+
Returns
312+
-------
313+
dims : int, array_like
314+
dimension :math:`i` along which the corresponding zero occurs
315+
dzeros : float, array_like
316+
of same size as dims. the :math:`t` such that :math:`d/dx_i B(t) =
317+
0`
318+
"""
319+
n = self.degree
320+
Cj = self.polynomial_coefficients
321+
dCj = np.atleast_2d(np.arange(1, n+1)).T * Cj[1:]
322+
if len(dCj) == 0:
323+
return np.array([]), np.array([])
324+
dims = []
325+
roots = []
326+
for i, pi in enumerate(dCj.T):
327+
r = np.roots(pi[::-1])
328+
roots.append(r)
329+
dims.append(i*np.ones_like(r))
330+
roots = np.concatenate(roots)
331+
dims = np.concatenate(dims)
332+
in_range = np.isreal(roots) & (roots >= 0) & (roots <= 1)
333+
return dims[in_range], np.real(roots)[in_range]
334+
240335

241336
def split_bezier_intersecting_with_closedpath(
242337
bezier, inside_closedpath, tolerance=0.01):

‎lib/matplotlib/path.py

Copy file name to clipboardExpand all lines: lib/matplotlib/path.py
+91-2Lines changed: 91 additions & 2 deletions
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:
@@ -339,7 +350,7 @@ def make_compound_path(cls, *args):
339350
for path in args:
340351
if path.codes is None:
341352
codes[i] = cls.MOVETO
342-
codes[i + 1:i + len(codes)] = cls.LINETO
353+
codes[i + 1:i + len(path.vertices)] = cls.LINETO
343354
else:
344355
codes[i:i + len(path.codes)] = path.codes
345356
i += len(path.vertices)
@@ -421,6 +432,54 @@ 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_curves(self, **kwargs):
436+
"""
437+
Iterate over each bezier curve (lines included) in a Path.
438+
439+
This is in contrast to iter_segments, which omits the first control
440+
point of each curve.
441+
442+
Parameters
443+
----------
444+
kwargs : Dict[str, object]
445+
Forwareded to iter_segments.
446+
447+
Yields
448+
------
449+
vertices : float, (N, 2) array_like
450+
The N control points of the next 2-dimensional bezier curve making
451+
up self. Note in particular that freestanding points are bezier
452+
curves of order 0, and lines are bezier curves of order 1 (with two
453+
control points).
454+
code : Path.code_type
455+
The code describing what kind of curve is being returned.
456+
Path.MOVETO, Path.LINETO, Path.CURVE3, Path.CURVE4 correspond to
457+
bezier curves with 1, 2, 3, and 4 control points (respectively).
458+
"""
459+
first_vertex = None
460+
prev_vertex = None
461+
for vertices, code in self.iter_segments(**kwargs):
462+
if first_vertex is None:
463+
if code != Path.MOVETO:
464+
raise ValueError("Malformed path, must start with MOVETO.")
465+
if code == Path.MOVETO: # a point is like "CURVE1"
466+
first_vertex = vertices
467+
yield np.array([first_vertex]), code
468+
elif code == Path.LINETO: # "CURVE2"
469+
yield np.array([prev_vertex, vertices]), code
470+
elif code == Path.CURVE3:
471+
yield np.array([prev_vertex, vertices[:2], vertices[2:]]), code
472+
elif code == Path.CURVE4:
473+
yield np.array([prev_vertex, vertices[:2], vertices[2:4],
474+
vertices[4:]]), code
475+
elif code == Path.CLOSEPOLY:
476+
yield np.array([prev_vertex, first_vertex]), code
477+
elif code == Path.STOP:
478+
return
479+
else:
480+
raise ValueError("Invalid Path.code_type: " + str(code))
481+
prev_vertex = vertices[-2:]
482+
424483
@cbook._delete_parameter("3.3", "quantize")
425484
def cleaned(self, transform=None, remove_nans=False, clip=None,
426485
quantize=False, simplify=False, curves=False,
@@ -546,6 +605,36 @@ def get_extents(self, transform=None):
546605
transform = None
547606
return Bbox(_path.get_path_extents(path, transform))
548607

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