--- /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]]