cubic bezier polyline
976685
def cubic_bezier(document, coords):
	""
	element = document.createElement('path')
	points  = [(coords[i], coords[i+1]) for i  in range(0, len(coords), 2)]
	path    = ["M%s %s" %points[0]]
	for n in xrange(1, len(points), 3):
		A, B, C = points[n:n+3]
		path.append("C%s,%s %s,%s %s,%s" % (A[0], A[1], B[0], B[1], C[0], C[1]))
	element.setAttribute('d', ' '.join(path))
	return element
441477
def smooth(polylines):
    
    for c in polylines:
        if len(c) < 9:
            # smoothing wouldn't make sense here
            continue
        x = c[:, 0]
        y = c[:, 1]

        t = np.arange(x.shape[0], dtype=float)
        t /= t[-1]
        x = UnivariateSpline(t, x)(t)
        y = UnivariateSpline(t, y)(t)
        c[:, 0] = x
        c[:, 1] = y
401382
private double cubicInterpolate(final double Y0, final double Y1, final double Y2, final double Y3, final double MU) {
        final double A0;
        final double A1;
        final double A2;
        final double A3;
        final double MU2;

        MU2 = MU * MU;
        A0 = Y3 - Y2 - Y0 + Y1;
        A1 = Y0 - Y1 - A0;
        A2 = Y2 - Y0;
        A3 = Y1;

        return ((A0 * MU * MU2) + (A1 * MU2) + (A2 * MU) + A3);
    }
226777
function getPointOnBezier(startX, startY, cpX, cpY, endX, endY, distance){
    var bestT = 0;
    var bestAccuracy = 1000;
    var stepSize = 0.001;
    for(var t = 0; t<1; t+=stepSize){
      var currentPoint = getQuadraticCurvePoint(startX, startY, cpX, cpY,
          endX, endY, t);
      var currentDistance = getDistanceBetweenPoints(startX, startY,
          currentPoint.x, currentPoint.y);
      if(Math.abs(currentDistance-distance) < bestAccuracy){
        bestAccuracy = Math.abs(currentDistance-distance);
        bestT = t;
      }
    }
    return getQuadraticCurvePoint(startX, startY, cpX, cpY, endX, endY, bestT);
  }
147305
def bezier_by_line_intersections(bezier, line):
    """"""
    # The method here is to translate (shift) then rotate the complex plane so
    # that line starts at the origin and proceeds along the positive real axis.
    # After this transformation, the intersection points are the real roots of
    # the imaginary component of the bezier for which the real component is
    # between 0 and abs(line[1]-line[0])].
    assert len(line[:]) == 2
    assert line[0] != line[1]
    if not any(p != bezier[0] for p in bezier):
        raise ValueError("bezier is nodal, use "
                         "bezier_by_line_intersection(bezier[0], line) "
                         "instead for a bool to be returned.")

    # First let's shift the complex plane so that line starts at the origin
    shifted_bezier = [z - line[0] for z in bezier]
    shifted_line_end = line[1] - line[0]
    line_length = abs(shifted_line_end)

    # Now let's rotate the complex plane so that line falls on the x-axis
    rotation_matrix = line_length/shifted_line_end
    transformed_bezier = [rotation_matrix*z for z in shifted_bezier]

    # Now all intersections should be roots of the imaginary component of
    # the transformed bezier
    transformed_bezier_imag = [p.imag for p in transformed_bezier]
    coeffs_y = bezier2polynomial(transformed_bezier_imag)
    roots_y = list(polyroots01(coeffs_y))  # returns real roots 0 <= r <= 1

    transformed_bezier_real = [p.real for p in transformed_bezier]
    intersection_list = []
    for bez_t in set(roots_y):
        xval = bezier_point(transformed_bezier_real, bez_t)
        if 0 <= xval <= line_length:
            line_t = xval/line_length
            intersection_list.append((bez_t, line_t))
    return intersection_list
752677
def bezier_point(p, t):
    """"""

    # begin arc support block ########################
    try:
        p.large_arc
        return p.point(t)
    except:
        pass
    # end arc support block ##########################

    deg = len(p) - 1
    if deg == 3:
        return p[0] + t*(
            3*(p[1] - p[0]) + t*(
                3*(p[0] + p[2]) - 6*p[1] + t*(
                    -p[0] + 3*(p[1] - p[2]) + p[3])))
    elif deg == 2:
        return p[0] + t*(
            2*(p[1] - p[0]) + t*(
                p[0] - 2*p[1] + p[2]))
    elif deg == 1:
        return p[0] + t*(p[1] - p[0])
    elif deg == 0:
        return p[0]
    else:
        bern = bernstein(deg, t)
        return sum(bern[k]*p[k] for k in range(deg+1))
149717
def curve_to(self, x, y, x2, y2, x3, y3):
        """"""
        self._add_instruction("curve_to", x, y, x2, y2, x3, y3)
1154546
def intersect(self, other_seg, tol=1e-12):
        """"""
        if isinstance(other_seg, Line):
            return bezier_by_line_intersections(self, other_seg)
        elif (isinstance(other_seg, QuadraticBezier) or
              isinstance(other_seg, CubicBezier)):
            assert self != other_seg
            longer_length = max(self.length(), other_seg.length())
            return bezier_intersections(self, other_seg,
                                        longer_length=longer_length,
                                        tol=tol, tol_deC=tol)
        elif isinstance(other_seg, Arc):
            t2t1s = other_seg.intersect(self)
            return [(t1, t2) for t2, t1 in t2t1s]
        elif isinstance(other_seg, Path):
            raise TypeError(
                "other_seg must be a path segment, not a Path object, use "
                "Path.intersect().")
        else:
            raise TypeError("other_seg must be a path segment.")
786839
function roundedRect(ctx, x, y, width, height, radius) {
    // from MDN docs
    ctx.beginPath();
    ctx.moveTo(x, y + radius);
    ctx.lineTo(x, y + height - radius);
    ctx.quadraticCurveTo(x, y + height, x + radius, y + height);
    ctx.lineTo(x + width - radius, y + height);
    ctx.quadraticCurveTo(x + width, y + height, x + width, y + height
        - radius);
    ctx.lineTo(x + width, y + radius);
    ctx.quadraticCurveTo(x + width, y, x + width - radius, y);
    ctx.lineTo(x + radius, y);
    ctx.quadraticCurveTo(x, y, x, y + radius);
    ctx.stroke();
    ctx.fill();
  }
713898
def Bezier(points, at):
    
    at = np.asarray(at)
    at_flat = at.ravel()
    N = len(points)
    curve = np.zeros((at_flat.shape[0], 2))
    for ii in range(N):
        curve += np.outer(Bernstein(N - 1, ii)(at_flat), points[ii])
    return curve.reshape(at.shape + (2,))
69524
def get_bezier_ellipse(x, y, xradius, yradius, kappa=0.5522848):
    """"""

    xs, ys = x - xradius, y - yradius
    ox, oy = xradius * kappa, yradius * kappa
    xe, ye = x + xradius, y + yradius

    pts = [(xs, y),
           (xs, y - oy), (x - ox, ys), (x, ys),
           (x + ox, ys), (xe, y - oy), (xe, y),
           (xe, y + oy), (x + ox, ye), (x, ye),
           (x - ox, ye), (xs, y + oy), (xs, y)]
    return pts
1335567
function (elem, fromD, toD) {
		fromD = fromD || '';
		var shift = elem.shift,
			bezier = fromD.indexOf('C') > -1,
			numParams = bezier ? 7 : 3,
			endLength,
			slice,
			i,
			start = fromD.split(' '),
			end = [].concat(toD), // copy
			startBaseLine,
			endBaseLine,
			sixify = function (arr) { // in splines make move points have six parameters like bezier curves
				i = arr.length;
				while (i--) {
					if (arr[i] === M) {
						arr.splice(i + 1, 0, arr[i + 1], arr[i + 2], arr[i + 1], arr[i + 2]);
					}
				}
			};

		if (bezier) {
			sixify(start);
			sixify(end);
		}

		// pull out the base lines before padding
		if (elem.isArea) {
			startBaseLine = start.splice(start.length - 6, 6);
			endBaseLine = end.splice(end.length - 6, 6);
		}

		// if shifting points, prepend a dummy point to the end path
		if (shift <= end.length / numParams && start.length === end.length) {
			while (shift--) {
				end = [].concat(end).splice(0, numParams).concat(end);
			}
		}
		elem.shift = 0; // reset for following animations

		// copy and append last point until the length matches the end length
		if (start.length) {
			endLength = end.length;
			while (start.length < endLength) {

				//bezier && sixify(start);
				slice = [].concat(start).splice(start.length - numParams, numParams);
				if (bezier) { // disable first control point
					slice[numParams - 6] = slice[numParams - 2];
					slice[numParams - 5] = slice[numParams - 1];
				}
				start = start.concat(slice);
			}
		}

		if (startBaseLine) { // append the base lines for areas
			start = start.concat(startBaseLine);
			end = end.concat(endBaseLine);
		}
		return [start, end];
	}
294778
function curve($x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3) {
    // in the current line style, draw a bezier curve from (x0,y0) to (x3,y3) using the other two points
    // as the control points for the curve.
    $this->objects[$this->currentContents]['c'] .=
      sprintf("\n%.3F %.3F m %.3F %.3F %.3F %.3F %.3F %.3F c S", $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3);
  }
101778
def cubic_interpolate(x, y, precision=250, **kwargs):
    
    n = len(x) - 1
    # Spline equation is a + bx + cx² + dx³
    # ie: Spline part i equation is a[i] + b[i]x + c[i]x² + d[i]x³
    a = y
    b = [0] * (n + 1)
    c = [0] * (n + 1)
    d = [0] * (n + 1)
    m = [0] * (n + 1)
    z = [0] * (n + 1)

    h = [x2 - x1 for x1, x2 in zip(x, x[1:])]
    k = [a2 - a1 for a1, a2 in zip(a, a[1:])]
    g = [k[i] / h[i] if h[i] else 1 for i in range(n)]

    for i in range(1, n):
        j = i - 1
        l = 1 / (2 * (x[i + 1] - x[j]) - h[j] * m[j]) if x[i + 1] - x[j] else 0
        m[i] = h[i] * l
        z[i] = (3 * (g[i] - g[j]) - h[j] * z[j]) * l

    for j in reversed(range(n)):
        if h[j] == 0:
            continue
        c[j] = z[j] - (m[j] * c[j + 1])
        b[j] = g[j] - (h[j] * (c[j + 1] + 2 * c[j])) / 3
        d[j] = (c[j + 1] - c[j]) / (3 * h[j])

    for i in range(n + 1):
        yield x[i], a[i]
        if i == n or h[i] == 0:
            continue
        for s in range(1, precision):
            X = s * h[i] / precision
            X2 = X * X
            X3 = X2 * X
            yield x[i] + X, a[i] + b[i] * X + c[i] * X2 + d[i] * X3
915463
def bezier_bounding_box(bez):
    """"""

    # begin arc support block ########################
    try:
        bla = bez.large_arc
        return bez.bbox()  # added to support Arc objects
    except:
        pass
    # end arc support block ##########################

    if len(bez) == 4:
        xmin, xmax = bezier_real_minmax([p.real for p in bez])
        ymin, ymax = bezier_real_minmax([p.imag for p in bez])
        return xmin, xmax, ymin, ymax
    poly = bezier2polynomial(bez, return_poly1d=True)
    x = real(poly)
    y = imag(poly)
    dx = x.deriv()
    dy = y.deriv()
    x_extremizers = [0, 1] + polyroots(dx, realroots=True,
                                    condition=lambda r: 0 < r < 1)
    y_extremizers = [0, 1] + polyroots(dy, realroots=True,
                                    condition=lambda r: 0 < r < 1)
    x_extrema = [x(t) for t in x_extremizers]
    y_extrema = [y(t) for t in y_extremizers]
    return min(x_extrema), max(x_extrema), min(y_extrema), max(y_extrema)
1155626
function bezier(x1, y1, x2, y2)
{
    var p1 = [x1, y1], p2 = [x2, y2],
        A = [null, null], B = [null, null], C = [null, null],

        bezCoOrd = function(time, ax)
        {
            C[ax] = 3 * p1[ax]; B[ax] = 3 * (p2[ax] - p1[ax]) - C[ax]; A[ax] = 1 - C[ax] - B[ax];
            return time * (C[ax] + time * (B[ax] + time * A[ax]));
        },

        xDeriv = function(time)
        {
            return C[0] + time * (2 * B[0] + 3 * A[0] * time);
        },

        xForT = function(time)
        {
            var x = time, i = 0, z;
            while (++i < 14)
            {
                z = bezCoOrd(x, 0) - time;
                if (Math.abs(z) < 1e-3) break;
                x -= z / xDeriv(x);
            }
            return x;
        };

    return function(time) {
        return bezCoOrd(xForT(time), 1);
    };
}
425151
def bezier_real_minmax(p):
    """"""
    local_extremizers = [0, 1]
    if len(p) == 4:  # cubic case
        a = [p.real for p in p]
        denom = a[0] - 3*a[1] + 3*a[2] - a[3]
        if denom != 0:
            delta = a[1]**2 - (a[0] + a[1])*a[2] + a[2]**2 + (a[0] - a[1])*a[3]
            if delta >= 0:  # otherwise no local extrema
                sqdelta = sqrt(delta)
                tau = a[0] - 2*a[1] + a[2]
                r1 = (tau + sqdelta)/denom
                r2 = (tau - sqdelta)/denom
                if 0 < r1 < 1:
                    local_extremizers.append(r1)
                if 0 < r2 < 1:
                    local_extremizers.append(r2)
            local_extrema = [bezier_point(a, t) for t in local_extremizers]
            return min(local_extrema), max(local_extrema)

    # find reverse standard coefficients of the derivative
    dcoeffs = bezier2polynomial(a, return_poly1d=True).deriv().coeffs

    # find real roots, r, such that 0 <= r <= 1
    local_extremizers += polyroots01(dcoeffs)
    local_extrema = [bezier_point(a, t) for t in local_extremizers]
    return min(local_extrema), max(local_extrema)