Implementing SVG arc curves in Python

Question

I'm trying to implement SVG path calculations in Python, but I'm running into problems with Arc curves.

I think the problem is in the conversion from end point to center parameterization, but I can't find the problem. You can find notes on how to implement it in section F6.5 of the SVG specifications. I've also looked at implementations in other languages and I can't see what they do different either.

My Arc object implementation is here:

class Arc(object):

    def __init__(self, start, radius, rotation, arc, sweep, end):
        """radius is complex, rotation is in degrees, 
           large and sweep are 1 or 0 (True/False also work)"""

        self.start = start
        self.radius = radius
        self.rotation = rotation
        self.arc = bool(arc)
        self.sweep = bool(sweep)
        self.end = end

        self._parameterize()

    def _parameterize(self):
        # Conversion from endpoint to center parameterization
        # http://www.w3.org/TR/SVG/implnote.html#ArcImplementationNotes

        cosr = cos(radians(self.rotation))
        sinr = sin(radians(self.rotation))
        dx = (self.start.real - self.end.real) / 2
        dy = (self.start.imag - self.end.imag) / 2
        x1prim = cosr * dx + sinr * dy
        x1prim_sq = x1prim * x1prim
        y1prim = -sinr * dx + cosr * dy
        y1prim_sq = y1prim * y1prim

        rx = self.radius.real
        rx_sq = rx * rx
        ry = self.radius.imag        
        ry_sq = ry * ry

        # Correct out of range radii
        radius_check = (x1prim_sq / rx_sq) + (y1prim_sq / ry_sq)
        if radius_check > 1:
            rx *= sqrt(radius_check)
            ry *= sqrt(radius_check)
            rx_sq = rx * rx
            ry_sq = ry * ry

        t1 = rx_sq * y1prim_sq
        t2 = ry_sq * x1prim_sq
        c = sqrt((rx_sq * ry_sq - t1 - t2) / (t1 + t2))
        if self.arc == self.sweep:
            c = -c
        cxprim = c * rx * y1prim / ry
        cyprim = -c * ry * x1prim / rx

        self.center = complex((cosr * cxprim - sinr * cyprim) + 
                              ((self.start.real + self.end.real) / 2),
                              (sinr * cxprim + cosr * cyprim) + 
                              ((self.start.imag + self.end.imag) / 2))

        ux = (x1prim - cxprim) / rx
        uy = (y1prim - cyprim) / ry
        vx = (-x1prim - cxprim) / rx
        vy = (-y1prim - cyprim) / ry
        n = sqrt(ux * ux + uy * uy)
        p = ux
        theta = degrees(acos(p / n))
        if uy > 0:
            theta = -theta
        self.theta = theta % 360

        n = sqrt((ux * ux + uy * uy) * (vx * vx + vy * vy))
        p = ux * vx + uy * vy
        if p == 0:
            delta = degrees(acos(0))
        else:
            delta = degrees(acos(p / n))
        if (ux * vy - uy * vx) < 0:
            delta = -delta
        self.delta = delta % 360
        if not self.sweep:
            self.delta -= 360

    def point(self, pos):
        if self.arc == self.sweep:
            angle = radians(self.theta - (self.delta * pos))
        else:
            angle = radians(self.delta + (self.delta * pos))

        x = sin(angle) * self.radius.real + self.center.real
        y = cos(angle) * self.radius.imag + self.center.imag
        return complex(x, y)

You can test this with the following code that will draw the curves with the Turtle module. (The raw_input() at the end is just to that the screen doesn't disappear when the program exits).

arc1 = Arc(0j, 100+50j, 0, 0, 0, 100+50j)
arc2 = Arc(0j, 100+50j, 0, 1, 0, 100+50j)
arc3 = Arc(0j, 100+50j, 0, 0, 1, 100+50j)
arc4 = Arc(0j, 100+50j, 0, 1, 1, 100+50j)

import turtle
t = turtle.Turtle()
t.penup()
t.goto(0, 0)
t.dot(5, 'red')
t.write('Start')
t.goto(100, 50)
t.dot(5, 'red')
t.write('End')        
t.pencolor = t.color('blue')

for arc in (arc1, arc2, arc3, arc4):
    t.penup()
    p = arc.point(0)
    t.goto(p.real, p.imag)
    t.pendown()
    for x in range(1,101):
        p = arc.point(x*0.01)
        t.goto(p.real, p.imag)

raw_input()

The issue:

Each of these four arcs drawn should draw from the Start point to the End point. However, they are drawn from the wrong points. Two curves go from end to start, and two goes from 100,-50 to 0,0 instead of from 0,0 to 100, 50.

Part of the problem is that the implementation notes give you the formula from how to do the conversion form endpoints to center, but doesn't explain what it does geometrically, so I'm not all clear on what each step does. An explanation of that would also be helpful.

Answer 1

I think I have found some errors in your code:

theta = degrees(acos(p / n))
if uy > 0:
    theta = -theta
self.theta = theta % 360

The condition uy > 0 is wrong, correct is uy < 0 (the directed angle from (1, 0) to (ux, uy) is negative if uy < 0):

theta = degrees(acos(p / n))
if uy < 0:
    theta = -theta
self.theta = theta % 360

Then

if self.arc == self.sweep:
    angle = radians(self.theta - (self.delta * pos))
else:
    angle = radians(self.delta + (self.delta * pos))

The distinction is not necessary here, the sweep and arc parameters are already accounted for in theta and delta. This can be simplified to:

angle = radians(self.theta + (self.delta * pos))

And finally

x = sin(angle) * self.radius.real + self.center.real
y = cos(angle) * self.radius.imag + self.center.imag

Here sin and cos are mixed up, correct is

x = cos(angle) * self.radius.real + self.center.real
y = sin(angle) * self.radius.imag + self.center.imag

After these modifications, the program runs as expected.

---

EDIT: There is one more problem. The point method does not account for a possible rotation parameter. The following version should be correct:

def point(self, pos):
    angle = radians(self.theta + (self.delta * pos))
    cosr = cos(radians(self.rotation))
    sinr = sin(radians(self.rotation))

    x = cosr * cos(angle) * self.radius.real - sinr * sin(angle) * self.radius.imag + self.center.real
    y = sinr * cos(angle) * self.radius.real + cosr * sin(angle) * self.radius.imag + self.center.imag
    return complex(x, y)

(See formula F.6.3.1 in the SVG specification.)

Answer 2

Maybe you could have a look at links below, there seems to be a step-by-step guide on how to compute the arcs (see computeArc()):

http://svn.apache.org/repos/asf/xmlgraphics/batik/branches/svg11/sources/org/apache/batik/ext/awt/geom/ExtendedGeneralPath.java

or

http://java.net/projects/svgsalamander/sources/svn/content/trunk/svg-core/src/main/java/com/kitfox/svg/pathcmd/Arc.java