add function to compute (signed) area of path

brunobeltran · brunobeltran · commit 4cf12f3658da · 2020-03-30T18:39:31.000-07:00
diff --git a/lib/matplotlib/bezier.py b/lib/matplotlib/bezier.py
@@ -191,15 +191,114 @@ def __init__(self, control_points):
         coeff = [math.factorial(self._N - 1)
                  // (math.factorial(i) * math.factorial(self._N - 1 - i))
                  for i in range(self._N)]
-        self._px = self._cpoints.T * coeff
+        self._px = (self._cpoints.T * coeff).T
 
     def __call__(self, t):
-        return self.point_at_t(t)
+        t = np.array(t)
+        orders_shape = (1,)*t.ndim + self._orders.shape
+        t_shape = t.shape + (1,)  # self._orders.ndim == 1
+        orders = np.reshape(self._orders, orders_shape)
+        rev_orders = np.reshape(self._orders[::-1], orders_shape)
+        t = np.reshape(t, t_shape)
+        return ((1 - t)**rev_orders * t**orders) @ self._px
 
     def point_at_t(self, t):
         """Return the point on the Bezier curve for parameter *t*."""
-        return tuple(
-            self._px @ (((1 - t) ** self._orders)[::-1] * t ** self._orders))
+        return tuple(self(t))
+
+    def arc_area(self):
+        r"""
+        (Signed) area swept out by ray from origin to curve.
+
+        Notes
+        -----
+        A simple, analytical formula is possible for arbitrary bezier curves.
+
+        Given a bezier curve B(t), in order to calculate the area of the arc
+        swept out by the ray from the origin to the curve, we simply need to
+        compute :math:`\frac{1}{2}\int_0^1 B(t) \cdot n(t) dt`, where
+        :math:`n(t) = u^{(1)}(t) \hat{x}_0 - u{(0)}(t) \hat{x}_1` is the normal
+        vector oriented away from the origin and :math:`u^{(i)}(t) =
+        \frac{d}{dt} B^{(i)}(t)` is the :math:`i`th component of the curve's
+        tangent vector.  (This formula can be found by applying the divergence
+        theorem to :math:`F(x,y) = [x, y]/2`, and calculates the *signed* area
+        for a counter-clockwise curve, by the right hand rule).
+
+        The control points of the curve are just its coefficients in a
+        Bernstein expansion, so if we let :math:`P_i = [P^{(0)}_i, P^{(1)}_i]`
+        be the :math:`i`'th control point, then
+
+        .. math::
+
+            \frac{1}{2}\int_0^1 B(t) \cdot n(t) dt
+                   &= \frac{1}{2}\int_0^1 B^{(0)}(t) \frac{d}{dt} B^{(1)}(t)
+                                        - B^{(1)}(t) \frac{d}{dt} B^{(0)}(t)
+                                        dt \\
+                   &= \frac{1}{2}\int_0^1
+                        \left( \sum_{j=0}^n P_j^{(0)} b_{j,n} \right)
+                        \left( n \sum_{k=0}^{n-1} (P_{k+1}^{(1)} -
+                               P_{k}^{(1)}) b_{j,n} \right)
+                      \\
+                      &\hspace{1em} - \left( \sum_{j=0}^n P_j^{(1)} b_{j,n}
+                        \right) \left( n \sum_{k=0}^{n-1} (P_{k+1}^{(0)}
+                                     - P_{k}^{(0)}) b_{j,n} \right)
+                      dt,
+
+        where :math:`b_{\nu, n}(t) = {n \choose \nu} t^\nu {(1 - t)}^{n-\nu}`
+        is the :math:`\nu`'th Bernstein polynomial of degree :math:`n`.
+
+        Grouping :math:`t^l(1-t)^m` terms together for each :math:`l`,
+        :math:`m`, we get that the integrand becomes
+
+        .. math::
+
+            \sum_{j=0}^n \sum_{k=0}^{n-1}
+                {n \choose j} {{n - 1} \choose k}
+                &\left[P_j^{(0)} (P_{k+1}^{(1)} - P_{k}^{(1)})
+                    - P_j^{(1)} (P_{k+1}^{(0)} - P_{k}^{(0)})\right] \\
+                &\hspace{1em}\times{}t^{j + k} {(1 - t)}^{2n - 1 - j - k}
+
+        or just
+
+        .. math::
+
+            \sum_{j=0}^n \sum_{k=0}^{n-1}
+                \frac{{n \choose j} {{n - 1} \choose k}}
+                        {{{2n - 1} \choose {j+k}}}
+                [P_j^{(0)} (P_{k+1}^{(1)} - P_{k}^{(1)})
+                    - P_j^{(1)} (P_{k+1}^{(0)} - P_{k}^{(0)})]
+                b_{j+k,2n-1}(t).
+
+        Interchanging sum and integral, and using the fact that :math:`\int_0^1
+        b_{\nu, n}(t) dt = \frac{1}{n + 1}`, we conclude that the
+        original integral  can
+        simply be written as
+
+        .. math::
+
+            \frac{1}{2}&\int_0^1 B(t) \cdot n(t) dt
+            \\
+            &= \frac{1}{4}\sum_{j=0}^n \sum_{k=0}^{n-1}
+              \frac{{n \choose j} {{n - 1} \choose k}}
+                    {{{2n - 1} \choose {j+k}}}
+              [P_j^{(0)} (P_{k+1}^{(1)} - P_{k}^{(1)})
+             - P_j^{(1)} (P_{k+1}^{(0)} - P_{k}^{(0)})]
+        """
+        n = self.degree
+        area = 0
+        P = self.control_points
+        dP = np.diff(P, axis=0)
+        for j in range(n + 1):
+            for k in range(n):
+                area += _comb(n, j)*_comb(n-1, k)/_comb(2*n - 1, j + k) \
+                        * (P[j, 0]*dP[k, 1] - P[j, 1]*dP[k, 0])
+        return (1/4)*area
+
+    @classmethod
+    def differentiate(cls, B):
+        """Return the derivative of a BezierSegment, itself a BezierSegment"""
+        dcontrol_points = B.degree*np.diff(B.control_points, axis=0)
+        return cls(dcontrol_points)
 
     @property
     def control_points(self):
@@ -270,6 +369,7 @@ def axis_aligned_extrema(self):
         """
         n = self.degree
         Cj = self.polynomial_coefficients
+        # much faster than .differentiate(self).polynomial_coefficients
         dCj = np.atleast_2d(np.arange(1, n+1)).T * Cj[1:]
         if len(dCj) == 0:
             return np.array([]), np.array([])
diff --git a/lib/matplotlib/path.py b/lib/matplotlib/path.py
@@ -642,6 +642,41 @@ def intersects_bbox(self, bbox, filled=True):
         return _path.path_intersects_rectangle(
             self, bbox.x0, bbox.y0, bbox.x1, bbox.y1, filled)
 
+    def signed_area(self, **kwargs):
+        """
+        Get signed area filled by path.
+
+        All sub paths are treated as if they had been closed. That is, if there
+        is a MOVETO without a preceding CLOSEPOLY, one is added.
+
+        Signed area means that if a path is self-intersecting, the drawing rule
+        "even-odd" is used and only the filled area is counted.
+
+        Returns
+        -------
+        area : float
+            The (signed) enclosed area of the path.
+        """
+        area = 0
+        prev_point = None
+        prev_code = None
+        start_point = None
+        for B, code in self.iter_bezier(**kwargs):
+            if code == Path.MOVETO:
+                if prev_code is not None and prev_code is not Path.CLOSEPOLY:
+                    Bclose = BezierSegment(np.array([prev_point, start_point]))
+                    area += Bclose.arc_area()
+                start_point = B.control_points[0]
+            area += B.arc_area()
+            prev_point = B.control_points[-1]
+            prev_code = code
+        # add final implied CLOSEPOLY, if necessary
+        if start_point is not None \
+                and not np.all(np.isclose(start_point, prev_point)):
+            B = BezierSegment(np.array([prev_point, start_point]))
+            area += B.arc_area()
+        return area
+
     def interpolated(self, steps):
         """
         Return a new path resampled to length N x steps.
diff --git a/lib/matplotlib/tests/test_bezier.py b/lib/matplotlib/tests/test_bezier.py
@@ -0,0 +1,35 @@
+from matplotlib import bezier
+
+import numpy as np
+import scipy.integrate
+
+
+test_curves = [
+    # cubic, degenerate derivative
+    bezier.BezierSegment([[0, 0], [1, 0], [1, 1], [0, 1]]),
+    # cubic, could be quadratic
+    bezier.BezierSegment([[0, 0], [1, 1/2], [1, 1/2], [0, 1]]),
+    # interior extrema determine extents
+    bezier.BezierSegment([[0, 0], [4, 0], [-4, 1], [0, 1]]),
+    # a quadratic curve
+    bezier.BezierSegment([[0, 0], [0, 1], [1, 1]]),
+    # a linear curve
+    bezier.BezierSegment([[0, 1], [1, 1]]),
+    # a point
+    bezier.BezierSegment([[1, 2]])
+]
+
+
+def _integral_arc_area(B):
+    """(Signed) area swept out by ray from origin to curve."""
+    dB = B.differentiate(B)
+    def integrand(t):
+        dr = dB(t).T
+        n = np.array([dr[1], -dr[0]])
+        return (B(t).T @ n) / 2
+    return scipy.integrate.quad(integrand, 0, 1)[0]
+
+
+def test_area_formula():
+    for B in test_curves:
+        assert(np.isclose(_integral_arc_area(B), B.arc_area()))
diff --git a/lib/matplotlib/tests/test_path.py b/lib/matplotlib/tests/test_path.py
@@ -49,10 +49,25 @@ def test_contains_points_negative_radius():
     np.testing.assert_equal(result, [True, False, False])
 
 
+# convenient curve (xmax=0.75, area=0.6, length=2.0)
+_hard_curve = Path([[0, 0], [1, 0], [1, 1], [0, 1]],
+                    [Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4])
 def test_exact_extents_cubic():
-    hard_curve = Path([[0, 0], [1, 0], [1, 1], [0, 1]],
-                      [Path.MOVETO, Path.CURVE4, Path.CURVE4, Path.CURVE4])
-    assert(hard_curve.get_extents().bounds == (0., 0., 0.75, 1.))
+    assert(_hard_curve.get_extents().bounds == (0., 0., 0.75, 1.))
+
+
+def test_signed_area_curve():
+    assert(np.isclose(_hard_curve.signed_area(), 0.6))
+    # now counter-clockwise
+    rverts = _hard_curve.vertices[:0:-1]
+    rverts = np.append(rverts, np.atleast_2d(_hard_curve.vertices[0]), axis=0)
+    rcurve = Path(rverts, _hard_curve.codes)
+    assert(np.isclose(rcurve.signed_area(), -0.6))
+
+
+def test_signed_area_unit_rectangle():
+    rect = Path.unit_rectangle()
+    assert(np.isclose(rect.signed_area(), 1))
 
 
 def test_point_in_path_nan():
diff --git a/requirements/testing/travis_all.txt b/requirements/testing/travis_all.txt
@@ -7,4 +7,5 @@ pytest-rerunfailures
 pytest-timeout
 pytest-xdist
 python-dateutil
+scipy
 tornado
