diff -r 0c9798d91427 -r 660ce16822a9 svg2gcode/svg/geometry.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/svg2gcode/svg/geometry.py	Sat Nov 07 13:33:12 2015 +0100
@@ -0,0 +1,343 @@
+# Copyright (C) 2013 -- CJlano < cjlano @ free.fr >
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along
+# with this program; if not, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+'''
+This module contains all the geometric classes and functions not directly
+related to SVG parsing. It can be reused outside the scope of SVG.
+'''
+
+import math
+import numbers
+import operator
+
+class Point:
+    def __init__(self, x=None, y=None):
+        '''A Point is defined either by a tuple/list of length 2 or
+           by 2 coordinates
+        >>> Point(1,2)
+        (1.000,2.000)
+        >>> Point((1,2))
+        (1.000,2.000)
+        >>> Point([1,2])
+        (1.000,2.000)
+        >>> Point('1', '2')
+        (1.000,2.000)
+        >>> Point(('1', None))
+        (1.000,0.000)
+        '''
+        if (isinstance(x, tuple) or isinstance(x, list)) and len(x) == 2:
+            x,y = x
+
+        # Handle empty parameter(s) which should be interpreted as 0
+        if x is None: x = 0
+        if y is None: y = 0
+
+        try:
+            self.x = float(x)
+            self.y = float(y)
+        except:
+            raise TypeError("A Point is defined by 2 numbers or a tuple")
+
+    def __add__(self, other):
+        '''Add 2 points by adding coordinates.
+        Try to convert other to Point if necessary
+        >>> Point(1,2) + Point(3,2)
+        (4.000,4.000)
+        >>> Point(1,2) + (3,2)
+        (4.000,4.000)'''
+        if not isinstance(other, Point):
+            try: other = Point(other)
+            except: return NotImplemented
+        return Point(self.x + other.x, self.y + other.y)
+
+    def __sub__(self, other):
+        '''Substract two Points.
+        >>> Point(1,2) - Point(3,2)
+        (-2.000,0.000)
+        '''
+        if not isinstance(other, Point):
+            try: other = Point(other)
+            except: return NotImplemented
+        return Point(self.x - other.x, self.y - other.y)
+
+    def __mul__(self, other):
+        '''Multiply a Point with a constant.
+        >>> 2 * Point(1,2)
+        (2.000,4.000)
+        >>> Point(1,2) * Point(1,2) #doctest:+IGNORE_EXCEPTION_DETAIL
+        Traceback (most recent call last):
+            ...
+        TypeError:
+        '''
+        if not isinstance(other, numbers.Real):
+            return NotImplemented
+        return Point(self.x * other, self.y * other)
+    def __rmul__(self, other):
+        return self.__mul__(other)
+
+    def __eq__(self, other):
+        '''Test equality
+        >>> Point(1,2) == (1,2)
+        True
+        >>> Point(1,2) == Point(2,1)
+        False
+        '''
+        if not isinstance(other, Point):
+            try: other = Point(other)
+            except: return NotImplemented
+        return (self.x == other.x) and (self.y == other.y)
+
+    def __repr__(self):
+        return '(' + format(self.x,'.3f') + ',' + format( self.y,'.3f') + ')'
+
+    def __str__(self):
+        return self.__repr__();
+
+    def coord(self):
+        '''Return the point tuple (x,y)'''
+        return (self.x, self.y)
+
+    def length(self):
+        '''Vector length, Pythagoras theorem'''
+        return math.sqrt(self.x ** 2 + self.y ** 2)
+
+    def rot(self, angle):
+        '''Rotate vector [Origin,self] '''
+        if not isinstance(angle, Angle):
+            try: angle = Angle(angle)
+            except: return NotImplemented
+        x = self.x * angle.cos - self.y * angle.sin
+        y = self.x * angle.sin + self.y * angle.cos
+        return Point(x,y)
+
+
+class Angle:
+    '''Define a trigonometric angle [of a vector] '''
+    def __init__(self, arg):
+        if isinstance(arg, numbers.Real):
+        # We precompute sin and cos for rotations
+            self.angle = arg
+            self.cos = math.cos(self.angle)
+            self.sin = math.sin(self.angle)
+        elif isinstance(arg, Point):
+        # Point angle is the trigonometric angle of the vector [origin, Point]
+            pt = arg
+            try:
+                self.cos = pt.x/pt.length()
+                self.sin = pt.y/pt.length()
+            except ZeroDivisionError:
+                self.cos = 1
+                self.sin = 0
+
+            self.angle = math.acos(self.cos)
+            if self.sin < 0:
+                self.angle = -self.angle
+        else:
+            raise TypeError("Angle is defined by a number or a Point")
+
+    def __neg__(self):
+        return Angle(Point(self.cos, -self.sin))
+
+class Segment:
+    '''A segment is an object defined by 2 points'''
+    def __init__(self, start, end):
+        self.start = start
+        self.end = end
+
+    def __str__(self):
+        return 'Segment from ' + str(self.start) + ' to ' + str(self.end)
+
+    def segments(self, precision=0):
+        ''' Segments is simply the segment start -> end'''
+        return [self.start, self.end]
+
+    def length(self):
+        '''Segment length, Pythagoras theorem'''
+        s = self.end - self.start
+        return math.sqrt(s.x ** 2 + s.y ** 2)
+
+    def pdistance(self, p):
+        '''Perpendicular distance between this Segment and a given Point p'''
+        if not isinstance(p, Point):
+            return NotImplemented
+
+        if self.start == self.end:
+        # Distance from a Point to another Point is length of a segment
+            return Segment(self.start, p).length()
+
+        s = self.end - self.start
+        if s.x == 0:
+        # Vertical Segment => pdistance is the difference of abscissa
+            return abs(self.start.x - p.x)
+        else:
+        # That's 2-D perpendicular distance formulae (ref: Wikipedia)
+            slope = s.y/s.x
+            # intercept: Crossing with ordinate y-axis
+            intercept = self.start.y - (slope * self.start.x)
+            return abs(slope * p.x - p.y + intercept) / math.sqrt(slope ** 2 + 1)
+
+
+    def bbox(self):
+        xmin = min(self.start.x, self.end.x)
+        xmax = max(self.start.x, self.end.x)
+        ymin = min(self.start.y, self.end.y)
+        ymax = max(self.start.y, self.end.y)
+
+        return (Point(xmin,ymin),Point(xmax,ymax))
+
+    def transform(self, matrix):
+        self.start = matrix * self.start
+        self.end = matrix * self.end
+
+    def scale(self, ratio):
+        self.start *= ratio
+        self.end *= ratio
+    def translate(self, offset):
+        self.start += offset
+        self.end += offset
+    def rotate(self, angle):
+        self.start = self.start.rot(angle)
+        self.end = self.end.rot(angle)
+
+class Bezier:
+    '''Bezier curve class
+       A Bezier curve is defined by its control points
+       Its dimension is equal to the number of control points
+       Note that SVG only support dimension 3 and 4 Bezier curve, respectively
+       Quadratic and Cubic Bezier curve'''
+    def __init__(self, pts):
+        self.pts = list(pts)
+        self.dimension = len(pts)
+
+    def __str__(self):
+        return 'Bezier' + str(self.dimension) + \
+                ' : ' + ", ".join([str(x) for x in self.pts])
+
+    def control_point(self, n):
+        if n >= self.dimension:
+            raise LookupError('Index is larger than Bezier curve dimension')
+        else:
+            return self.pts[n]
+
+    def rlength(self):
+        '''Rough Bezier length: length of control point segments'''
+        pts = list(self.pts)
+        l = 0.0
+        p1 = pts.pop()
+        while pts:
+            p2 = pts.pop()
+            l += Segment(p1, p2).length()
+            p1 = p2
+        return l
+
+    def bbox(self):
+        return self.rbbox()
+
+    def rbbox(self):
+        '''Rough bounding box: return the bounding box (P1,P2) of the Bezier
+        _control_ points'''
+        xmin = min([p.x for p in self.pts])
+        xmax = max([p.x for p in self.pts])
+        ymin = min([p.y for p in self.pts])
+        ymax = max([p.y for p in self.pts])
+
+        return (Point(xmin,ymin), Point(xmax,ymax))
+
+    def segments(self, precision=0):
+        '''Return a polyline approximation ("segments") of the Bezier curve
+           precision is the minimum significative length of a segment'''
+        segments = []
+        # n is the number of Bezier points to draw according to precision
+        if precision != 0:
+            n = int(self.rlength() / precision) + 1
+        else:
+            n = 1000
+        if n < 10: n = 10
+        if n > 1000 : n = 1000
+
+        for t in range(0, n+1):
+            segments.append(self._bezierN(float(t)/n))
+        return segments
+
+    def _bezier1(self, p0, p1, t):
+        '''Bezier curve, one dimension
+        Compute the Point corresponding to a linear Bezier curve between
+        p0 and p1 at "time" t '''
+        pt = p0 + t * (p1 - p0)
+        return pt
+
+    def _bezierN(self, t):
+        '''Bezier curve, Nth dimension
+        Compute the point of the Nth dimension Bezier curve at "time" t'''
+        # We reduce the N Bezier control points by computing the linear Bezier
+        # point of each control point segment, creating N-1 control points
+        # until we reach one single point
+        res = list(self.pts)
+        # We store the resulting Bezier points in res[], recursively
+        for n in range(self.dimension, 1, -1):
+            # For each control point of nth dimension,
+            # compute linear Bezier point a t
+            for i in range(0,n-1):
+                res[i] = self._bezier1(res[i], res[i+1], t)
+        return res[0]
+
+    def transform(self, matrix):
+        self.pts = [matrix * x for x in self.pts]
+
+    def scale(self, ratio):
+        self.pts = [x * ratio for x in self.pts]
+    def translate(self, offset):
+        self.pts = [x + offset for x in self.pts]
+    def rotate(self, angle):
+        self.pts = [x.rot(angle) for x in self.pts]
+
+class MoveTo:
+    def __init__(self, dest):
+        self.dest = dest
+
+    def bbox(self):
+        return (self.dest, self.dest)
+
+    def transform(self, matrix):
+        self.dest = matrix * self.dest
+
+    def scale(self, ratio):
+        self.dest *= ratio
+    def translate(self, offset):
+        self.dest += offset
+    def rotate(self, angle):
+        self.dest = self.dest.rot(angle)
+
+
+def simplify_segment(segment, epsilon):
+    '''Ramer-Douglas-Peucker algorithm'''
+    if len(segment) < 3 or epsilon <= 0:
+        return segment[:]
+
+    l = Segment(segment[0], segment[-1]) # Longest segment
+
+    # Find the furthest point from the segment
+    index, maxDist = max([(i, l.pdistance(p)) for i,p in enumerate(segment)],
+            key=operator.itemgetter(1))
+
+    if maxDist > epsilon:
+        # Recursively call with segment splited in 2 on its furthest point
+        r1 = simplify_segment(segment[:index+1], epsilon)
+        r2 = simplify_segment(segment[index:], epsilon)
+        # Remove redundant 'middle' Point
+        return r1[:-1] + r2
+    else:
+        return [segment[0], segment[-1]]