blob: 73053052dcced347225bb0e3bf65fc319ebdba05 [file] [log] [blame]
# -*- coding: utf-8 -*-
"""fontTools.misc.bezierTools.py -- tools for working with bezier path segments.
"""
from __future__ import print_function, division, absolute_import
from fontTools.misc.arrayTools import calcBounds
from fontTools.misc.py23 import *
import math
__all__ = [
"approximateCubicArcLength",
"approximateCubicArcLengthC",
"approximateQuadraticArcLength",
"approximateQuadraticArcLengthC",
"calcCubicArcLength",
"calcCubicArcLengthC",
"calcQuadraticArcLength",
"calcQuadraticArcLengthC",
"calcCubicBounds",
"calcQuadraticBounds",
"splitLine",
"splitQuadratic",
"splitCubic",
"splitQuadraticAtT",
"splitCubicAtT",
"solveQuadratic",
"solveCubic",
]
def calcCubicArcLength(pt1, pt2, pt3, pt4, tolerance=0.005):
"""Return the arc length for a cubic bezier segment."""
return calcCubicArcLengthC(complex(*pt1), complex(*pt2), complex(*pt3), complex(*pt4), tolerance)
def _split_cubic_into_two(p0, p1, p2, p3):
mid = (p0 + 3 * (p1 + p2) + p3) * .125
deriv3 = (p3 + p2 - p1 - p0) * .125
return ((p0, (p0 + p1) * .5, mid - deriv3, mid),
(mid, mid + deriv3, (p2 + p3) * .5, p3))
def _calcCubicArcLengthCRecurse(mult, p0, p1, p2, p3):
arch = abs(p0-p3)
box = abs(p0-p1) + abs(p1-p2) + abs(p2-p3)
if arch * mult >= box:
return (arch + box) * .5
else:
one,two = _split_cubic_into_two(p0,p1,p2,p3)
return _calcCubicArcLengthCRecurse(mult, *one) + _calcCubicArcLengthCRecurse(mult, *two)
def calcCubicArcLengthC(pt1, pt2, pt3, pt4, tolerance=0.005):
"""Return the arc length for a cubic bezier segment using complex points."""
mult = 1. + 1.5 * tolerance # The 1.5 is a empirical hack; no math
return _calcCubicArcLengthCRecurse(mult, pt1, pt2, pt3, pt4)
epsilonDigits = 6
epsilon = 1e-10
def _dot(v1, v2):
return (v1 * v2.conjugate()).real
def _intSecAtan(x):
# In : sympy.integrate(sp.sec(sp.atan(x)))
# Out: x*sqrt(x**2 + 1)/2 + asinh(x)/2
return x * math.sqrt(x**2 + 1)/2 + math.asinh(x)/2
def calcQuadraticArcLength(pt1, pt2, pt3):
"""Return the arc length for a qudratic bezier segment.
pt1 and pt3 are the "anchor" points, pt2 is the "handle".
>>> calcQuadraticArcLength((0, 0), (0, 0), (0, 0)) # empty segment
0.0
>>> calcQuadraticArcLength((0, 0), (50, 0), (80, 0)) # collinear points
80.0
>>> calcQuadraticArcLength((0, 0), (0, 50), (0, 80)) # collinear points vertical
80.0
>>> calcQuadraticArcLength((0, 0), (50, 20), (100, 40)) # collinear points
107.70329614269008
>>> calcQuadraticArcLength((0, 0), (0, 100), (100, 0))
154.02976155645263
>>> calcQuadraticArcLength((0, 0), (0, 50), (100, 0))
120.21581243984076
>>> calcQuadraticArcLength((0, 0), (50, -10), (80, 50))
102.53273816445825
>>> calcQuadraticArcLength((0, 0), (40, 0), (-40, 0)) # collinear points, control point outside
66.66666666666667
>>> calcQuadraticArcLength((0, 0), (40, 0), (0, 0)) # collinear points, looping back
40.0
"""
return calcQuadraticArcLengthC(complex(*pt1), complex(*pt2), complex(*pt3))
def calcQuadraticArcLengthC(pt1, pt2, pt3):
"""Return the arc length for a qudratic bezier segment using complex points.
pt1 and pt3 are the "anchor" points, pt2 is the "handle"."""
# Analytical solution to the length of a quadratic bezier.
# I'll explain how I arrived at this later.
d0 = pt2 - pt1
d1 = pt3 - pt2
d = d1 - d0
n = d * 1j
scale = abs(n)
if scale == 0.:
return abs(pt3-pt1)
origDist = _dot(n,d0)
if abs(origDist) < epsilon:
if _dot(d0,d1) >= 0:
return abs(pt3-pt1)
a, b = abs(d0), abs(d1)
return (a*a + b*b) / (a+b)
x0 = _dot(d,d0) / origDist
x1 = _dot(d,d1) / origDist
Len = abs(2 * (_intSecAtan(x1) - _intSecAtan(x0)) * origDist / (scale * (x1 - x0)))
return Len
def approximateQuadraticArcLength(pt1, pt2, pt3):
# Approximate length of quadratic Bezier curve using Gauss-Legendre quadrature
# with n=3 points.
return approximateQuadraticArcLengthC(complex(*pt1), complex(*pt2), complex(*pt3))
def approximateQuadraticArcLengthC(pt1, pt2, pt3):
# Approximate length of quadratic Bezier curve using Gauss-Legendre quadrature
# with n=3 points for complex points.
#
# This, essentially, approximates the length-of-derivative function
# to be integrated with the best-matching fifth-degree polynomial
# approximation of it.
#
#https://en.wikipedia.org/wiki/Gaussian_quadrature#Gauss.E2.80.93Legendre_quadrature
# abs(BezierCurveC[2].diff(t).subs({t:T})) for T in sorted(.5, .5±sqrt(3/5)/2),
# weighted 5/18, 8/18, 5/18 respectively.
v0 = abs(-0.492943519233745*pt1 + 0.430331482911935*pt2 + 0.0626120363218102*pt3)
v1 = abs(pt3-pt1)*0.4444444444444444
v2 = abs(-0.0626120363218102*pt1 - 0.430331482911935*pt2 + 0.492943519233745*pt3)
return v0 + v1 + v2
def calcQuadraticBounds(pt1, pt2, pt3):
"""Return the bounding rectangle for a qudratic bezier segment.
pt1 and pt3 are the "anchor" points, pt2 is the "handle".
>>> calcQuadraticBounds((0, 0), (50, 100), (100, 0))
(0, 0, 100, 50.0)
>>> calcQuadraticBounds((0, 0), (100, 0), (100, 100))
(0.0, 0.0, 100, 100)
"""
(ax, ay), (bx, by), (cx, cy) = calcQuadraticParameters(pt1, pt2, pt3)
ax2 = ax*2.0
ay2 = ay*2.0
roots = []
if ax2 != 0:
roots.append(-bx/ax2)
if ay2 != 0:
roots.append(-by/ay2)
points = [(ax*t*t + bx*t + cx, ay*t*t + by*t + cy) for t in roots if 0 <= t < 1] + [pt1, pt3]
return calcBounds(points)
def approximateCubicArcLength(pt1, pt2, pt3, pt4):
"""Return the approximate arc length for a cubic bezier segment.
pt1 and pt4 are the "anchor" points, pt2 and pt3 are the "handles".
>>> approximateCubicArcLength((0, 0), (25, 100), (75, 100), (100, 0))
190.04332968932817
>>> approximateCubicArcLength((0, 0), (50, 0), (100, 50), (100, 100))
154.8852074945903
>>> approximateCubicArcLength((0, 0), (50, 0), (100, 0), (150, 0)) # line; exact result should be 150.
149.99999999999991
>>> approximateCubicArcLength((0, 0), (50, 0), (100, 0), (-50, 0)) # cusp; exact result should be 150.
136.9267662156362
>>> approximateCubicArcLength((0, 0), (50, 0), (100, -50), (-50, 0)) # cusp
154.80848416537057
"""
# Approximate length of cubic Bezier curve using Gauss-Lobatto quadrature
# with n=5 points.
return approximateCubicArcLengthC(complex(*pt1), complex(*pt2), complex(*pt3), complex(*pt4))
def approximateCubicArcLengthC(pt1, pt2, pt3, pt4):
"""Return the approximate arc length for a cubic bezier segment of complex points.
pt1 and pt4 are the "anchor" points, pt2 and pt3 are the "handles"."""
# Approximate length of cubic Bezier curve using Gauss-Lobatto quadrature
# with n=5 points for complex points.
#
# This, essentially, approximates the length-of-derivative function
# to be integrated with the best-matching seventh-degree polynomial
# approximation of it.
#
# https://en.wikipedia.org/wiki/Gaussian_quadrature#Gauss.E2.80.93Lobatto_rules
# abs(BezierCurveC[3].diff(t).subs({t:T})) for T in sorted(0, .5±(3/7)**.5/2, .5, 1),
# weighted 1/20, 49/180, 32/90, 49/180, 1/20 respectively.
v0 = abs(pt2-pt1)*.15
v1 = abs(-0.558983582205757*pt1 + 0.325650248872424*pt2 + 0.208983582205757*pt3 + 0.024349751127576*pt4)
v2 = abs(pt4-pt1+pt3-pt2)*0.26666666666666666
v3 = abs(-0.024349751127576*pt1 - 0.208983582205757*pt2 - 0.325650248872424*pt3 + 0.558983582205757*pt4)
v4 = abs(pt4-pt3)*.15
return v0 + v1 + v2 + v3 + v4
def calcCubicBounds(pt1, pt2, pt3, pt4):
"""Return the bounding rectangle for a cubic bezier segment.
pt1 and pt4 are the "anchor" points, pt2 and pt3 are the "handles".
>>> calcCubicBounds((0, 0), (25, 100), (75, 100), (100, 0))
(0, 0, 100, 75.0)
>>> calcCubicBounds((0, 0), (50, 0), (100, 50), (100, 100))
(0.0, 0.0, 100, 100)
>>> print("%f %f %f %f" % calcCubicBounds((50, 0), (0, 100), (100, 100), (50, 0)))
35.566243 0.000000 64.433757 75.000000
"""
(ax, ay), (bx, by), (cx, cy), (dx, dy) = calcCubicParameters(pt1, pt2, pt3, pt4)
# calc first derivative
ax3 = ax * 3.0
ay3 = ay * 3.0
bx2 = bx * 2.0
by2 = by * 2.0
xRoots = [t for t in solveQuadratic(ax3, bx2, cx) if 0 <= t < 1]
yRoots = [t for t in solveQuadratic(ay3, by2, cy) if 0 <= t < 1]
roots = xRoots + yRoots
points = [(ax*t*t*t + bx*t*t + cx * t + dx, ay*t*t*t + by*t*t + cy * t + dy) for t in roots] + [pt1, pt4]
return calcBounds(points)
def splitLine(pt1, pt2, where, isHorizontal):
"""Split the line between pt1 and pt2 at position 'where', which
is an x coordinate if isHorizontal is False, a y coordinate if
isHorizontal is True. Return a list of two line segments if the
line was successfully split, or a list containing the original
line.
>>> printSegments(splitLine((0, 0), (100, 100), 50, True))
((0, 0), (50, 50))
((50, 50), (100, 100))
>>> printSegments(splitLine((0, 0), (100, 100), 100, True))
((0, 0), (100, 100))
>>> printSegments(splitLine((0, 0), (100, 100), 0, True))
((0, 0), (0, 0))
((0, 0), (100, 100))
>>> printSegments(splitLine((0, 0), (100, 100), 0, False))
((0, 0), (0, 0))
((0, 0), (100, 100))
>>> printSegments(splitLine((100, 0), (0, 0), 50, False))
((100, 0), (50, 0))
((50, 0), (0, 0))
>>> printSegments(splitLine((0, 100), (0, 0), 50, True))
((0, 100), (0, 50))
((0, 50), (0, 0))
"""
pt1x, pt1y = pt1
pt2x, pt2y = pt2
ax = (pt2x - pt1x)
ay = (pt2y - pt1y)
bx = pt1x
by = pt1y
a = (ax, ay)[isHorizontal]
if a == 0:
return [(pt1, pt2)]
t = (where - (bx, by)[isHorizontal]) / a
if 0 <= t < 1:
midPt = ax * t + bx, ay * t + by
return [(pt1, midPt), (midPt, pt2)]
else:
return [(pt1, pt2)]
def splitQuadratic(pt1, pt2, pt3, where, isHorizontal):
"""Split the quadratic curve between pt1, pt2 and pt3 at position 'where',
which is an x coordinate if isHorizontal is False, a y coordinate if
isHorizontal is True. Return a list of curve segments.
>>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 150, False))
((0, 0), (50, 100), (100, 0))
>>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 50, False))
((0, 0), (25, 50), (50, 50))
((50, 50), (75, 50), (100, 0))
>>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 25, False))
((0, 0), (12.5, 25), (25, 37.5))
((25, 37.5), (62.5, 75), (100, 0))
>>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 25, True))
((0, 0), (7.32233, 14.6447), (14.6447, 25))
((14.6447, 25), (50, 75), (85.3553, 25))
((85.3553, 25), (92.6777, 14.6447), (100, -7.10543e-15))
>>> # XXX I'm not at all sure if the following behavior is desirable:
>>> printSegments(splitQuadratic((0, 0), (50, 100), (100, 0), 50, True))
((0, 0), (25, 50), (50, 50))
((50, 50), (50, 50), (50, 50))
((50, 50), (75, 50), (100, 0))
"""
a, b, c = calcQuadraticParameters(pt1, pt2, pt3)
solutions = solveQuadratic(a[isHorizontal], b[isHorizontal],
c[isHorizontal] - where)
solutions = sorted([t for t in solutions if 0 <= t < 1])
if not solutions:
return [(pt1, pt2, pt3)]
return _splitQuadraticAtT(a, b, c, *solutions)
def splitCubic(pt1, pt2, pt3, pt4, where, isHorizontal):
"""Split the cubic curve between pt1, pt2, pt3 and pt4 at position 'where',
which is an x coordinate if isHorizontal is False, a y coordinate if
isHorizontal is True. Return a list of curve segments.
>>> printSegments(splitCubic((0, 0), (25, 100), (75, 100), (100, 0), 150, False))
((0, 0), (25, 100), (75, 100), (100, 0))
>>> printSegments(splitCubic((0, 0), (25, 100), (75, 100), (100, 0), 50, False))
((0, 0), (12.5, 50), (31.25, 75), (50, 75))
((50, 75), (68.75, 75), (87.5, 50), (100, 0))
>>> printSegments(splitCubic((0, 0), (25, 100), (75, 100), (100, 0), 25, True))
((0, 0), (2.29379, 9.17517), (4.79804, 17.5085), (7.47414, 25))
((7.47414, 25), (31.2886, 91.6667), (68.7114, 91.6667), (92.5259, 25))
((92.5259, 25), (95.202, 17.5085), (97.7062, 9.17517), (100, 1.77636e-15))
"""
a, b, c, d = calcCubicParameters(pt1, pt2, pt3, pt4)
solutions = solveCubic(a[isHorizontal], b[isHorizontal], c[isHorizontal],
d[isHorizontal] - where)
solutions = sorted([t for t in solutions if 0 <= t < 1])
if not solutions:
return [(pt1, pt2, pt3, pt4)]
return _splitCubicAtT(a, b, c, d, *solutions)
def splitQuadraticAtT(pt1, pt2, pt3, *ts):
"""Split the quadratic curve between pt1, pt2 and pt3 at one or more
values of t. Return a list of curve segments.
>>> printSegments(splitQuadraticAtT((0, 0), (50, 100), (100, 0), 0.5))
((0, 0), (25, 50), (50, 50))
((50, 50), (75, 50), (100, 0))
>>> printSegments(splitQuadraticAtT((0, 0), (50, 100), (100, 0), 0.5, 0.75))
((0, 0), (25, 50), (50, 50))
((50, 50), (62.5, 50), (75, 37.5))
((75, 37.5), (87.5, 25), (100, 0))
"""
a, b, c = calcQuadraticParameters(pt1, pt2, pt3)
return _splitQuadraticAtT(a, b, c, *ts)
def splitCubicAtT(pt1, pt2, pt3, pt4, *ts):
"""Split the cubic curve between pt1, pt2, pt3 and pt4 at one or more
values of t. Return a list of curve segments.
>>> printSegments(splitCubicAtT((0, 0), (25, 100), (75, 100), (100, 0), 0.5))
((0, 0), (12.5, 50), (31.25, 75), (50, 75))
((50, 75), (68.75, 75), (87.5, 50), (100, 0))
>>> printSegments(splitCubicAtT((0, 0), (25, 100), (75, 100), (100, 0), 0.5, 0.75))
((0, 0), (12.5, 50), (31.25, 75), (50, 75))
((50, 75), (59.375, 75), (68.75, 68.75), (77.3438, 56.25))
((77.3438, 56.25), (85.9375, 43.75), (93.75, 25), (100, 0))
"""
a, b, c, d = calcCubicParameters(pt1, pt2, pt3, pt4)
return _splitCubicAtT(a, b, c, d, *ts)
def _splitQuadraticAtT(a, b, c, *ts):
ts = list(ts)
segments = []
ts.insert(0, 0.0)
ts.append(1.0)
ax, ay = a
bx, by = b
cx, cy = c
for i in range(len(ts) - 1):
t1 = ts[i]
t2 = ts[i+1]
delta = (t2 - t1)
# calc new a, b and c
delta_2 = delta*delta
a1x = ax * delta_2
a1y = ay * delta_2
b1x = (2*ax*t1 + bx) * delta
b1y = (2*ay*t1 + by) * delta
t1_2 = t1*t1
c1x = ax*t1_2 + bx*t1 + cx
c1y = ay*t1_2 + by*t1 + cy
pt1, pt2, pt3 = calcQuadraticPoints((a1x, a1y), (b1x, b1y), (c1x, c1y))
segments.append((pt1, pt2, pt3))
return segments
def _splitCubicAtT(a, b, c, d, *ts):
ts = list(ts)
ts.insert(0, 0.0)
ts.append(1.0)
segments = []
ax, ay = a
bx, by = b
cx, cy = c
dx, dy = d
for i in range(len(ts) - 1):
t1 = ts[i]
t2 = ts[i+1]
delta = (t2 - t1)
delta_2 = delta*delta
delta_3 = delta*delta_2
t1_2 = t1*t1
t1_3 = t1*t1_2
# calc new a, b, c and d
a1x = ax * delta_3
a1y = ay * delta_3
b1x = (3*ax*t1 + bx) * delta_2
b1y = (3*ay*t1 + by) * delta_2
c1x = (2*bx*t1 + cx + 3*ax*t1_2) * delta
c1y = (2*by*t1 + cy + 3*ay*t1_2) * delta
d1x = ax*t1_3 + bx*t1_2 + cx*t1 + dx
d1y = ay*t1_3 + by*t1_2 + cy*t1 + dy
pt1, pt2, pt3, pt4 = calcCubicPoints((a1x, a1y), (b1x, b1y), (c1x, c1y), (d1x, d1y))
segments.append((pt1, pt2, pt3, pt4))
return segments
#
# Equation solvers.
#
from math import sqrt, acos, cos, pi
def solveQuadratic(a, b, c,
sqrt=sqrt):
"""Solve a quadratic equation where a, b and c are real.
a*x*x + b*x + c = 0
This function returns a list of roots. Note that the returned list
is neither guaranteed to be sorted nor to contain unique values!
"""
if abs(a) < epsilon:
if abs(b) < epsilon:
# We have a non-equation; therefore, we have no valid solution
roots = []
else:
# We have a linear equation with 1 root.
roots = [-c/b]
else:
# We have a true quadratic equation. Apply the quadratic formula to find two roots.
DD = b*b - 4.0*a*c
if DD >= 0.0:
rDD = sqrt(DD)
roots = [(-b+rDD)/2.0/a, (-b-rDD)/2.0/a]
else:
# complex roots, ignore
roots = []
return roots
def solveCubic(a, b, c, d):
"""Solve a cubic equation where a, b, c and d are real.
a*x*x*x + b*x*x + c*x + d = 0
This function returns a list of roots. Note that the returned list
is neither guaranteed to be sorted nor to contain unique values!
>>> solveCubic(1, 1, -6, 0)
[-3.0, -0.0, 2.0]
>>> solveCubic(-10.0, -9.0, 48.0, -29.0)
[-2.9, 1.0, 1.0]
>>> solveCubic(-9.875, -9.0, 47.625, -28.75)
[-2.911392, 1.0, 1.0]
>>> solveCubic(1.0, -4.5, 6.75, -3.375)
[1.5, 1.5, 1.5]
>>> solveCubic(-12.0, 18.0, -9.0, 1.50023651123)
[0.5, 0.5, 0.5]
>>> solveCubic(
... 9.0, 0.0, 0.0, -7.62939453125e-05
... ) == [-0.0, -0.0, -0.0]
True
"""
#
# adapted from:
# CUBIC.C - Solve a cubic polynomial
# public domain by Ross Cottrell
# found at: http://www.strangecreations.com/library/snippets/Cubic.C
#
if abs(a) < epsilon:
# don't just test for zero; for very small values of 'a' solveCubic()
# returns unreliable results, so we fall back to quad.
return solveQuadratic(b, c, d)
a = float(a)
a1 = b/a
a2 = c/a
a3 = d/a
Q = (a1*a1 - 3.0*a2)/9.0
R = (2.0*a1*a1*a1 - 9.0*a1*a2 + 27.0*a3)/54.0
R2 = R*R
Q3 = Q*Q*Q
R2 = 0 if R2 < epsilon else R2
Q3 = 0 if abs(Q3) < epsilon else Q3
R2_Q3 = R2 - Q3
if R2 == 0. and Q3 == 0.:
x = round(-a1/3.0, epsilonDigits)
return [x, x, x]
elif R2_Q3 <= epsilon * .5:
# The epsilon * .5 above ensures that Q3 is not zero.
theta = acos(max(min(R/sqrt(Q3), 1.0), -1.0))
rQ2 = -2.0*sqrt(Q)
a1_3 = a1/3.0
x0 = rQ2*cos(theta/3.0) - a1_3
x1 = rQ2*cos((theta+2.0*pi)/3.0) - a1_3
x2 = rQ2*cos((theta+4.0*pi)/3.0) - a1_3
x0, x1, x2 = sorted([x0, x1, x2])
# Merge roots that are close-enough
if x1 - x0 < epsilon and x2 - x1 < epsilon:
x0 = x1 = x2 = round((x0 + x1 + x2) / 3., epsilonDigits)
elif x1 - x0 < epsilon:
x0 = x1 = round((x0 + x1) / 2., epsilonDigits)
x2 = round(x2, epsilonDigits)
elif x2 - x1 < epsilon:
x0 = round(x0, epsilonDigits)
x1 = x2 = round((x1 + x2) / 2., epsilonDigits)
else:
x0 = round(x0, epsilonDigits)
x1 = round(x1, epsilonDigits)
x2 = round(x2, epsilonDigits)
return [x0, x1, x2]
else:
x = pow(sqrt(R2_Q3)+abs(R), 1/3.0)
x = x + Q/x
if R >= 0.0:
x = -x
x = round(x - a1/3.0, epsilonDigits)
return [x]
#
# Conversion routines for points to parameters and vice versa
#
def calcQuadraticParameters(pt1, pt2, pt3):
x2, y2 = pt2
x3, y3 = pt3
cx, cy = pt1
bx = (x2 - cx) * 2.0
by = (y2 - cy) * 2.0
ax = x3 - cx - bx
ay = y3 - cy - by
return (ax, ay), (bx, by), (cx, cy)
def calcCubicParameters(pt1, pt2, pt3, pt4):
x2, y2 = pt2
x3, y3 = pt3
x4, y4 = pt4
dx, dy = pt1
cx = (x2 -dx) * 3.0
cy = (y2 -dy) * 3.0
bx = (x3 - x2) * 3.0 - cx
by = (y3 - y2) * 3.0 - cy
ax = x4 - dx - cx - bx
ay = y4 - dy - cy - by
return (ax, ay), (bx, by), (cx, cy), (dx, dy)
def calcQuadraticPoints(a, b, c):
ax, ay = a
bx, by = b
cx, cy = c
x1 = cx
y1 = cy
x2 = (bx * 0.5) + cx
y2 = (by * 0.5) + cy
x3 = ax + bx + cx
y3 = ay + by + cy
return (x1, y1), (x2, y2), (x3, y3)
def calcCubicPoints(a, b, c, d):
ax, ay = a
bx, by = b
cx, cy = c
dx, dy = d
x1 = dx
y1 = dy
x2 = (cx / 3.0) + dx
y2 = (cy / 3.0) + dy
x3 = (bx + cx) / 3.0 + x2
y3 = (by + cy) / 3.0 + y2
x4 = ax + dx + cx + bx
y4 = ay + dy + cy + by
return (x1, y1), (x2, y2), (x3, y3), (x4, y4)
def _segmentrepr(obj):
"""
>>> _segmentrepr([1, [2, 3], [], [[2, [3, 4], [0.1, 2.2]]]])
'(1, (2, 3), (), ((2, (3, 4), (0.1, 2.2))))'
"""
try:
it = iter(obj)
except TypeError:
return "%g" % obj
else:
return "(%s)" % ", ".join([_segmentrepr(x) for x in it])
def printSegments(segments):
"""Helper for the doctests, displaying each segment in a list of
segments on a single line as a tuple.
"""
for segment in segments:
print(_segmentrepr(segment))
if __name__ == "__main__":
import sys
import doctest
sys.exit(doctest.testmod().failed)