gcodetools_current_version = "1.7"

import inkex, simplestyle, simplepath

import cubicsuperpath, simpletransform, bezmisc

import os

import math

import bezmisc

import re

import copy

import sys

import time

import cmath

import numpy

import codecs

import random

import gettext

_ = gettext.gettext

if "errormsg" not in dir(inkex):

inkex.errormsg = lambda msg: sys.stderr.write((unicode(msg) + "\n").encode("UTF-8"))

def bezierslopeatt(((bx0,by0),(bx1,by1),(bx2,by2),(bx3,by3)),t):

ax,ay,bx,by,cx,cy,x0,y0=bezmisc.bezierparameterize(((bx0,by0),(bx1,by1),(bx2,by2),(bx3,by3)))

dx=3*ax*(t**2)+2*bx*t+cx

dy=3*ay*(t**2)+2*by*t+cy

if dx==dy==0 :

dx = 6*ax*t+2*bx

dy = 6*ay*t+2*by

if dx==dy==0 :

dx = 6*ax

dy = 6*ay

if dx==dy==0 :

print_("Slope error x = %s*t^3+%s*t^2+%s*t+%s, y = %s*t^3+%s*t^2+%s*t+%s, t = %s, dx==dy==0" % (ax,bx,cx,dx,ay,by,cy,dy,t))

print_(((bx0,by0),(bx1,by1),(bx2,by2),(bx3,by3)))

dx, dy = 1, 1

return dx,dy

bezmisc.bezierslopeatt = bezierslopeatt

def ireplace(self,old,new,count=0):

pattern = re.compile(re.escape(old),re.I)

return re.sub(pattern,new,self,count)

def isset(variable):

# VARIABLE NAME SHOULD BE A STRING! Like isset("foobar")

return variable in locals() or variable in globals()

math.pi2 = math.pi*2

straight_tolerance = 0.0001

straight_distance_tolerance = 0.0001

engraving_tolerance = 0.0001

loft_lengths_tolerance = 0.0000001

EMC_TOLERANCE_EQUAL = 0.00001

options = {}

defaults = {

'header': """%

""",

'footer': """

}

intersection_recursion_depth = 10

intersection_tolerance = 0.00001

styles = {

"in_out_path_style" : simplestyle.formatStyle({ 'stroke': '#0072a7', 'fill': 'none', 'stroke-width':'1', 'marker-mid':'url(#InOutPathMarker)' }),

"loft_style" : {

'main curve': simplestyle.formatStyle({ 'stroke': '#88f', 'fill': 'none', 'stroke-width':'1', 'marker-end':'url(#Arrow2Mend)' }),

},

"biarc_style" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#88f', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#8f8', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'line': simplestyle.formatStyle({ 'stroke': '#f88', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'area': simplestyle.formatStyle({ 'stroke': '#777', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.1' }),

},

"biarc_style_dark" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#33a', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#3a3', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'line': simplestyle.formatStyle({ 'stroke': '#a33', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'area': simplestyle.formatStyle({ 'stroke': '#222', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"biarc_style_dark_area" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#33a', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.1' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#3a3', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.1' }),

'line': simplestyle.formatStyle({ 'stroke': '#a33', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.1' }),

'area': simplestyle.formatStyle({ 'stroke': '#222', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"biarc_style_i" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#880', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#808', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'line': simplestyle.formatStyle({ 'stroke': '#088', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'area': simplestyle.formatStyle({ 'stroke': '#999', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"biarc_style_dark_i" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#dd5', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#d5d', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'line': simplestyle.formatStyle({ 'stroke': '#5dd', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'1' }),

'area': simplestyle.formatStyle({ 'stroke': '#aaa', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"biarc_style_lathe_feed" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#07f', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#0f7', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'line': simplestyle.formatStyle({ 'stroke': '#f44', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'area': simplestyle.formatStyle({ 'stroke': '#aaa', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"biarc_style_lathe_passing feed" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#07f', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#0f7', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'line': simplestyle.formatStyle({ 'stroke': '#f44', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'area': simplestyle.formatStyle({ 'stroke': '#aaa', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"biarc_style_lathe_fine feed" : {

'biarc0': simplestyle.formatStyle({ 'stroke': '#7f0', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'biarc1': simplestyle.formatStyle({ 'stroke': '#f70', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'line': simplestyle.formatStyle({ 'stroke': '#744', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'.4' }),

'area': simplestyle.formatStyle({ 'stroke': '#aaa', 'fill': 'none', "marker-end":"url(#DrawCurveMarker)", 'stroke-width':'0.3' }),

},

"area artefact": simplestyle.formatStyle({ 'stroke': '#ff0000', 'fill': '#ffff00', 'stroke-width':'1' }),

"area artefact arrow": simplestyle.formatStyle({ 'stroke': '#ff0000', 'fill': '#ffff00', 'stroke-width':'1' }),

"dxf_points": simplestyle.formatStyle({ "stroke": "#ff0000", "fill": "#ff0000"}),

}

def gcode_comment_str(s, replace_new_line = False):

if replace_new_line :

s = re.sub(r"[\n\r]+", ".", s)

res = ""

if s[-1] == "\n" : s = s[:-1]

for a in s.split("\n") :

if a != "" :

res += "(" + re.sub(r"[\(\)\\\n\r]", ".", a) + ")\n"

else :

res += "\n"

return res

def csp_from_polyline(line) :

return [ [ [point[:] for k in range(3) ] for point in subline ] for subline in line ]

def csp_remove_zerro_segments(csp, tolerance = 1e-7):

res = []

for subpath in csp:

if len(subpath) > 0 :

res.append([subpath[0]])

for sp1,sp2 in zip(subpath,subpath[1:]) :

if point_to_point_d2(sp1[1],sp2[1])<=tolerance and point_to_point_d2(sp1[2],sp2[1])<=tolerance and point_to_point_d2(sp1[1],sp2[0])<=tolerance :

res[-1][-1][2] = sp2[2]

else :

res[-1].append(sp2)

return res

def point_inside_csp(p,csp, on_the_path = True) :

# we'll do the raytracing and see how many intersections are there on the ray's way.

# if number of intersections is even then point is outside.

# ray will be x=p.x and y=>p.y

# you can assing any value to on_the_path, by dfault if point is on the path

# function will return thai it's inside the path.

x,y = p

ray_intersections_count = 0

for subpath in csp :

for i in range(1, len(subpath)) :

sp1, sp2 = subpath[i-1], subpath[i]

ax,ay,bx,by,cx,cy,dx,dy = csp_parameterize(sp1,sp2)

if ax==0 and bx==0 and cx==0 and dx==x :

#we've got a special case here

b = csp_true_bounds( [[sp1,sp2]])

if b[1][1]<=y<=b[3][1] :

# points is on the path

return on_the_path

else :

# we can skip this segment because it wont influence the answer.

pass

else:

for t in csp_line_intersection([x,y],[x,y+5],sp1,sp2) :

if t == 0 or t == 1 :

#we've got another special case here

x1,y1 = csp_at_t(sp1,sp2,t)

if y1==y :

# the point is on the path

return on_the_path

# if t == 0 we sould have considered this case previously.

if t == 1 :

# we have to check the next segmant if it is on the same side of the ray

st_d = csp_normalized_slope(sp1,sp2,1)[0]

if st_d == 0 : st_d = csp_normalized_slope(sp1,sp2,0.99)[0]

for j in range(1, len(subpath)+1):

if (i+j) % len(subpath) == 0 : continue # skip the closing segment

sp11,sp22 = subpath[(i-1+j) % len(subpath)], subpath[(i+j) % len(subpath)]

ax1,ay1,bx1,by1,cx1,cy1,dx1,dy1 = csp_parameterize(sp1,sp2)

if ax1==0 and bx1==0 and cx1==0 and dx1==x : continue # this segment parallel to the ray, so skip it

en_d = csp_normalized_slope(sp11,sp22,0)[0]

if en_d == 0 : en_d = csp_normalized_slope(sp11,sp22,0.01)[0]

if st_d*en_d <=0 :

ray_intersections_count += 1

break

else :

x1,y1 = csp_at_t(sp1,sp2,t)

if y1==y :

# the point is on the path

return on_the_path

else :

if y1>y and 3*ax*t**2 + 2*bx*t + cx !=0 : # if it's 0 the path only touches the ray

ray_intersections_count += 1

return ray_intersections_count%2 == 1

def csp_close_all_subpaths(csp, tolerance = 0.000001):

for i in range(len(csp)):

if point_to_point_d2(csp[i][0][1] , csp[i][-1][1])> tolerance**2 :

csp[i][-1][2] = csp[i][-1][1][:]

csp[i] += [ [csp[i][0][1][:] for j in range(3)] ]

else:

if csp[i][0][1] != csp[i][-1][1] :

csp[i][-1][1] = csp[i][0][1][:]

return csp

def csp_simple_bound(csp):

minx,miny,maxx,maxy = None,None,None,None

for subpath in csp:

for sp in subpath :

for p in sp:

minx = min(minx,p[0]) if minx!=None else p[0]

miny = min(miny,p[1]) if miny!=None else p[1]

maxx = max(maxx,p[0]) if maxx!=None else p[0]

maxy = max(maxy,p[1]) if maxy!=None else p[1]

return minx,miny,maxx,maxy

def csp_segment_to_bez(sp1,sp2) :

return sp1[1:]+sp2[:2]

def bound_to_bound_distance(sp1,sp2,sp3,sp4) :

min_dist = 1e100

max_dist = 0

points1 = csp_segment_to_bez(sp1,sp2)

points2 = csp_segment_to_bez(sp3,sp4)

for i in range(4) :

for j in range(4) :

min_, max_ = line_to_line_min_max_distance_2(points1[i-1], points1[i], points2[j-1], points2[j])

min_dist = min(min_dist,min_)

max_dist = max(max_dist,max_)

print_("bound_to_bound", min_dist, max_dist)

return min_dist, max_dist

def csp_to_point_distance(csp, p, dist_bounds = [0,1e100], tolerance=.01) :

min_dist = [1e100,0,0,0]

for j in range(len(csp)) :

for i in range(1,len(csp[j])) :

d = csp_seg_to_point_distance(csp[j][i-1],csp[j][i],p,sample_points = 5, tolerance = .01)

if d[0] < dist_bounds[0] :

return [d[0],j,i,d[1]]

else :

if d[0] < min_dist[0] : min_dist = [d[0],j,i,d[1]]

return min_dist

def csp_seg_to_point_distance(sp1,sp2,p,sample_points = 5, tolerance = .01) :

ax,ay,bx,by,cx,cy,dx,dy = csp_parameterize(sp1,sp2)

dx, dy = dx-p[0], dy-p[1]

if sample_points < 2 : sample_points = 2

d = min( [(p[0]-sp1[1][0])**2 + (p[1]-sp1[1][1])**2,0.], [(p[0]-sp2[1][0])**2 + (p[1]-sp2[1][1])**2,1.] )

for k in range(sample_points) :

t = float(k)/(sample_points-1)

i = 0

while i==0 or abs(f)>0.000001 and i<20 :

t2,t3 = t**2,t**3

f = (ax*t3+bx*t2+cx*t+dx)*(3*ax*t2+2*bx*t+cx) + (ay*t3+by*t2+cy*t+dy)*(3*ay*t2+2*by*t+cy)

df = (6*ax*t+2*bx)*(ax*t3+bx*t2+cx*t+dx) + (3*ax*t2+2*bx*t+cx)**2 + (6*ay*t+2*by)*(ay*t3+by*t2+cy*t+dy) + (3*ay*t2+2*by*t+cy)**2

if df!=0 :

t = t - f/df

else :

break

i += 1

if 0<=t<=1 :

p1 = csp_at_t(sp1,sp2,t)

d1 = (p1[0]-p[0])**2 + (p1[1]-p[1])**2

if d1 < d[0] :

d = [d1,t]

return d

def csp_seg_to_csp_seg_distance(sp1,sp2,sp3,sp4, dist_bounds = [0,1e100], sample_points = 5, tolerance=.01) :

# check the ending points first

dist = csp_seg_to_point_distance(sp1,sp2,sp3[1],sample_points, tolerance)

dist += [0.]

if dist[0] <= dist_bounds[0] : return dist

d = csp_seg_to_point_distance(sp1,sp2,sp4[1],sample_points, tolerance)

if d[0]<dist[0] :

dist = d+[1.]

if dist[0] <= dist_bounds[0] : return dist

d = csp_seg_to_point_distance(sp3,sp4,sp1[1],sample_points, tolerance)

if d[0]<dist[0] :

dist = [d[0],0.,d[1]]

if dist[0] <= dist_bounds[0] : return dist

d = csp_seg_to_point_distance(sp3,sp4,sp2[1],sample_points, tolerance)

if d[0]<dist[0] :

dist = [d[0],1.,d[1]]

if dist[0] <= dist_bounds[0] : return dist

sample_points -= 2

if sample_points < 1 : sample_points = 1

ax1,ay1,bx1,by1,cx1,cy1,dx1,dy1 = csp_parameterize(sp1,sp2)

ax2,ay2,bx2,by2,cx2,cy2,dx2,dy2 = csp_parameterize(sp3,sp4)

# try to find closes points using Newtons method

for k in range(sample_points) :

for j in range(sample_points) :

t1,t2 = float(k+1)/(sample_points+1), float(j)/(sample_points+1)

t12, t13, t22, t23 = t1*t1, t1*t1*t1, t2*t2, t2*t2*t2

i = 0

F1, F2, F = [0,0], [[0,0],[0,0]], 1e100

x,y = ax1*t13+bx1*t12+cx1*t1+dx1 - (ax2*t23+bx2*t22+cx2*t2+dx2), ay1*t13+by1*t12+cy1*t1+dy1 - (ay2*t23+by2*t22+cy2*t2+dy2)

while i<2 or abs(F-Flast)>tolerance and i<30 :

#draw_pointer(csp_at_t(sp1,sp2,t1))

f1x = 3*ax1*t12+2*bx1*t1+cx1

f1y = 3*ay1*t12+2*by1*t1+cy1

f2x = 3*ax2*t22+2*bx2*t2+cx2

f2y = 3*ay2*t22+2*by2*t2+cy2

F1[0] = 2*f1x*x + 2*f1y*y

F1[1] = -2*f2x*x - 2*f2y*y

F2[0][0] = 2*(6*ax1*t1+2*bx1)*x + 2*f1x*f1x + 2*(6*ay1*t1+2*by1)*y +2*f1y*f1y

F2[0][1] = -2*f1x*f2x - 2*f1y*f2y

F2[1][0] = -2*f2x*f1x - 2*f2y*f1y

F2[1][1] = -2*(6*ax2*t2+2*bx2)*x + 2*f2x*f2x - 2*(6*ay2*t2+2*by2)*y + 2*f2y*f2y

F2 = inv_2x2(F2)

if F2!=None :

t1 -= ( F2[0][0]*F1[0] + F2[0][1]*F1[1] )

t2 -= ( F2[1][0]*F1[0] + F2[1][1]*F1[1] )

t12, t13, t22, t23 = t1*t1, t1*t1*t1, t2*t2, t2*t2*t2

x,y = ax1*t13+bx1*t12+cx1*t1+dx1 - (ax2*t23+bx2*t22+cx2*t2+dx2), ay1*t13+by1*t12+cy1*t1+dy1 - (ay2*t23+by2*t22+cy2*t2+dy2)

Flast = F

F = x*x+y*y

else :

break

i += 1

if F < dist[0] and 0<=t1<=1 and 0<=t2<=1:

dist = [F,t1,t2]

if dist[0] <= dist_bounds[0] :

return dist

return dist

def csp_to_csp_distance(csp1,csp2, dist_bounds = [0,1e100], tolerance=.01) :

dist = [1e100,0,0,0,0,0,0]

for i1 in range(len(csp1)) :

for j1 in range(1,len(csp1[i1])) :

for i2 in range(len(csp2)) :

for j2 in range(1,len(csp2[i2])) :

d = csp_seg_bound_to_csp_seg_bound_max_min_distance(csp1[i1][j1-1],csp1[i1][j1],csp2[i2][j2-1],csp2[i2][j2])

if d[0] >= dist_bounds[1] : continue

if d[1] < dist_bounds[0] : return [d[1],i1,j1,1,i2,j2,1]

d = csp_seg_to_csp_seg_distance(csp1[i1][j1-1],csp1[i1][j1],csp2[i2][j2-1],csp2[i2][j2], dist_bounds, tolerance=tolerance)

if d[0] < dist[0] :

dist = [d[0], i1,j1,d[1], i2,j2,d[2]]

if dist[0] <= dist_bounds[0] :

return dist

if dist[0] >= dist_bounds[1] :

return dist

return dist

def csp_split(sp1,sp2,t=.5) :

[x1,y1],[x2,y2],[x3,y3],[x4,y4] = sp1[1], sp1[2], sp2[0], sp2[1]

x12 = x1+(x2-x1)*t

y12 = y1+(y2-y1)*t

x23 = x2+(x3-x2)*t

y23 = y2+(y3-y2)*t

x34 = x3+(x4-x3)*t

y34 = y3+(y4-y3)*t

x1223 = x12+(x23-x12)*t

y1223 = y12+(y23-y12)*t

x2334 = x23+(x34-x23)*t

y2334 = y23+(y34-y23)*t

x = x1223+(x2334-x1223)*t

y = y1223+(y2334-y1223)*t

return [sp1[0],sp1[1],[x12,y12]], [[x1223,y1223],[x,y],[x2334,y2334]], [[x34,y34],sp2[1],sp2[2]]

def csp_true_bounds(csp) :

# Finds minx,miny,maxx,maxy of the csp and return their (x,y,i,j,t)

minx = [float("inf"), 0, 0, 0]

maxx = [float("-inf"), 0, 0, 0]

miny = [float("inf"), 0, 0, 0]

maxy = [float("-inf"), 0, 0, 0]

for i in range(len(csp)):

for j in range(1,len(csp[i])):

ax,ay,bx,by,cx,cy,x0,y0 = bezmisc.bezierparameterize((csp[i][j-1][1],csp[i][j-1][2],csp[i][j][0],csp[i][j][1]))

roots = cubic_solver(0, 3*ax, 2*bx, cx) + [0,1]

for root in roots :

if type(root) is complex and abs(root.imag)<1e-10:

root = root.real

if type(root) is not complex and 0<=root<=1:

y = ay*(root**3)+by*(root**2)+cy*root+y0

x = ax*(root**3)+bx*(root**2)+cx*root+x0

maxx = max([x,y,i,j,root],maxx)

minx = min([x,y,i,j,root],minx)

roots = cubic_solver(0, 3*ay, 2*by, cy) + [0,1]

for root in roots :

if type(root) is complex and root.imag==0:

root = root.real

if type(root) is not complex and 0<=root<=1:

y = ay*(root**3)+by*(root**2)+cy*root+y0

x = ax*(root**3)+bx*(root**2)+cx*root+x0

maxy = max([y,x,i,j,root],maxy)

miny = min([y,x,i,j,root],miny)

maxy[0],maxy[1] = maxy[1],maxy[0]

miny[0],miny[1] = miny[1],miny[0]

return minx,miny,maxx,maxy

def csp_segments_intersection(sp1,sp2,sp3,sp4) :

a, b = csp_segment_to_bez(sp1,sp2), csp_segment_to_bez(sp3,sp4)

def polish_intersection(a,b,ta,tb, tolerance = intersection_tolerance) :

ax,ay,bx,by,cx,cy,dx,dy = bezmisc.bezierparameterize(a)

ax1,ay1,bx1,by1,cx1,cy1,dx1,dy1 = bezmisc.bezierparameterize(b)

i = 0

F, F1 = [.0,.0], [[.0,.0],[.0,.0]]

while i==0 or (abs(F[0])**2+abs(F[1])**2 > tolerance and i<10):

ta3, ta2, tb3, tb2 = ta**3, ta**2, tb**3, tb**2

F[0] = ax*ta3+bx*ta2+cx*ta+dx-ax1*tb3-bx1*tb2-cx1*tb-dx1

F[1] = ay*ta3+by*ta2+cy*ta+dy-ay1*tb3-by1*tb2-cy1*tb-dy1

F1[0][0] = 3*ax *ta2 + 2*bx *ta + cx

F1[0][1] = -3*ax1*tb2 - 2*bx1*tb - cx1

F1[1][0] = 3*ay *ta2 + 2*by *ta + cy

F1[1][1] = -3*ay1*tb2 - 2*by1*tb - cy1

det = F1[0][0]*F1[1][1] - F1[0][1]*F1[1][0]

if det!=0 :

F1 = [ [ F1[1][1]/det, -F1[0][1]/det], [-F1[1][0]/det, F1[0][0]/det] ]

ta = ta - ( F1[0][0]*F[0] + F1[0][1]*F[1] )

tb = tb - ( F1[1][0]*F[0] + F1[1][1]*F[1] )

else: break

i += 1

return ta, tb

def recursion(a,b, ta0,ta1,tb0,tb1, depth_a,depth_b) :

global bezier_intersection_recursive_result

if a==b :

bezier_intersection_recursive_result += [[ta0,tb0,ta1,tb1,"Overlap"]]

return

tam, tbm = (ta0+ta1)/2, (tb0+tb1)/2

if depth_a>0 and depth_b>0 :

a1,a2 = bez_split(a,0.5)

b1,b2 = bez_split(b,0.5)

if bez_bounds_intersect(a1,b1) : recursion(a1,b1, ta0,tam,tb0,tbm, depth_a-1,depth_b-1)

if bez_bounds_intersect(a2,b1) : recursion(a2,b1, tam,ta1,tb0,tbm, depth_a-1,depth_b-1)

if bez_bounds_intersect(a1,b2) : recursion(a1,b2, ta0,tam,tbm,tb1, depth_a-1,depth_b-1)

if bez_bounds_intersect(a2,b2) : recursion(a2,b2, tam,ta1,tbm,tb1, depth_a-1,depth_b-1)

elif depth_a>0 :

a1,a2 = bez_split(a,0.5)

if bez_bounds_intersect(a1,b) : recursion(a1,b, ta0,tam,tb0,tb1, depth_a-1,depth_b)

if bez_bounds_intersect(a2,b) : recursion(a2,b, tam,ta1,tb0,tb1, depth_a-1,depth_b)

elif depth_b>0 :

b1,b2 = bez_split(b,0.5)

if bez_bounds_intersect(a,b1) : recursion(a,b1, ta0,ta1,tb0,tbm, depth_a,depth_b-1)

if bez_bounds_intersect(a,b2) : recursion(a,b2, ta0,ta1,tbm,tb1, depth_a,depth_b-1)

else : # Both segments have been subdevided enougth. Let's get some intersections :).

intersection, t1, t2 = straight_segments_intersection([a[0]]+[a[3]],[b[0]]+[b[3]])

if intersection :

if intersection == "Overlap" :

t1 = ( max(0,min(1,t1[0]))+max(0,min(1,t1[1])) )/2

t2 = ( max(0,min(1,t2[0]))+max(0,min(1,t2[1])) )/2

bezier_intersection_recursive_result += [[ta0+t1*(ta1-ta0),tb0+t2*(tb1-tb0)]]

global bezier_intersection_recursive_result

bezier_intersection_recursive_result = []

recursion(a,b,0.,1.,0.,1.,intersection_recursion_depth,intersection_recursion_depth)

intersections = bezier_intersection_recursive_result

for i in range(len(intersections)) :

if len(intersections[i])<5 or intersections[i][4] != "Overlap" :

intersections[i] = polish_intersection(a,b,intersections[i][0],intersections[i][1])

return intersections

def csp_segments_true_intersection(sp1,sp2,sp3,sp4) :

intersections = csp_segments_intersection(sp1,sp2,sp3,sp4)

res = []

for intersection in intersections :

if (

(len(intersection)==5 and intersection[4] == "Overlap" and (0<=intersection[0]<=1 or 0<=intersection[1]<=1) and (0<=intersection[2]<=1 or 0<=intersection[3]<=1) )

or ( 0<=intersection[0]<=1 and 0<=intersection[1]<=1 )

) :

res += [intersection]

return res

def csp_get_t_at_curvature(sp1,sp2,c, sample_points = 16):

# returns a list containning [t1,t2,t3,...,tn], 0<=ti<=1...

if sample_points < 2 : sample_points = 2

tolerance = .0000000001

res = []

ax,ay,bx,by,cx,cy,dx,dy = csp_parameterize(sp1,sp2)

for k in range(sample_points) :

t = float(k)/(sample_points-1)

i, F = 0, 1e100

while i<2 or abs(F)>tolerance and i<17 :

try : # some numerical calculation could exceed the limits

t2 = t*t

#slopes...

f1x = 3*ax*t2+2*bx*t+cx

f1y = 3*ay*t2+2*by*t+cy

f2x = 6*ax*t+2*bx

f2y = 6*ay*t+2*by

f3x = 6*ax

f3y = 6*ay

d = (f1x**2+f1y**2)**1.5

F1 = (

( (f1x*f3y-f3x*f1y)*d - (f1x*f2y-f2x*f1y)*3.*(f2x*f1x+f2y*f1y)*((f1x**2+f1y**2)**.5) ) /

((f1x**2+f1y**2)**3)

)

F = (f1x*f2y-f1y*f2x)/d - c

t -= F/F1

except:

break

i += 1

if 0<=t<=1 and F<=tolerance:

if len(res) == 0 :

res.append(t)

for i in res :

if abs(t-i)<=0.001 :

break

if not abs(t-i)<=0.001 :

res.append(t)

return res

def csp_max_curvature(sp1,sp2):

ax,ay,bx,by,cx,cy,dx,dy = csp_parameterize(sp1,sp2)

tolerance = .0001

F = 0.

i = 0

while i<2 or F-Flast<tolerance and i<10 :

t = .5

f1x = 3*ax*t**2 + 2*bx*t + cx

f1y = 3*ay*t**2 + 2*by*t + cy

f2x = 6*ax*t + 2*bx

f2y = 6*ay*t + 2*by

f3x = 6*ax

f3y = 6*ay

d = pow(f1x**2+f1y**2,1.5)

if d != 0 :

Flast = F

F = (f1x*f2y-f1y*f2x)/d

F1 = (

( d*(f1x*f3y-f3x*f1y) - (f1x*f2y-f2x*f1y)*3.*(f2x*f1x+f2y*f1y)*pow(f1x**2+f1y**2,.5) ) /

(f1x**2+f1y**2)**3

)

i+=1

if F1!=0:

t -= F/F1

else:

break

else: break

return t

def csp_curvature_at_t(sp1,sp2,t, depth = 3) :

ax,ay,bx,by,cx,cy,dx,dy = bezmisc.bezierparameterize(csp_segment_to_bez(sp1,sp2))

#curvature = (x'y''-y'x'') / (x'^2+y'^2)^1.5

f1x = 3*ax*t**2 + 2*bx*t + cx

f1y = 3*ay*t**2 + 2*by*t + cy

f2x = 6*ax*t + 2*bx

f2y = 6*ay*t + 2*by

d = (f1x**2+f1y**2)**1.5

if d != 0 :

return (f1x*f2y-f1y*f2x)/d

else :

t1 = f1x*f2y-f1y*f2x

if t1 > 0 : return 1e100

if t1 < 0 : return -1e100

# Use the Lapitals rule to solve 0/0 problem for 2 times...

t1 = 2*(bx*ay-ax*by)*t+(ay*cx-ax*cy)

if t1 > 0 : return 1e100

if t1 < 0 : return -1e100

t1 = bx*ay-ax*by

if t1 > 0 : return 1e100

if t1 < 0 : return -1e100

if depth>0 :

# little hack ;^) hope it wont influence anything...

return csp_curvature_at_t(sp1,sp2,t*1.004, depth-1)

return 1e100

def csp_curvature_radius_at_t(sp1,sp2,t) :

c = csp_curvature_at_t(sp1,sp2,t)

if c == 0 : return 1e100

else: return 1/c

def csp_special_points(sp1,sp2) :

# special points = curvature == 0

ax,ay,bx,by,cx,cy,dx,dy = bezmisc.bezierparameterize((sp1[1],sp1[2],sp2[0],sp2[1]))

a = 3*ax*by-3*ay*bx

b = 3*ax*cy-3*cx*ay

c = bx*cy-cx*by

roots = cubic_solver(0, a, b, c)

res = []

for i in roots :

if type(i) is complex and i.imag==0:

i = i.real

if type(i) is not complex and 0<=i<=1:

res.append(i)

return res

def csp_subpath_ccw(subpath):

# Remove all zerro length segments

s = 0

#subpath = subpath[:]

if (P(subpath[-1][1])-P(subpath[0][1])).l2() > 1e-10 :

subpath[-1][2] = subpath[-1][1]

subpath[0][0] = subpath[0][1]

subpath += [ [subpath[0][1],subpath[0][1],subpath[0][1]] ]

pl = subpath[-1][2]

for sp1 in subpath:

for p in sp1 :

s += (p[0]-pl[0])*(p[1]+pl[1])

pl = p

return s<0

def csp_at_t(sp1,sp2,t):

ax,bx,cx,dx = sp1[1][0], sp1[2][0], sp2[0][0], sp2[1][0]

ay,by,cy,dy = sp1[1][1], sp1[2][1], sp2[0][1], sp2[1][1]

x1, y1 = ax+(bx-ax)*t, ay+(by-ay)*t

x2, y2 = bx+(cx-bx)*t, by+(cy-by)*t

x3, y3 = cx+(dx-cx)*t, cy+(dy-cy)*t

x4,y4 = x1+(x2-x1)*t, y1+(y2-y1)*t

x5,y5 = x2+(x3-x2)*t, y2+(y3-y2)*t

x,y = x4+(x5-x4)*t, y4+(y5-y4)*t

return [x,y]

def csp_at_length(sp1,sp2,l=0.5, tolerance = 0.01):

bez = (sp1[1][:],sp1[2][:],sp2[0][:],sp2[1][:])

t = bezmisc.beziertatlength(bez, l, tolerance)

return csp_at_t(sp1,sp2,t)

def csp_splitatlength(sp1, sp2, l = 0.5, tolerance = 0.01):

bez = (sp1[1][:],sp1[2][:],sp2[0][:],sp2[1][:])

t = bezmisc.beziertatlength(bez, l, tolerance)

return csp_split(sp1, sp2, t)

def cspseglength(sp1,sp2, tolerance = 0.01):

bez = (sp1[1][:],sp1[2][:],sp2[0][:],sp2[1][:])

return bezmisc.bezierlength(bez, tolerance)

def csplength(csp):

total = 0

lengths = []

for sp in csp:

for i in xrange(1,len(sp)):

l = cspseglength(sp[i-1],sp[i])

lengths.append(l)

total += l

return lengths, total

def csp_segments(csp):

l, seg = 0, [0]

for sp in csp:

for i in xrange(1,len(sp)):

l += cspseglength(sp[i-1],sp[i])

seg += [ l ]

if l>0 :

seg = [seg[i]/l for i in xrange(len(seg))]

return seg,l

def rebuild_csp (csp, segs, s=None):

# rebuild_csp() adds to csp control points making it's segments looks like segs

if s==None : s, l = csp_segments(csp)

if len(s)>len(segs) : return None

segs = segs[:]

segs.sort()

for i in xrange(len(s)):

d = None

for j in xrange(len(segs)):

d = min( [abs(s[i]-segs[j]),j], d) if d!=None else [abs(s[i]-segs[j]),j]

del segs[d[1]]

for i in xrange(len(segs)):

for j in xrange(0,len(s)):

if segs[i]<s[j] : break

if s[j]-s[j-1] != 0 :

t = (segs[i] - s[j-1])/(s[j]-s[j-1])

sp1,sp2,sp3 = csp_split(csp[j-1],csp[j], t)

csp = csp[:j-1] + [sp1,sp2,sp3] + csp[j+1:]

s = s[:j] + [ s[j-1]*(1-t)+s[j]*t ] + s[j:]

return csp, s

def csp_slope(sp1,sp2,t):

bez = (sp1[1][:],sp1[2][:],sp2[0][:],sp2[1][:])

return bezmisc.bezierslopeatt(bez,t)

def csp_line_intersection(l1,l2,sp1,sp2):

dd=l1[0]

cc=l2[0]-l1[0]

bb=l1[1]

aa=l2[1]-l1[1]

if aa==cc==0 : return []

if aa:

coef1=cc/aa

coef2=1

else:

coef1=1

coef2=aa/cc

bez = (sp1[1][:],sp1[2][:],sp2[0][:],sp2[1][:])

ax,ay,bx,by,cx,cy,x0,y0=bezmisc.bezierparameterize(bez)

a=coef1*ay-coef2*ax

b=coef1*by-coef2*bx

c=coef1*cy-coef2*cx

d=coef1*(y0-bb)-coef2*(x0-dd)

roots = cubic_solver(a,b,c,d)

retval = []

for i in roots :

if type(i) is complex and abs(i.imag)<1e-7:

i = i.real

if type(i) is not complex and -1e-10<=i<=1.+1e-10:

retval.append(i)

return retval

def csp_split_by_two_points(sp1,sp2,t1,t2) :

if t1>t2 : t1, t2 = t2, t1

if t1 == t2 :

sp1,sp2,sp3 = csp_split(sp1,sp2,t)

return [sp1,sp2,sp2,sp3]

elif t1 <= 1e-10 and t2 >= 1.-1e-10 :

return [sp1,sp1,sp2,sp2]

elif t1 <= 1e-10:

sp1,sp2,sp3 = csp_split(sp1,sp2,t2)

return [sp1,sp1,sp2,sp3]

elif t2 >= 1.-1e-10 :

sp1,sp2,sp3 = csp_split(sp1,sp2,t1)

return [sp1,sp2,sp3,sp3]

else:

sp1,sp2,sp3 = csp_split(sp1,sp2,t1)

sp2,sp3,sp4 = csp_split(sp2,sp3,(t2-t1)/(1-t1) )

return [sp1,sp2,sp3,sp4]

def csp_seg_split(sp1,sp2, points):

# points is float=t or list [t1, t2, ..., tn]

if type(points) is float :

points = [points]

points.sort()

res = [sp1,sp2]

last_t = 0

for t in points:

if 1e-10<t<1.-1e-10 :

sp3,sp4,sp5 = csp_split(res[-2],res[-1], (t-last_t)/(1-last_t))

last_t = t

res[-2:] = [sp3,sp4,sp5]

return res

def csp_subpath_split_by_points(subpath, points) :

# points are [[i,t]...] where i-segment's number

points.sort()

points = [[1,0.]] + points + [[len(subpath)-1,1.]]

parts = []

for int1,int2 in zip(points,points[1:]) :

if int1==int2 :

continue

if int1[1] == 1. :

int1[0] += 1

int1[1] = 0.

if int1==int2 :

continue

if int2[1] == 0. :

int2[0] -= 1

int2[1] = 1.

if int1[0] == 0 and int2[0]==len(subpath)-1:# and small(int1[1]) and small(int2[1]-1) :

continue

if int1[0]==int2[0] : # same segment

sp = csp_split_by_two_points(subpath[int1[0]-1],subpath[int1[0]],int1[1], int2[1])

if sp[1]!=sp[2] :

parts += [ [sp[1],sp[2]] ]

else :

sp5,sp1,sp2 = csp_split(subpath[int1[0]-1],subpath[int1[0]],int1[1])

sp3,sp4,sp5 = csp_split(subpath[int2[0]-1],subpath[int2[0]],int2[1])

if int1[0]==int2[0]-1 :

parts += [ [sp1, [sp2[0],sp2[1],sp3[2]], sp4] ]

else :

parts += [ [sp1,sp2]+subpath[int1[0]+1:int2[0]-1]+[sp3,sp4] ]

return parts

def arc_from_s_r_n_l(s,r,n,l) :

if abs(n[0]**2+n[1]**2 - 1) > 1e-10 : n = normalize(n)

return arc_from_c_s_l([s[0]+n[0]*r, s[1]+n[1]*r],s,l)

def arc_from_c_s_l(c,s,l) :

r = point_to_point_d(c,s)

if r == 0 : return []

alpha = l/r

cos_, sin_ = math.cos(alpha), math.sin(alpha)

e = [ c[0] + (s[0]-c[0])*cos_ - (s[1]-c[1])*sin_, c[1] + (s[0]-c[0])*sin_ + (s[1]-c[1])*cos_]

n = [c[0]-s[0],c[1]-s[1]]

slope = rotate_cw(n) if l>0 else rotate_ccw(n)

return csp_from_arc(s, e, c, r, slope)

def csp_from_arc(start, end, center, r, slope_st) :

# Creates csp that approximise specified arc

r = abs(r)

alpha = (atan2(end[0]-center[0],end[1]-center[1]) - atan2(start[0]-center[0],start[1]-center[1])) % math.pi2

sectors = int(abs(alpha)*2/math.pi)+1

alpha_start = atan2(start[0]-center[0],start[1]-center[1])

cos_,sin_ = math.cos(alpha_start), math.sin(alpha_start)

k = (4.*math.tan(alpha/sectors/4.)/3.)

if dot(slope_st , [- sin_*k*r, cos_*k*r]) < 0 :

if alpha>0 : alpha -= math.pi2

else: alpha += math.pi2

if abs(alpha*r)<0.001 :

return []

sectors = int(abs(alpha)*2/math.pi)+1

k = (4.*math.tan(alpha/sectors/4.)/3.)

result = []

for i in range(sectors+1) :

cos_,sin_ = math.cos(alpha_start + alpha*i/sectors), math.sin(alpha_start + alpha*i/sectors)

sp = [ [], [center[0] + cos_*r, center[1] + sin_*r], [] ]

sp[0] = [sp[1][0] + sin_*k*r, sp[1][1] - cos_*k*r ]

sp[2] = [sp[1][0] - sin_*k*r, sp[1][1] + cos_*k*r ]

result += [sp]

result[0][0] = result[0][1][:]

result[-1][2] = result[-1][1]

return result

def point_to_arc_distance(p, arc):

### Distance calculattion from point to arc

P0,P2,c,a = arc

dist = None

p = P(p)

r = (P0-c).mag()

if r>0 :

i = c + (p-c).unit()*r

alpha = ((i-c).angle() - (P0-c).angle())

if a*alpha<0:

if alpha>0: alpha = alpha-math.pi2

else: alpha = math.pi2+alpha

if between(alpha,0,a) or min(abs(alpha),abs(alpha-a))<straight_tolerance :

return (p-i).mag(), [i.x, i.y]

else :

d1, d2 = (p-P0).mag(), (p-P2).mag()

if d1<d2 :

return (d1, [P0.x,P0.y])

else :

return (d2, [P2.x,P2.y])

def csp_to_arc_distance(sp1,sp2, arc1, arc2, tolerance = 0.01 ): # arc = [start,end,center,alpha]

n, i = 10, 0

d, d1, dl = (0,(0,0)), (0,(0,0)), 0

while i<1 or (abs(d1[0]-dl[0])>tolerance and i<4):

i += 1

dl = d1*1

for j in range(n+1):

t = float(j)/n

p = csp_at_t(sp1,sp2,t)

d = min(point_to_arc_distance(p,arc1), point_to_arc_distance(p,arc2))

d1 = max(d1,d)

n=n*2

return d1[0]

def csp_simple_bound_to_point_distance(p, csp):

minx,miny,maxx,maxy = None,None,None,None

for subpath in csp:

for sp in subpath:

for p_ in sp:

minx = min(minx,p_[0]) if minx!=None else p_[0]

miny = min(miny,p_[1]) if miny!=None else p_[1]

maxx = max(maxx,p_[0]) if maxx!=None else p_[0]

maxy = max(maxy,p_[1]) if maxy!=None else p_[1]

return math.sqrt(max(minx-p[0],p[0]-maxx,0)**2+max(miny-p[1],p[1]-maxy,0)**2)

def csp_point_inside_bound(sp1, sp2, p):

bez = [sp1[1],sp1[2],sp2[0],sp2[1]]

x,y = p

c = 0

#CLT added test of x in range

xmin=1e100

xmax=-1e100

for i in range(4):

[x0,y0], [x1,y1] = bez[i-1], bez[i]

xmin=min(xmin,x0)

xmax=max(xmax,x0)

if x0-x1!=0 and (y-y0)*(x1-x0)>=(x-x0)*(y1-y0) and x>min(x0,x1) and x<=max(x0,x1) :

c +=1

return xmin<=x<=xmax and c%2==0

def csp_bound_to_point_distance(sp1, sp2, p):

if csp_point_inside_bound(sp1, sp2, p) :

return 0.

bez = csp_segment_to_bez(sp1,sp2)

min_dist = 1e100

for i in range(0,4):

d = point_to_line_segment_distance_2(p, bez[i-1],bez[i])

if d <= min_dist : min_dist = d

return min_dist

def line_line_intersect(p1,p2,p3,p4) : # Return only true intersection.

if (p1[0]==p2[0] and p1[1]==p2[1]) or (p3[0]==p4[0] and p3[1]==p4[1]) : return False

x = (p2[0]-p1[0])*(p4[1]-p3[1]) - (p2[1]-p1[1])*(p4[0]-p3[0])

if x==0 : # Lines are parallel

if (p3[0]-p1[0])*(p2[1]-p1[1]) == (p3[1]-p1[1])*(p2[0]-p1[0]) :

if p3[0]!=p4[0] :

t11 = (p1[0]-p3[0])/(p4[0]-p3[0])

t12 = (p2[0]-p3[0])/(p4[0]-p3[0])

t21 = (p3[0]-p1[0])/(p2[0]-p1[0])

t22 = (p4[0]-p1[0])/(p2[0]-p1[0])

else:

t11 = (p1[1]-p3[1])/(p4[1]-p3[1])

t12 = (p2[1]-p3[1])/(p4[1]-p3[1])

t21 = (p3[1]-p1[1])/(p2[1]-p1[1])

t22 = (p4[1]-p1[1])/(p2[1]-p1[1])

return ("Overlap" if (0<=t11<=1 or 0<=t12<=1) and (0<=t21<=1 or 0<=t22<=1) else False)

else: return False

else :

return (

0<=((p4[0]-p3[0])*(p1[1]-p3[1]) - (p4[1]-p3[1])*(p1[0]-p3[0]))/x<=1 and

0<=((p2[0]-p1[0])*(p1[1]-p3[1]) - (p2[1]-p1[1])*(p1[0]-p3[0]))/x<=1 )

def line_line_intersection_points(p1,p2,p3,p4) : # Return only points [ (x,y) ]

if (p1[0]==p2[0] and p1[1]==p2[1]) or (p3[0]==p4[0] and p3[1]==p4[1]) : return []

x = (p2[0]-p1[0])*(p4[1]-p3[1]) - (p2[1]-p1[1])*(p4[0]-p3[0])

if x==0 : # Lines are parallel

if (p3[0]-p1[0])*(p2[1]-p1[1]) == (p3[1]-p1[1])*(p2[0]-p1[0]) :

if p3[0]!=p4[0] :

t11 = (p1[0]-p3[0])/(p4[0]-p3[0])

t12 = (p2[0]-p3[0])/(p4[0]-p3[0])

t21 = (p3[0]-p1[0])/(p2[0]-p1[0])

t22 = (p4[0]-p1[0])/(p2[0]-p1[0])

else:

t11 = (p1[1]-p3[1])/(p4[1]-p3[1])

t12 = (p2[1]-p3[1])/(p4[1]-p3[1])

t21 = (p3[1]-p1[1])/(p2[1]-p1[1])

t22 = (p4[1]-p1[1])/(p2[1]-p1[1])

res = []

if (0<=t11<=1 or 0<=t12<=1) and (0<=t21<=1 or 0<=t22<=1) :

if 0<=t11<=1 : res += [p1]

if 0<=t12<=1 : res += [p2]

if 0<=t21<=1 : res += [p3]

if 0<=t22<=1 : res += [p4]

return res

else: return []

else :

t1 = ((p4[0]-p3[0])*(p1[1]-p3[1]) - (p4[1]-p3[1])*(p1[0]-p3[0]))/x

t2 = ((p2[0]-p1[0])*(p1[1]-p3[1]) - (p2[1]-p1[1])*(p1[0]-p3[0]))/x

if 0<=t1<=1 and 0<=t2<=1 : return [ [p1[0]*(1-t1)+p2[0]*t1, p1[1]*(1-t1)+p2[1]*t1] ]

else : return []

def point_to_point_d2(a,b):

return (a[0]-b[0])**2 + (a[1]-b[1])**2

def point_to_point_d(a,b):

return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

def point_to_line_segment_distance_2(p1, p2,p3) :

# p1 - point, p2,p3 - line segment

#draw_pointer(p1)

w0 = [p1[0]-p2[0], p1[1]-p2[1]]

v = [p3[0]-p2[0], p3[1]-p2[1]]

c1 = w0[0]*v[0] + w0[1]*v[1]

if c1 <= 0 :

return w0[0]*w0[0]+w0[1]*w0[1]

c2 = v[0]*v[0] + v[1]*v[1]

if c2 <= c1 :

return (p1[0]-p3[0])**2 + (p1[1]-p3[1])**2

return (p1[0]- p2[0]-v[0]*c1/c2)**2 + (p1[1]- p2[1]-v[1]*c1/c2)

def line_to_line_distance_2(p1,p2,p3,p4):

if line_line_intersect(p1,p2,p3,p4) : return 0

return min(

point_to_line_segment_distance_2(p1,p3,p4),

point_to_line_segment_distance_2(p2,p3,p4),

point_to_line_segment_distance_2(p3,p1,p2),

point_to_line_segment_distance_2(p4,p1,p2))

def csp_seg_bound_to_csp_seg_bound_max_min_distance(sp1,sp2,sp3,sp4) :

bez1 = csp_segment_to_bez(sp1,sp2)

bez2 = csp_segment_to_bez(sp3,sp4)

min_dist = 1e100

max_dist = 0.

for i in range(4) :

if csp_point_inside_bound(sp1, sp2, bez2[i]) or csp_point_inside_bound(sp3, sp4, bez1[i]) :

min_dist = 0.

break

for i in range(4) :

for j in range(4) :

d = line_to_line_distance_2(bez1[i-1],bez1[i],bez2[j-1],bez2[j])

if d < min_dist : min_dist = d

d = (bez2[j][0]-bez1[i][0])**2 + (bez2[j][1]-bez1[i][1])**2

if max_dist < d : max_dist = d

return min_dist, max_dist

def csp_reverse(csp) :

for i in range(len(csp)) :

n = []

for j in csp[i] :

n = [ [j[2][:],j[1][:],j[0][:]] ] + n

csp[i] = n[:]

return csp

def csp_normalized_slope(sp1,sp2,t) :

ax,ay,bx,by,cx,cy,dx,dy=bezmisc.bezierparameterize((sp1[1][:],sp1[2][:],sp2[0][:],sp2[1][:]))

if sp1[1]==sp2[1]==sp1[2]==sp2[0] : return [1.,0.]

f1x = 3*ax*t*t+2*bx*t+cx

f1y = 3*ay*t*t+2*by*t+cy

if abs(f1x*f1x+f1y*f1y) > 1e-9 : #LT changed this from 1e-20, which caused problems

l = math.sqrt(f1x*f1x+f1y*f1y)

return [f1x/l, f1y/l]

if t == 0 :

f1x = sp2[0][0]-sp1[1][0]

f1y = sp2[0][1]-sp1[1][1]

if abs(f1x*f1x+f1y*f1y) > 1e-9 : #LT changed this from 1e-20, which caused problems

l = math.sqrt(f1x*f1x+f1y*f1y)

return [f1x/l, f1y/l]

else :

f1x = sp2[1][0]-sp1[1][0]

f1y = sp2[1][1]-sp1[1][1]

if f1x*f1x+f1y*f1y != 0 :

l = math.sqrt(f1x*f1x+f1y*f1y)

return [f1x/l, f1y/l]

elif t == 1 :

f1x = sp2[1][0]-sp1[2][0]

f1y = sp2[1][1]-sp1[2][1]

if abs(f1x*f1x+f1y*f1y) > 1e-9 :

l = math.sqrt(f1x*f1x+f1y*f1y)

return [f1x/l, f1y/l]

else :

f1x = sp2[1][0]-sp1[1][0]

f1y = sp2[1][1]-sp1[1][1]

if f1x*f1x+f1y*f1y != 0 :

l = math.sqrt(f1x*f1x+f1y*f1y)

return [f1x/l, f1y/l]

else :

return [1.,0.]

def csp_normalized_normal(sp1,sp2,t) :

nx,ny = csp_normalized_slope(sp1,sp2,t)

return [-ny, nx]

def csp_parameterize(sp1,sp2):

return bezmisc.bezierparameterize(csp_segment_to_bez(sp1,sp2))

def csp_concat_subpaths(*s):

def concat(s1,s2) :

if s1 == [] : return s2

if s2 == [] : return s1

if (s1[-1][1][0]-s2[0][1][0])**2 + (s1[-1][1][1]-s2[0][1][1])**2 > 0.00001 :

return s1[:-1]+[ [s1[-1][0],s1[-1][1],s1[-1][1]], [s2[0][1],s2[0][1],s2[0][2]] ] + s2[1:]

else :

return s1[:-1]+[ [s1[-1][0],s2[0][1],s2[0][2]] ] + s2[1:]

if len(s) == 0 : return []

if len(s) ==1 : return s[0]

result = s[0]

for s1 in s[1:]:

result = concat(result,s1)

return result

def csp_subpaths_end_to_start_distance2(s1,s2):

return (s1[-1][1][0]-s2[0][1][0])**2 + (s1[-1][1][1]-s2[0][1][1])**2

def csp_clip_by_line(csp,l1,l2) :

result = []

for i in range(len(csp)):

s = csp[i]

intersections = []

for j in range(1,len(s)) :

intersections += [ [j,int_] for int_ in csp_line_intersection(l1,l2,s[j-1],s[j])]

splitted_s = csp_subpath_split_by_points(s, intersections)

for s in splitted_s[:] :

clip = False

for p in csp_true_bounds([s]) :

if (l1[1]-l2[1])*p[0] + (l2[0]-l1[0])*p[1] + (l1[0]*l2[1]-l2[0]*l1[1])<-0.01 :

clip = True

break

if clip :

splitted_s.remove(s)

result += splitted_s

return result

def csp_subpath_line_to(subpath, points, prepend = False) :

# Appends subpath with line or polyline.

if len(points)>0 :

if not prepend :

if len(subpath)>0:

subpath[-1][2] = subpath[-1][1][:]

if type(points[0]) == type([1,1]) :

for p in points :

subpath += [ [p[:],p[:],p[:]] ]

else:

subpath += [ [points,points,points] ]

else :

if len(subpath)>0:

subpath[0][0] = subpath[0][1][:]

if type(points[0]) == type([1,1]) :

for p in points :

subpath = [ [p[:],p[:],p[:]] ] + subpath

else:

subpath = [ [points,points,points] ] + subpath

return subpath

def csp_join_subpaths(csp) :

result = csp[:]

done_smf = True

joined_result = []

while done_smf :

done_smf = False

while len(result)>0:

s1 = result[-1][:]

del(result[-1])

j = 0

joined_smf = False

while j<len(joined_result) :

if csp_subpaths_end_to_start_distance2(joined_result[j],s1) <0.000001 :

joined_result[j] = csp_concat_subpaths(joined_result[j],s1)

done_smf = True

joined_smf = True

break

if csp_subpaths_end_to_start_distance2(s1,joined_result[j]) <0.000001 :

joined_result[j] = csp_concat_subpaths(s1,joined_result[j])

done_smf = True

joined_smf = True

break

j += 1

if not joined_smf : joined_result += [s1[:]]

if done_smf :

result = joined_result[:]

joined_result = []

return joined_result

def triangle_cross(a,b,c):

return (a[0]-b[0])*(c[1]-b[1]) - (c[0]-b[0])*(a[1]-b[1])

def csp_segment_convex_hull(sp1,sp2):

a,b,c,d = sp1[1][:], sp1[2][:], sp2[0][:], sp2[1][:]

abc = triangle_cross(a,b,c)

abd = triangle_cross(a,b,d)

bcd = triangle_cross(b,c,d)

cad = triangle_cross(c,a,d)

if abc == 0 and abd == 0 : return [min(a,b,c,d), max(a,b,c,d)]

if abc == 0 : return [d, min(a,b,c), max(a,b,c)]

if abd == 0 : return [c, min(a,b,d), max(a,b,d)]

if bcd == 0 : return [a, min(b,c,d), max(b,c,d)]

if cad == 0 : return [b, min(c,a,d), max(c,a,d)]

m1, m2, m3 = abc*abd>0, abc*bcd>0, abc*cad>0

if m1 and m2 and m3 : return [a,b,c]

if m1 and m2 and not m3 : return [a,b,c,d]

if m1 and not m2 and m3 : return [a,b,d,c]

if not m1 and m2 and m3 : return [a,d,b,c]

if m1 and not (m2 and m3) : return [a,b,d]

if not (m1 and m2) and m3 : return [c,a,d]

if not (m1 and m3) and m2 : return [b,c,d]

raise ValueError, "csp_segment_convex_hull happend something that shouldnot happen!"

def bez_bounds_intersect(bez1, bez2) :

return bounds_intersect(bez_bound(bez2), bez_bound(bez1))

def bez_bound(bez) :

return [

min(bez[0][0], bez[1][0], bez[2][0], bez[3][0]),

min(bez[0][1], bez[1][1], bez[2][1], bez[3][1]),

max(bez[0][0], bez[1][0], bez[2][0], bez[3][0]),

max(bez[0][1], bez[1][1], bez[2][1], bez[3][1]),

]

def bounds_intersect(a, b) :

return not ( (a[0]>b[2]) or (b[0]>a[2]) or (a[1]>b[3]) or (b[1]>a[3]) )

def tpoint((x1,y1),(x2,y2),t):

return [x1+t*(x2-x1),y1+t*(y2-y1)]

def bez_to_csp_segment(bez) :

return [bez[0],bez[0],bez[1]], [bez[2],bez[3],bez[3]]

def bez_split(a,t=0.5) :

a1 = tpoint(a[0],a[1],t)

at = tpoint(a[1],a[2],t)

b2 = tpoint(a[2],a[3],t)

a2 = tpoint(a1,at,t)

b1 = tpoint(b2,at,t)

a3 = tpoint(a2,b1,t)

return [a[0],a1,a2,a3], [a3,b1,b2,a[3]]

def bez_at_t(bez,t) :

return csp_at_t([bez[0],bez[0],bez[1]],[bez[2],bez[3],bez[3]],t)

def bez_to_point_distance(bez,p,needed_dist=[0.,1e100]):

# returns [d^2,t]

return csp_seg_to_point_distance(bez_to_csp_segment(bez),p,needed_dist)

def bez_normalized_slope(bez,t):

return csp_normalized_slope([bez[0],bez[0],bez[1]], [bez[2],bez[3],bez[3]],t)

def normalize((x,y)) :

l = math.sqrt(x**2+y**2)

if l == 0 : return [0.,0.]

else : return [x/l, y/l]

def cross(a,b) :

return a[1] * b[0] - a[0] * b[1]

def dot(a,b) :

return a[0] * b[0] + a[1] * b[1]

def rotate_ccw(d) :

return [-d[1],d[0]]

def rotate_cw(d) :

return [d[1],-d[0]]

def vectors_ccw(a,b):

return a[0]*b[1]-b[0]*a[1] < 0

def vector_add(a,b) :

return [a[0]+b[0],a[1]+b[1]]

def vector_mul(a,b) :

return [a[0]*b,a[1]*b]

def vector_from_to_length(a,b):

return math.sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]))

def matrix_mul(a,b) :

return [ [ sum([a[i][k]*b[k][j] for k in range(len(a[0])) ]) for j in range(len(b[0]))] for i in range(len(a))]

try :

return [ [ sum([a[i][k]*b[k][j] for k in range(len(a[0])) ]) for j in range(len(b[0]))] for i in range(len(a))]

except :

return None

def transpose(a) :

try :

return [ [ a[i][j] for i in range(len(a)) ] for j in range(len(a[0])) ]

except :

return None

def det_3x3(a):

return float(

a[0][0]*a[1][1]*a[2][2] + a[0][1]*a[1][2]*a[2][0] + a[1][0]*a[2][1]*a[0][2]

- a[0][2]*a[1][1]*a[2][0] - a[0][0]*a[2][1]*a[1][2] - a[0][1]*a[2][2]*a[1][0]

)

def inv_3x3(a): # invert matrix 3x3

det = det_3x3(a)

if det==0: return None

return [

[ (a[1][1]*a[2][2] - a[2][1]*a[1][2])/det, -(a[0][1]*a[2][2] - a[2][1]*a[0][2])/det, (a[0][1]*a[1][2] - a[1][1]*a[0][2])/det ],

[ -(a[1][0]*a[2][2] - a[2][0]*a[1][2])/det, (a[0][0]*a[2][2] - a[2][0]*a[0][2])/det, -(a[0][0]*a[1][2] - a[1][0]*a[0][2])/det ],

[ (a[1][0]*a[2][1] - a[2][0]*a[1][1])/det, -(a[0][0]*a[2][1] - a[2][0]*a[0][1])/det, (a[0][0]*a[1][1] - a[1][0]*a[0][1])/det ]

]

def inv_2x2(a): # invert matrix 2x2

det = a[0][0]*a[1][1] - a[1][0]*a[0][1]

if det==0: return None

return [

[a[1][1]/det, -a[0][1]/det],

[-a[1][0]/det, a[0][0]/det]

]

def small(a) :

global small_tolerance

return abs(a)<small_tolerance

def atan2(*arg):

if len(arg)==1 and ( type(arg[0]) == type([0.,0.]) or type(arg[0])==type((0.,0.)) ) :

return (math.pi/2 - math.atan2(arg[0][0], arg[0][1]) ) % math.pi2

elif len(arg)==2 :

return (math.pi/2 - math.atan2(arg[0],arg[1]) ) % math.pi2

else :

raise ValueError, "Bad argumets for atan! (%s)" % arg

def get_text(node) :

value = None

if node.text!=None : value = value +"\n" + node.text if value != None else node.text

for k in node :

if k.tag == inkex.addNS('tspan','svg'):

if k.text!=None : value = value +"\n" + k.text if value != None else k.text

return value

def draw_text(text,x,y, group = None, style = None, font_size = 10, gcodetools_tag = None) :

if style == None :

style = "font-family:DejaVu Sans;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:DejaVu Sans;fill:#000000;fill-opacity:1;stroke:none;"

style += "font-size:%fpx;"%font_size

attributes = { 'x': str(x),

inkex.addNS("space","xml"):"preserve",

'y': str(y),

'style' : style

}

if gcodetools_tag!=None :

attributes["gcodetools"] = str(gcodetools_tag)

if group == None:

group = options.doc_root

t = inkex.etree.SubElement( group, inkex.addNS('text','svg'), attributes)