8000 compute area without integration and tests · matplotlib/matplotlib@abc420a · GitHub
[go: up one dir, main page]

Skip to content

Co 8000 mmit abc420a

Browse files
committed
compute area without integration and tests
1 parent ed5c99b commit abc420a

File tree

2 files changed

+87
-8
lines changed

2 files changed

+87
-8
lines changed

lib/matplotlib/bezier.py

Lines changed: 71 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,6 @@
66
import warnings
77

88
import numpy as np
9-
import scipy.integrate
109

1110
import matplotlib.cbook as cbook
1211

@@ -256,13 +255,77 @@ def point_at_t(self, t):
256255
return tuple(self(t))
257256

258257
def arc_area(self):
259-
"""(Signed) area between curve an origin."""
260-
dB = self.differentiate(self)
261-
def integrand(t):
262-
dr = dB(t).T
263-
n = np.array([dr[1], -dr[0]])
264-
return (self(t).T @ n) / 2
265-
return scipy.integrate.quad(integrand, 0, 1)[0]
258+
r"""(Signed) area swept out by ray from origin to curve.
259+
260+
Notes
261+
-----
262+
Exact formula used for Bezier curves.
263+
264+
Now for an arbitrary bezier curve B(t), the area of the arc swept
265+
out by the ray from the origin to the curve, we simply need to compute
266+
:math:`\frac{1}{2}\int_0^1 B(t) \cdot n(t) dt`, where :math:`n(t) =
267+
u^{(1)}(t) \hat{x}_0 - u{(0)}(t) \hat{x}_1` is the normal vector
268+
oriented away from the origin and :math:`u^{(i)}(t) = \frac{d}{dt}
269+
B^{(i)}(t)` is the :math:`i`th component of the curve's tangent vector.
270+
(This formula can be found by applying the divergence theorem to
271+
:math:`F(x,y) = [x, y]/2`.
272+
273+
The control points of the curve are just its coefficients in a
274+
Bernstein expansion, so if we let :math:`P_i = [x_i, y_i]` be the
275+
:math:`i`th control point, then
276+
277+
.. math::
278+
279+
\frac{1}{2}\int_0^1 B(t) \cdot n(t) dt \\
280+
= \frac{1}{2}\int_0^1 B^{(0)}(t) \frac{d}{dt} B^{(1)}(t)
281+
- B^{(1)}(t) \frac{d}{dt} B^{(0)}(t)
282+
dt \\
283+
= \frac{1}{2}\int_0^1
284+
\left( \sum_{j=0}^n P_j^{(0)} b_{j,n} \right)
285+
\left( n \sum_{k=0}^{n-1} (P_{k+1}^{(1)} -
286+
P_{k}^{(1)}) b_{j,n} \right)
287+
- \left( \sum_{j=0}^n P_j^{(1)} b_{j,n} \right)
288+
\left( n \sum_{k=0}^{n-1} (P_{k+1}^{(0)} -
289+
P_{k}^{(0)}) b_{j,n} \right)
290+
dt
291+
292+
Where :math:`b_{\nu,n}(t)` is the :math:`\nu`'th Bernstein polynomial
293+
of degree :math:`n`, :math:`b_{\nu, n}(t) = {n \choose \nu} t^\nu {(1 -
294+
t)}^{n-\nu}`.
295+
296+
grouping :math:`t^l(1-t)^m` terms together for each :math:`l`,
297+
:math:`m`, we get that the integrand becomes
298+
299+
.. math::
300+
301+
\frac{n}{2}\int_0^1 \sum_{j=0}^n \sum_{k=0}^{n-1}
302+
\frac{{n \choose j} {{n - 1} \choose k}}
303+
{{{2n - 1} \choose {j+k}}}
304+
[P_j^{(0)} (P_{k+1}^{(1)} - P_{k}^{(1)})
305+
- P_j^{(1)} (P_{k+1}^{(0)} - P_{k}^{(0)})]
306+
b_{j+k,2n-1}(t) dt
307+
308+
Interchanging sum and integral, we notice that :math:`\int_0^1 b_{\nu,
309+
n}(t) dt = \frac{1}{n + 1}`, so we conclude that
310+
311+
.. math::
312+
313+
\frac{1}{2}\int_0^1 B(t) \cdot n(t) dt
314+
= \frac{1}{4}\sum_{j=0}^n \sum_{k=0}^{n-1}
315+
\frac{{n \choose j} {{n - 1} \choose k}}
316+
{{{2n - 1} \choose {j+k}}}
317+
[P_j^{(0)} (P_{k+1}^{(1)} - P_{k}^{(1)})
318+
- P_j^{(1)} (P_{k+1}^{(0)} - P_{k}^{(0)})]
319+
"""
320+
n = self.degree
321+
area = 0
322+
P = self.control_points
323+
dP = np.diff(P, axis=0)
324+
for j in range(n + 1):
325+
for k in range(n):
326+
area += _comb(n, j)*_comb(n-1, k)/_comb(2*n - 1, j + k) \
327+
* (P[j, 0]*dP[k, 1] - P[j, 1]*dP[k, 0])
328+
return (1/4)*area
266329

267330
@classmethod
268331
def differentiate(cls, B):

lib/matplotlib/tests/test_path.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,22 @@ def test_exact_extents_cubic():
5555
np.testing.assert_equal(hard_curve.get_exact_extents(), [0., 0., 0.75, 1.])
5656

5757

58+
def test_signed_area_unit_circle():
59+
circ = Path.unit_circle()
60+
# not quite pi...since it's not quite a circle!
61+
assert(np.isclose(circ.signed_area(), 3.1415935732517166))
62+
# now counter-clockwise
63+
rverts = circ.vertices[-2::-1]
64+
rverts = np.append(rverts, np.atleast_2d(circ.vertices[0]), axis=0)
65+
rcirc = Path(rverts, circ.codes)
66+
assert(np.isclose(rcirc.signed_area(), -3.1415935732517166))
67+
68+
69+
def test_signed_area_unit_rectangle():
70+
rect = Path.unit_rectangle()
71+
assert(np.isclose(rect.signed_area(), 1))
72+
73+
5874
def test_point_in_path_nan():
5975
box = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]])
6076
p = Path(box)

0 commit comments

Comments
 (0)
0