test new exact path bbox code

brunobeltran · brunobeltran · commit 9c69a534cc1d · 2020-03-20T10:48:47.000-07:00
diff --git a/lib/matplotlib/bezier.py b/lib/matplotlib/bezier.py
@@ -238,6 +238,57 @@ def point_at_t(self, t):
         return tuple(
             self._px @ (((1 - t) ** self._orders)[::-1] * t ** self._orders))
 
+    def __call__(self, t):
+        return self.point_at_t(t)
+
+    @property
+    def interior_extrema(self):
+        """
+        Return the location along the curve's interior where its partial derivative is
+        zero, along with the dimension along which it is zero for each
+        instance.
+
+        Returns
+        -------
+        dims : int, array_like
+            dimension $i$ along which the corresponding zero occurs
+        dzeros : float, array_like
+            of same size as dims. the $t$ such that $d/dx_i B(t) = 0$
+        """
+        if self.n <= 2:  # a line's extrema are always its tips
+            p = [0]  # roots returns empty array for zero polynomial
+            return np.array([]), np.array([])
+        elif self.n == 3:  # quadratic curve
+            # the bezier curve in standard form is
+            # cp[0] * (1 - t)^2 + cp[1] * 2t(1-t) + cp[2] * t^2
+            # can be re-written as
+            # cp[0] + 2 (cp[1] - cp[0]) t + (cp[2] - 2 cp[1] + cp[0]) t^2
+            # which has simple derivative
+            # 2*(cp[2] - 2*cp[1] + cp[0]) t + 2*(cp[1] - cp[0])
+            p = [2*(self.cpoints[2] - 2*self.cpoints[1] + self.cpoints[0]),
+                 2*(self.cpoints[1] - self.cpoints[0])]
+        elif self.n == 4:  # cubic curve
+            P = self.cpoints
+            # derivative of cubic bezier curve has coefficients
+            a = 3*(P[3] - 3*P[2] + 3*P[1] - P[0])
+            b = 6*(P[2] - 2*P[1] + P[0])
+            c = 3*(P[1] - P[0])
+            p = [a, b, c]
+        else:  # self.n > 4:
+            # a general formula exists, but is not useful for matplotlib
+            raise NotImplementedError("Zero finding only implemented up to "
+                                      "cubic curves.")
+        dims = []
+        roots = []
+        for i, pi in enumerate(np.array(p).T):
+            r = np.roots(pi)
+            roots.append(r)
+            dims.append(i*np.ones_like(r))
+        roots = np.concatenate(roots)
+        dims = np.concatenate(dims)
+        in_range = np.isreal(roots) & (roots > 0) & (roots < 1)
+        return dims[in_range], np.real(roots)[in_range]
+
 
 def split_bezier_intersecting_with_closedpath(
         bezier, inside_closedpath, tolerance=0.01):
diff --git a/lib/matplotlib/path.py b/lib/matplotlib/path.py
@@ -17,7 +17,18 @@
 import matplotlib as mpl
 from . import _path, cbook
 from .cbook import _to_unmasked_float_array, simple_linear_interpolation
-from .bezier import split_bezier_intersecting_with_closedpath
+from .bezier import BezierSegment, split_bezier_intersecting_with_closedpath
+
+
+def _update_extents(extents, point):
+    dim = len(point)
+    for i,xi in enumerate(point):
+        if xi < extents[i]:
+            extents[i] = xi
+        # elif here would fail to correctly update from "null" extents of
+        # np.array([np.inf, np.inf, -np.inf, -np.inf])
+        if extents[i+dim] < xi:
+            extents[i+dim] = xi
 
 
 class Path:
@@ -422,6 +433,54 @@ def iter_segments(self, transform=None, remove_nans=True, clip=None,
                     curr_vertices = np.append(curr_vertices, next(vertices))
             yield curr_vertices, code
 
+    def iter_curves(self, **kwargs):
+        """
+        Iterate over each bezier curve (lines included) in a Path.
+
+        This is in contrast to iter_segments, which omits the first control
+        point of each curve.
+
+        Parameters
+        ----------
+        kwargs : Dict[str, object]
+            Forwareded to iter_segments.
+
+        Yields
+        ------
+        vertices : float, (N, 2) array_like
+            The N control points of the next 2-dimensional bezier curve making
+            up self. Note in particular that freestanding points are bezier
+            curves of order 0, and lines are bezier curves of order 1 (with two
+            control points).
+        code : Path.code_type
+            The code describing what kind of curve is being returned.
+            Path.MOVETO, Path.LINETO, Path.CURVE3, Path.CURVE4 correspond to
+            bezier curves with 1, 2, 3, and 4 control points (respectively).
+        """
+        first_vertex = None
+        prev_vertex = None
+        for vertices, code in self.iter_segments(**kwargs):
+            if first_vertex is None:
+                if code != Path.MOVETO:
+                    raise ValueError("Malformed path, must start with MOVETO.")
+            if code == Path.MOVETO:  # a point is like "CURVE1"
+                first_vertex = vertices
+                yield np.array([first_vertex]), code
+            elif code == Path.LINETO:  # "CURVE2"
+                yield np.array([prev_vertex, vertices]), code
+            elif code == Path.CURVE3:
+                yield np.array([prev_vertex, vertices[:2], vertices[2:]]), code
+            elif code == Path.CURVE4:
+                yield np.array([prev_vertex, vertices[:2], vertices[2:4],
+                                vertices[4:]]), code
+            elif code == Path.CLOSEPOLY:
+                yield np.array([prev_vertex, first_vertex]), code
+            elif code == Path.STOP:
+                return
+            else:
+                raise ValueError("Invalid Path.code_type: " + str(code))
+            prev_vertex = vertices[-2:]
+
     @cbook._delete_parameter("3.3", "quantize")
     def cleaned(self, transform=None, remove_nans=False, clip=None,
                 quantize=False, simplify=False, curves=False,
@@ -547,6 +606,36 @@ def get_extents(self, transform=None):
                 transform = None
         return Bbox(_path.get_path_extents(path, transform))
 
+    def get_exact_extents(self, **kwargs):
+        """Get size of Bbox of curve (instead of Bbox of control points).
+
+        Parameters
+        ----------
+        kwargs : Dict[str, object]
+            Forwarded to self.iter_curves.
+
+        Returns
+        -------
+        extents : (4,) float, array_like
+            The extents of the path (xmin, ymin, xmax, ymax).
+        """
+        maxi = 2  # [xmin, ymin, *xmax, ymax]
+        # return value for empty paths to match _path.h
+        extents = np.array([np.inf, np.inf, -np.inf, -np.inf])
+        for curve, code in self.iter_curves(**kwargs):
+            curve = BezierSegment(curve)
+            # start and endpoints can be extrema of the curve
+            _update_extents(extents, curve(0))  # start point
+            _update_extents(extents, curve(1))  # end point
+            # interior extrema where d/ds B(s) == 0
+            _, dzeros = curve.interior_extrema
+            if len(dzeros) == 0:
+                continue
+            for zero in dzeros:
+                potential_extrema = curve.point_at_t(zero)
+                _update_extents(extents, potential_extrema)
+        return extents
+
     def intersects_path(self, other, filled=True):
         """
         Returns *True* if this path intersects another given path.
diff --git a/lib/matplotlib/tests/test_path.py b/lib/matplotlib/tests/test_path.py
@@ -49,6 +49,15 @@ def test_contains_points_negative_radius():
     np.testing.assert_equal(result, [True, False, False])
 
 
+def test_exact_extents_cubic():
+    hard_curve = Path([[0, 0],
+                    [1, 0], [1, 1], [0, 1]],
+                    [Path.MOVETO,
+                    Path.CURVE4, Path.CURVE4, Path.CURVE4])
+    np.testing.assert_equal(hard_curve.get_exact_extents(),
+                            [0., 0., 0.75, 1.])
+
+
 def test_point_in_path_nan():
     box = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]])
     p = Path(box)
