1from __future__ import division
2from math import sqrt, cos, sin, acos, degrees, radians, log, pi
3from collections import MutableSequence
4from bisect import bisect
5
6# This file contains classes for the different types of SVG path segments as
7# well as a Path object that contains a sequence of path segments.
8
9MIN_DEPTH = 5
10ERROR = 1e-12
11
12
13def segment_length(curve, start, end, start_point, end_point, error, min_depth, depth):
14    """Recursively approximates the length by straight lines"""
15    mid = (start + end) / 2
16    mid_point = curve.point(mid)
17    length = abs(end_point - start_point)
18    first_half = abs(mid_point - start_point)
19    second_half = abs(end_point - mid_point)
20
21    length2 = first_half + second_half
22    if (length2 - length > error) or (depth < min_depth):
23        # Calculate the length of each segment:
24        depth += 1
25        return segment_length(
26            curve, start, mid, start_point, mid_point, error, min_depth, depth
27        ) + segment_length(
28            curve, mid, end, mid_point, end_point, error, min_depth, depth
29        )
30    # This is accurate enough.
31    return length2
32
33
34class Linear(object):
35    """A straight line
36
37    The base for Line() and Close().
38    """
39
40    def __init__(self, start, end):
41        self.start = start
42        self.end = end
43
44    def __ne__(self, other):
45        if not isinstance(other, Line):
46            return NotImplemented
47        return not self == other
48
49    def point(self, pos):
50        distance = self.end - self.start
51        return self.start + distance * pos
52
53    def length(self, error=None, min_depth=None):
54        distance = self.end - self.start
55        return sqrt(distance.real ** 2 + distance.imag ** 2)
56
57
58class Line(Linear):
59    def __repr__(self):
60        return "Line(start=%s, end=%s)" % (self.start, self.end)
61
62    def __eq__(self, other):
63        if not isinstance(other, Line):
64            return NotImplemented
65        return self.start == other.start and self.end == other.end
66
67
68class CubicBezier(object):
69    def __init__(self, start, control1, control2, end):
70        self.start = start
71        self.control1 = control1
72        self.control2 = control2
73        self.end = end
74
75    def __repr__(self):
76        return "CubicBezier(start=%s, control1=%s, control2=%s, end=%s)" % (
77            self.start,
78            self.control1,
79            self.control2,
80            self.end,
81        )
82
83    def __eq__(self, other):
84        if not isinstance(other, CubicBezier):
85            return NotImplemented
86        return (
87            self.start == other.start
88            and self.end == other.end
89            and self.control1 == other.control1
90            and self.control2 == other.control2
91        )
92
93    def __ne__(self, other):
94        if not isinstance(other, CubicBezier):
95            return NotImplemented
96        return not self == other
97
98    def is_smooth_from(self, previous):
99        """Checks if this segment would be a smooth segment following the previous"""
100        if isinstance(previous, CubicBezier):
101            return self.start == previous.end and (self.control1 - self.start) == (
102                previous.end - previous.control2
103            )
104        else:
105            return self.control1 == self.start
106
107    def point(self, pos):
108        """Calculate the x,y position at a certain position of the path"""
109        return (
110            ((1 - pos) ** 3 * self.start)
111            + (3 * (1 - pos) ** 2 * pos * self.control1)
112            + (3 * (1 - pos) * pos ** 2 * self.control2)
113            + (pos ** 3 * self.end)
114        )
115
116    def length(self, error=ERROR, min_depth=MIN_DEPTH):
117        """Calculate the length of the path up to a certain position"""
118        start_point = self.point(0)
119        end_point = self.point(1)
120        return segment_length(self, 0, 1, start_point, end_point, error, min_depth, 0)
121
122
123class QuadraticBezier(object):
124    def __init__(self, start, control, end):
125        self.start = start
126        self.end = end
127        self.control = control
128
129    def __repr__(self):
130        return "QuadraticBezier(start=%s, control=%s, end=%s)" % (
131            self.start,
132            self.control,
133            self.end,
134        )
135
136    def __eq__(self, other):
137        if not isinstance(other, QuadraticBezier):
138            return NotImplemented
139        return (
140            self.start == other.start
141            and self.end == other.end
142            and self.control == other.control
143        )
144
145    def __ne__(self, other):
146        if not isinstance(other, QuadraticBezier):
147            return NotImplemented
148        return not self == other
149
150    def is_smooth_from(self, previous):
151        """Checks if this segment would be a smooth segment following the previous"""
152        if isinstance(previous, QuadraticBezier):
153            return self.start == previous.end and (self.control - self.start) == (
154                previous.end - previous.control
155            )
156        else:
157            return self.control == self.start
158
159    def point(self, pos):
160        return (
161            (1 - pos) ** 2 * self.start
162            + 2 * (1 - pos) * pos * self.control
163            + pos ** 2 * self.end
164        )
165
166    def length(self, error=None, min_depth=None):
167        a = self.start - 2 * self.control + self.end
168        b = 2 * (self.control - self.start)
169        a_dot_b = a.real * b.real + a.imag * b.imag
170
171        if abs(a) < 1e-12:
172            s = abs(b)
173        elif abs(a_dot_b + abs(a) * abs(b)) < 1e-12:
174            k = abs(b) / abs(a)
175            if k >= 2:
176                s = abs(b) - abs(a)
177            else:
178                s = abs(a) * (k ** 2 / 2 - k + 1)
179        else:
180            # For an explanation of this case, see
181            # http://www.malczak.info/blog/quadratic-bezier-curve-length/
182            A = 4 * (a.real ** 2 + a.imag ** 2)
183            B = 4 * (a.real * b.real + a.imag * b.imag)
184            C = b.real ** 2 + b.imag ** 2
185
186            Sabc = 2 * sqrt(A + B + C)
187            A2 = sqrt(A)
188            A32 = 2 * A * A2
189            C2 = 2 * sqrt(C)
190            BA = B / A2
191
192            s = (
193                A32 * Sabc
194                + A2 * B * (Sabc - C2)
195                + (4 * C * A - B ** 2) * log((2 * A2 + BA + Sabc) / (BA + C2))
196            ) / (4 * A32)
197        return s
198
199
200class Arc(object):
201    def __init__(self, start, radius, rotation, arc, sweep, end):
202        """radius is complex, rotation is in degrees,
203           large and sweep are 1 or 0 (True/False also work)"""
204
205        self.start = start
206        self.radius = radius
207        self.rotation = rotation
208        self.arc = bool(arc)
209        self.sweep = bool(sweep)
210        self.end = end
211
212        self._parameterize()
213
214    def __repr__(self):
215        return "Arc(start=%s, radius=%s, rotation=%s, arc=%s, sweep=%s, end=%s)" % (
216            self.start,
217            self.radius,
218            self.rotation,
219            self.arc,
220            self.sweep,
221            self.end,
222        )
223
224    def __eq__(self, other):
225        if not isinstance(other, Arc):
226            return NotImplemented
227        return (
228            self.start == other.start
229            and self.end == other.end
230            and self.radius == other.radius
231            and self.rotation == other.rotation
232            and self.arc == other.arc
233            and self.sweep == other.sweep
234        )
235
236    def __ne__(self, other):
237        if not isinstance(other, Arc):
238            return NotImplemented
239        return not self == other
240
241    def _parameterize(self):
242        # Conversion from endpoint to center parameterization
243        # http://www.w3.org/TR/SVG/implnote.html#ArcImplementationNotes
244        if self.start == self.end:
245            # This is equivalent of omitting the segment, so do nothing
246            return
247
248        if self.radius.real == 0 or self.radius.imag == 0:
249            # This should be treated as a straight line
250            return
251
252        cosr = cos(radians(self.rotation))
253        sinr = sin(radians(self.rotation))
254        dx = (self.start.real - self.end.real) / 2
255        dy = (self.start.imag - self.end.imag) / 2
256        x1prim = cosr * dx + sinr * dy
257        x1prim_sq = x1prim * x1prim
258        y1prim = -sinr * dx + cosr * dy
259        y1prim_sq = y1prim * y1prim
260
261        rx = self.radius.real
262        rx_sq = rx * rx
263        ry = self.radius.imag
264        ry_sq = ry * ry
265
266        # Correct out of range radii
267        radius_scale = (x1prim_sq / rx_sq) + (y1prim_sq / ry_sq)
268        if radius_scale > 1:
269            radius_scale = sqrt(radius_scale)
270            rx *= radius_scale
271            ry *= radius_scale
272            rx_sq = rx * rx
273            ry_sq = ry * ry
274            self.radius_scale = radius_scale
275        else:
276            # SVG spec only scales UP
277            self.radius_scale = 1
278
279        t1 = rx_sq * y1prim_sq
280        t2 = ry_sq * x1prim_sq
281        c = sqrt(abs((rx_sq * ry_sq - t1 - t2) / (t1 + t2)))
282
283        if self.arc == self.sweep:
284            c = -c
285        cxprim = c * rx * y1prim / ry
286        cyprim = -c * ry * x1prim / rx
287
288        self.center = complex(
289            (cosr * cxprim - sinr * cyprim) + ((self.start.real + self.end.real) / 2),
290            (sinr * cxprim + cosr * cyprim) + ((self.start.imag + self.end.imag) / 2),
291        )
292
293        ux = (x1prim - cxprim) / rx
294        uy = (y1prim - cyprim) / ry
295        vx = (-x1prim - cxprim) / rx
296        vy = (-y1prim - cyprim) / ry
297        n = sqrt(ux * ux + uy * uy)
298        p = ux
299        theta = degrees(acos(p / n))
300        if uy < 0:
301            theta = -theta
302        self.theta = theta % 360
303
304        n = sqrt((ux * ux + uy * uy) * (vx * vx + vy * vy))
305        p = ux * vx + uy * vy
306        d = p / n
307        # In certain cases the above calculation can through inaccuracies
308        # become just slightly out of range, f ex -1.0000000000000002.
309        if d > 1.0:
310            d = 1.0
311        elif d < -1.0:
312            d = -1.0
313        delta = degrees(acos(d))
314        if (ux * vy - uy * vx) < 0:
315            delta = -delta
316        self.delta = delta % 360
317        if not self.sweep:
318            self.delta -= 360
319
320    def point(self, pos):
321        if self.start == self.end:
322            # This is equivalent of omitting the segment
323            return self.start
324
325        if self.radius.real == 0 or self.radius.imag == 0:
326            # This should be treated as a straight line
327            distance = self.end - self.start
328            return self.start + distance * pos
329
330        angle = radians(self.theta + (self.delta * pos))
331        cosr = cos(radians(self.rotation))
332        sinr = sin(radians(self.rotation))
333        radius = self.radius * self.radius_scale
334
335        x = (
336            cosr * cos(angle) * radius.real
337            - sinr * sin(angle) * radius.imag
338            + self.center.real
339        )
340        y = (
341            sinr * cos(angle) * radius.real
342            + cosr * sin(angle) * radius.imag
343            + self.center.imag
344        )
345        return complex(x, y)
346
347    def length(self, error=ERROR, min_depth=MIN_DEPTH):
348        """The length of an elliptical arc segment requires numerical
349        integration, and in that case it's simpler to just do a geometric
350        approximation, as for cubic bezier curves.
351        """
352        if self.start == self.end:
353            # This is equivalent of omitting the segment
354            return 0
355
356        if self.radius.real == 0 or self.radius.imag == 0:
357            # This should be treated as a straight line
358            distance = self.end - self.start
359            return sqrt(distance.real ** 2 + distance.imag ** 2)
360
361        if self.radius.real == self.radius.imag:
362            # It's a circle, which simplifies this a LOT.
363            radius = self.radius.real * self.radius_scale
364            return abs(radius * self.delta * pi / 180)
365
366        start_point = self.point(0)
367        end_point = self.point(1)
368        return segment_length(self, 0, 1, start_point, end_point, error, min_depth, 0)
369
370
371class Move(object):
372    """Represents move commands. Does nothing, but is there to handle
373    paths that consist of only move commands, which is valid, but pointless.
374    """
375
376    def __init__(self, to):
377        self.start = self.end = to
378
379    def __repr__(self):
380        return "Move(to=%s)" % self.start
381
382    def __eq__(self, other):
383        if not isinstance(other, Move):
384            return NotImplemented
385        return self.start == other.start
386
387    def __ne__(self, other):
388        if not isinstance(other, Move):
389            return NotImplemented
390        return not self == other
391
392    def point(self, pos):
393        return self.start
394
395    def length(self, error=ERROR, min_depth=MIN_DEPTH):
396        return 0
397
398
399class Close(Linear):
400    """Represents the closepath command"""
401
402    def __eq__(self, other):
403        if not isinstance(other, Close):
404            return NotImplemented
405        return self.start == other.start and self.end == other.end
406
407    def __repr__(self):
408        return "Close(start=%s, end=%s)" % (self.start, self.end)
409
410
411class Path(MutableSequence):
412    """A Path is a sequence of path segments"""
413
414    def __init__(self, *segments):
415        self._segments = list(segments)
416        self._length = None
417        self._lengths = None
418        # Fractional distance from starting point through the end of each segment.
419        self._fractions = []
420
421    def __getitem__(self, index):
422        return self._segments[index]
423
424    def __setitem__(self, index, value):
425        self._segments[index] = value
426        self._length = None
427
428    def __delitem__(self, index):
429        del self._segments[index]
430        self._length = None
431
432    def insert(self, index, value):
433        self._segments.insert(index, value)
434        self._length = None
435
436    def reverse(self):
437        # Reversing the order of a path would require reversing each element
438        # as well. That's not implemented.
439        raise NotImplementedError
440
441    def __len__(self):
442        return len(self._segments)
443
444    def __repr__(self):
445        return "Path(%s)" % (", ".join(repr(x) for x in self._segments))
446
447    def __eq__(self, other):
448
449        if not isinstance(other, Path):
450            return NotImplemented
451        if len(self) != len(other):
452            return False
453        for s, o in zip(self._segments, other._segments):
454            if not s == o:
455                return False
456        return True
457
458    def __ne__(self, other):
459        if not isinstance(other, Path):
460            return NotImplemented
461        return not self == other
462
463    def _calc_lengths(self, error=ERROR, min_depth=MIN_DEPTH):
464        if self._length is not None:
465            return
466
467        lengths = [
468            each.length(error=error, min_depth=min_depth) for each in self._segments
469        ]
470        self._length = sum(lengths)
471        self._lengths = [each / self._length for each in lengths]
472        # Calculate the fractional distance for each segment to use in point()
473        fraction = 0
474        for each in self._lengths:
475            fraction += each
476            self._fractions.append(fraction)
477
478    def point(self, pos, error=ERROR):
479
480        # Shortcuts
481        if pos == 0.0:
482            return self._segments[0].point(pos)
483        if pos == 1.0:
484            return self._segments[-1].point(pos)
485
486        self._calc_lengths(error=error)
487        # Find which segment the point we search for is located on:
488        i = bisect(self._fractions, pos)
489        if i == 0:
490            segment_pos = pos / self._fractions[0]
491        else:
492            segment_pos = (pos - self._fractions[i - 1]) / (
493                self._fractions[i] - self._fractions[i - 1]
494            )
495        return self._segments[i].point(segment_pos)
496
497    def length(self, error=ERROR, min_depth=MIN_DEPTH):
498        self._calc_lengths(error, min_depth)
499        return self._length
500
501    def d(self):
502        current_pos = None
503        parts = []
504        previous_segment = None
505        end = self[-1].end
506
507        for segment in self:
508            start = segment.start
509            # If the start of this segment does not coincide with the end of
510            # the last segment or if this segment is actually the close point
511            # of a closed path, then we should start a new subpath here.
512            if isinstance(segment, Close):
513                parts.append("Z")
514            elif (
515                isinstance(segment, Move)
516                or (current_pos != start)
517                or (start == end and not isinstance(previous_segment, Move))
518            ):
519                parts.append("M {0:G},{1:G}".format(start.real, start.imag))
520
521            if isinstance(segment, Line):
522                parts.append("L {0:G},{1:G}".format(segment.end.real, segment.end.imag))
523            elif isinstance(segment, CubicBezier):
524                if segment.is_smooth_from(previous_segment):
525                    parts.append(
526                        "S {0:G},{1:G} {2:G},{3:G}".format(
527                            segment.control2.real,
528                            segment.control2.imag,
529                            segment.end.real,
530                            segment.end.imag,
531                        )
532                    )
533                else:
534                    parts.append(
535                        "C {0:G},{1:G} {2:G},{3:G} {4:G},{5:G}".format(
536                            segment.control1.real,
537                            segment.control1.imag,
538                            segment.control2.real,
539                            segment.control2.imag,
540                            segment.end.real,
541                            segment.end.imag,
542                        )
543                    )
544            elif isinstance(segment, QuadraticBezier):
545                if segment.is_smooth_from(previous_segment):
546                    parts.append(
547                        "T {0:G},{1:G}".format(segment.end.real, segment.end.imag)
548                    )
549                else:
550                    parts.append(
551                        "Q {0:G},{1:G} {2:G},{3:G}".format(
552                            segment.control.real,
553                            segment.control.imag,
554                            segment.end.real,
555                            segment.end.imag,
556                        )
557                    )
558            elif isinstance(segment, Arc):
559                parts.append(
560                    "A {0:G},{1:G} {2:G} {3:d},{4:d} {5:G},{6:G}".format(
561                        segment.radius.real,
562                        segment.radius.imag,
563                        segment.rotation,
564                        int(segment.arc),
565                        int(segment.sweep),
566                        segment.end.real,
567                        segment.end.imag,
568                    )
569                )
570
571            current_pos = segment.end
572            previous_segment = segment
573
574        return " ".join(parts)
575