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 d7084de

Browse filesBrowse files
brunobeltranbrunobeltran
committed
correctly compute bounding box for path
1 parent 696b64c commit d7084de
Copy full SHA for d7084de

File tree

Expand file treeCollapse file tree

3 files changed

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

3 files changed

+199
-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
+90-1Lines changed: 90 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,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.