Mercurial > hg-public > lasercut-scripts / file comparison
comparison: svg2gcode/svg/geometry.py
svg2gcode/svg/geometry.py
- changeset 2
- 660ce16822a9
equal
deleted
inserted
replaced
| 1:0c9798d91427 | 2:660ce16822a9 |
|---|---|
| 1 # Copyright (C) 2013 -- CJlano < cjlano @ free.fr > | |
| 2 | |
| 3 # This program is free software; you can redistribute it and/or modify | |
| 4 # it under the terms of the GNU General Public License as published by | |
| 5 # the Free Software Foundation; either version 2 of the License, or | |
| 6 # (at your option) any later version. | |
| 7 # | |
| 8 # This program is distributed in the hope that it will be useful, | |
| 9 # but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 11 # GNU General Public License for more details. | |
| 12 # | |
| 13 # You should have received a copy of the GNU General Public License along | |
| 14 # with this program; if not, write to the Free Software Foundation, Inc., | |
| 15 # 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 16 | |
| 17 ''' | |
| 18 This module contains all the geometric classes and functions not directly | |
| 19 related to SVG parsing. It can be reused outside the scope of SVG. | |
| 20 ''' | |
| 21 | |
| 22 import math | |
| 23 import numbers | |
| 24 import operator | |
| 25 | |
| 26 class Point: | |
| 27 def __init__(self, x=None, y=None): | |
| 28 '''A Point is defined either by a tuple/list of length 2 or | |
| 29 by 2 coordinates | |
| 30 >>> Point(1,2) | |
| 31 (1.000,2.000) | |
| 32 >>> Point((1,2)) | |
| 33 (1.000,2.000) | |
| 34 >>> Point([1,2]) | |
| 35 (1.000,2.000) | |
| 36 >>> Point('1', '2') | |
| 37 (1.000,2.000) | |
| 38 >>> Point(('1', None)) | |
| 39 (1.000,0.000) | |
| 40 ''' | |
| 41 if (isinstance(x, tuple) or isinstance(x, list)) and len(x) == 2: | |
| 42 x,y = x | |
| 43 | |
| 44 # Handle empty parameter(s) which should be interpreted as 0 | |
| 45 if x is None: x = 0 | |
| 46 if y is None: y = 0 | |
| 47 | |
| 48 try: | |
| 49 self.x = float(x) | |
| 50 self.y = float(y) | |
| 51 except: | |
| 52 raise TypeError("A Point is defined by 2 numbers or a tuple") | |
| 53 | |
| 54 def __add__(self, other): | |
| 55 '''Add 2 points by adding coordinates. | |
| 56 Try to convert other to Point if necessary | |
| 57 >>> Point(1,2) + Point(3,2) | |
| 58 (4.000,4.000) | |
| 59 >>> Point(1,2) + (3,2) | |
| 60 (4.000,4.000)''' | |
| 61 if not isinstance(other, Point): | |
| 62 try: other = Point(other) | |
| 63 except: return NotImplemented | |
| 64 return Point(self.x + other.x, self.y + other.y) | |
| 65 | |
| 66 def __sub__(self, other): | |
| 67 '''Substract two Points. | |
| 68 >>> Point(1,2) - Point(3,2) | |
| 69 (-2.000,0.000) | |
| 70 ''' | |
| 71 if not isinstance(other, Point): | |
| 72 try: other = Point(other) | |
| 73 except: return NotImplemented | |
| 74 return Point(self.x - other.x, self.y - other.y) | |
| 75 | |
| 76 def __mul__(self, other): | |
| 77 '''Multiply a Point with a constant. | |
| 78 >>> 2 * Point(1,2) | |
| 79 (2.000,4.000) | |
| 80 >>> Point(1,2) * Point(1,2) #doctest:+IGNORE_EXCEPTION_DETAIL | |
| 81 Traceback (most recent call last): | |
| 82 ... | |
| 83 TypeError: | |
| 84 ''' | |
| 85 if not isinstance(other, numbers.Real): | |
| 86 return NotImplemented | |
| 87 return Point(self.x * other, self.y * other) | |
| 88 def __rmul__(self, other): | |
| 89 return self.__mul__(other) | |
| 90 | |
| 91 def __eq__(self, other): | |
| 92 '''Test equality | |
| 93 >>> Point(1,2) == (1,2) | |
| 94 True | |
| 95 >>> Point(1,2) == Point(2,1) | |
| 96 False | |
| 97 ''' | |
| 98 if not isinstance(other, Point): | |
| 99 try: other = Point(other) | |
| 100 except: return NotImplemented | |
| 101 return (self.x == other.x) and (self.y == other.y) | |
| 102 | |
| 103 def __repr__(self): | |
| 104 return '(' + format(self.x,'.3f') + ',' + format( self.y,'.3f') + ')' | |
| 105 | |
| 106 def __str__(self): | |
| 107 return self.__repr__(); | |
| 108 | |
| 109 def coord(self): | |
| 110 '''Return the point tuple (x,y)''' | |
| 111 return (self.x, self.y) | |
| 112 | |
| 113 def length(self): | |
| 114 '''Vector length, Pythagoras theorem''' | |
| 115 return math.sqrt(self.x ** 2 + self.y ** 2) | |
| 116 | |
| 117 def rot(self, angle): | |
| 118 '''Rotate vector [Origin,self] ''' | |
| 119 if not isinstance(angle, Angle): | |
| 120 try: angle = Angle(angle) | |
| 121 except: return NotImplemented | |
| 122 x = self.x * angle.cos - self.y * angle.sin | |
| 123 y = self.x * angle.sin + self.y * angle.cos | |
| 124 return Point(x,y) | |
| 125 | |
| 126 | |
| 127 class Angle: | |
| 128 '''Define a trigonometric angle [of a vector] ''' | |
| 129 def __init__(self, arg): | |
| 130 if isinstance(arg, numbers.Real): | |
| 131 # We precompute sin and cos for rotations | |
| 132 self.angle = arg | |
| 133 self.cos = math.cos(self.angle) | |
| 134 self.sin = math.sin(self.angle) | |
| 135 elif isinstance(arg, Point): | |
| 136 # Point angle is the trigonometric angle of the vector [origin, Point] | |
| 137 pt = arg | |
| 138 try: | |
| 139 self.cos = pt.x/pt.length() | |
| 140 self.sin = pt.y/pt.length() | |
| 141 except ZeroDivisionError: | |
| 142 self.cos = 1 | |
| 143 self.sin = 0 | |
| 144 | |
| 145 self.angle = math.acos(self.cos) | |
| 146 if self.sin < 0: | |
| 147 self.angle = -self.angle | |
| 148 else: | |
| 149 raise TypeError("Angle is defined by a number or a Point") | |
| 150 | |
| 151 def __neg__(self): | |
| 152 return Angle(Point(self.cos, -self.sin)) | |
| 153 | |
| 154 class Segment: | |
| 155 '''A segment is an object defined by 2 points''' | |
| 156 def __init__(self, start, end): | |
| 157 self.start = start | |
| 158 self.end = end | |
| 159 | |
| 160 def __str__(self): | |
| 161 return 'Segment from ' + str(self.start) + ' to ' + str(self.end) | |
| 162 | |
| 163 def segments(self, precision=0): | |
| 164 ''' Segments is simply the segment start -> end''' | |
| 165 return [self.start, self.end] | |
| 166 | |
| 167 def length(self): | |
| 168 '''Segment length, Pythagoras theorem''' | |
| 169 s = self.end - self.start | |
| 170 return math.sqrt(s.x ** 2 + s.y ** 2) | |
| 171 | |
| 172 def pdistance(self, p): | |
| 173 '''Perpendicular distance between this Segment and a given Point p''' | |
| 174 if not isinstance(p, Point): | |
| 175 return NotImplemented | |
| 176 | |
| 177 if self.start == self.end: | |
| 178 # Distance from a Point to another Point is length of a segment | |
| 179 return Segment(self.start, p).length() | |
| 180 | |
| 181 s = self.end - self.start | |
| 182 if s.x == 0: | |
| 183 # Vertical Segment => pdistance is the difference of abscissa | |
| 184 return abs(self.start.x - p.x) | |
| 185 else: | |
| 186 # That's 2-D perpendicular distance formulae (ref: Wikipedia) | |
| 187 slope = s.y/s.x | |
| 188 # intercept: Crossing with ordinate y-axis | |
| 189 intercept = self.start.y - (slope * self.start.x) | |
| 190 return abs(slope * p.x - p.y + intercept) / math.sqrt(slope ** 2 + 1) | |
| 191 | |
| 192 | |
| 193 def bbox(self): | |
| 194 xmin = min(self.start.x, self.end.x) | |
| 195 xmax = max(self.start.x, self.end.x) | |
| 196 ymin = min(self.start.y, self.end.y) | |
| 197 ymax = max(self.start.y, self.end.y) | |
| 198 | |
| 199 return (Point(xmin,ymin),Point(xmax,ymax)) | |
| 200 | |
| 201 def transform(self, matrix): | |
| 202 self.start = matrix * self.start | |
| 203 self.end = matrix * self.end | |
| 204 | |
| 205 def scale(self, ratio): | |
| 206 self.start *= ratio | |
| 207 self.end *= ratio | |
| 208 def translate(self, offset): | |
| 209 self.start += offset | |
| 210 self.end += offset | |
| 211 def rotate(self, angle): | |
| 212 self.start = self.start.rot(angle) | |
| 213 self.end = self.end.rot(angle) | |
| 214 | |
| 215 class Bezier: | |
| 216 '''Bezier curve class | |
| 217 A Bezier curve is defined by its control points | |
| 218 Its dimension is equal to the number of control points | |
| 219 Note that SVG only support dimension 3 and 4 Bezier curve, respectively | |
| 220 Quadratic and Cubic Bezier curve''' | |
| 221 def __init__(self, pts): | |
| 222 self.pts = list(pts) | |
| 223 self.dimension = len(pts) | |
| 224 | |
| 225 def __str__(self): | |
| 226 return 'Bezier' + str(self.dimension) + \ | |
| 227 ' : ' + ", ".join([str(x) for x in self.pts]) | |
| 228 | |
| 229 def control_point(self, n): | |
| 230 if n >= self.dimension: | |
| 231 raise LookupError('Index is larger than Bezier curve dimension') | |
| 232 else: | |
| 233 return self.pts[n] | |
| 234 | |
| 235 def rlength(self): | |
| 236 '''Rough Bezier length: length of control point segments''' | |
| 237 pts = list(self.pts) | |
| 238 l = 0.0 | |
| 239 p1 = pts.pop() | |
| 240 while pts: | |
| 241 p2 = pts.pop() | |
| 242 l += Segment(p1, p2).length() | |
| 243 p1 = p2 | |
| 244 return l | |
| 245 | |
| 246 def bbox(self): | |
| 247 return self.rbbox() | |
| 248 | |
| 249 def rbbox(self): | |
| 250 '''Rough bounding box: return the bounding box (P1,P2) of the Bezier | |
| 251 _control_ points''' | |
| 252 xmin = min([p.x for p in self.pts]) | |
| 253 xmax = max([p.x for p in self.pts]) | |
| 254 ymin = min([p.y for p in self.pts]) | |
| 255 ymax = max([p.y for p in self.pts]) | |
| 256 | |
| 257 return (Point(xmin,ymin), Point(xmax,ymax)) | |
| 258 | |
| 259 def segments(self, precision=0): | |
| 260 '''Return a polyline approximation ("segments") of the Bezier curve | |
| 261 precision is the minimum significative length of a segment''' | |
| 262 segments = [] | |
| 263 # n is the number of Bezier points to draw according to precision | |
| 264 if precision != 0: | |
| 265 n = int(self.rlength() / precision) + 1 | |
| 266 else: | |
| 267 n = 1000 | |
| 268 if n < 10: n = 10 | |
| 269 if n > 1000 : n = 1000 | |
| 270 | |
| 271 for t in range(0, n+1): | |
| 272 segments.append(self._bezierN(float(t)/n)) | |
| 273 return segments | |
| 274 | |
| 275 def _bezier1(self, p0, p1, t): | |
| 276 '''Bezier curve, one dimension | |
| 277 Compute the Point corresponding to a linear Bezier curve between | |
| 278 p0 and p1 at "time" t ''' | |
| 279 pt = p0 + t * (p1 - p0) | |
| 280 return pt | |
| 281 | |
| 282 def _bezierN(self, t): | |
| 283 '''Bezier curve, Nth dimension | |
| 284 Compute the point of the Nth dimension Bezier curve at "time" t''' | |
| 285 # We reduce the N Bezier control points by computing the linear Bezier | |
| 286 # point of each control point segment, creating N-1 control points | |
| 287 # until we reach one single point | |
| 288 res = list(self.pts) | |
| 289 # We store the resulting Bezier points in res[], recursively | |
| 290 for n in range(self.dimension, 1, -1): | |
| 291 # For each control point of nth dimension, | |
| 292 # compute linear Bezier point a t | |
| 293 for i in range(0,n-1): | |
| 294 res[i] = self._bezier1(res[i], res[i+1], t) | |
| 295 return res[0] | |
| 296 | |
| 297 def transform(self, matrix): | |
| 298 self.pts = [matrix * x for x in self.pts] | |
| 299 | |
| 300 def scale(self, ratio): | |
| 301 self.pts = [x * ratio for x in self.pts] | |
| 302 def translate(self, offset): | |
| 303 self.pts = [x + offset for x in self.pts] | |
| 304 def rotate(self, angle): | |
| 305 self.pts = [x.rot(angle) for x in self.pts] | |
| 306 | |
| 307 class MoveTo: | |
| 308 def __init__(self, dest): | |
| 309 self.dest = dest | |
| 310 | |
| 311 def bbox(self): | |
| 312 return (self.dest, self.dest) | |
| 313 | |
| 314 def transform(self, matrix): | |
| 315 self.dest = matrix * self.dest | |
| 316 | |
| 317 def scale(self, ratio): | |
| 318 self.dest *= ratio | |
| 319 def translate(self, offset): | |
| 320 self.dest += offset | |
| 321 def rotate(self, angle): | |
| 322 self.dest = self.dest.rot(angle) | |
| 323 | |
| 324 | |
| 325 def simplify_segment(segment, epsilon): | |
| 326 '''Ramer-Douglas-Peucker algorithm''' | |
| 327 if len(segment) < 3 or epsilon <= 0: | |
| 328 return segment[:] | |
| 329 | |
| 330 l = Segment(segment[0], segment[-1]) # Longest segment | |
| 331 | |
| 332 # Find the furthest point from the segment | |
| 333 index, maxDist = max([(i, l.pdistance(p)) for i,p in enumerate(segment)], | |
| 334 key=operator.itemgetter(1)) | |
| 335 | |
| 336 if maxDist > epsilon: | |
| 337 # Recursively call with segment splited in 2 on its furthest point | |
| 338 r1 = simplify_segment(segment[:index+1], epsilon) | |
| 339 r2 = simplify_segment(segment[index:], epsilon) | |
| 340 # Remove redundant 'middle' Point | |
| 341 return r1[:-1] + r2 | |
| 342 else: | |
| 343 return [segment[0], segment[-1]] |
