#!/usr/bin/env python3
#
# SVG Path Ordering Extension
# This extension uses a simple TSP algorithm to order the paths so as
# to reduce plotting time by plotting nearby paths consecutively.
#
#
# While written from scratch, this is a derivative in spirit of the work by
# Matthew Beckler and Daniel C. Newman for the EggBot project.
#
# The MIT License (MIT)
#
# Copyright (c) 2020 Windell H. Oskay, Evil Mad Science LLC
# www.evilmadscientist.com
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
import math
import sys
from lxml import etree
import inkex
import simpletransform
import simplestyle
import plot_utils
"""
TODOs:
* Apparent difference in execution time for portrait vs landscape document orientation.
Seems to be related to the _change_
* Implement path functions
<_option value=0>Leave as is
<_option value=1>Reorder subpaths
<_option value=2>Break apart
self.OptionParser.add_option( "--path_handling",\
action="store", type="int", dest="path_handling",\
default=1,help="How compound paths are handled")
* Consider re-introducing GUI method for rendering:
false
"""
class OptimizeSequenceTravelDistance(inkex.EffectExtension):
"""
Inkscape effect extension.
Re-order the objects in the SVG document for faster plotting.
Respect layers: Initialize a new dictionary of objects for each layer, and sort
objects within that layer only
Objects in root of document are treated as being on a _single_ layer, and will all
be sorted.
"""
def add_arguments(self, pars):
pars.add_argument( "--reordering",type=int, default=1, help="How groups are handled")
pars.add_argument( "--preview_rendering",type=inkex.Boolean, default=False, help="Preview rendering") # Rendering is available for debug purposes. It only previews pen-up movements that are reordered and typically does not include all possible movement.
self.auto_rotate = True
def effect(self):
# Main entry point of the program
self.svg_width = 0
self.svg_height = 0
self.air_total_default = 0
self.air_total_sorted = 0
self.printPortrait = False
self.layer_index = 0 # index for coloring layers
self.svg = self.document.getroot()
self.DocUnits = "in" # Default
self.DocUnits = self.svg.unit
self.unit_scaling = 1
self.getDocProps()
"""
Set up the document-wide transforms to handle SVG viewbox
"""
matCurrent = [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0]]
viewbox = self.svg.get( 'viewBox' )
vb = self.svg.get('viewBox')
if vb:
p_a_r = self.svg.get('preserveAspectRatio')
sx,sy,ox,oy = plot_utils.vb_scale(vb, p_a_r, self.svg_width, self.svg_height)
else:
sx = 1.0 / float(plot_utils.PX_PER_INCH) # Handle case of no viewbox
sy = sx
ox = 0.0
oy = 0.0
# Initial transform of document is based on viewbox, if present:
matCurrent = simpletransform.parseTransform('scale({0:.6E},{1:.6E}) translate({2:.6E},{3:.6E})'.format(sx, sy, ox, oy))
# Set up x_last, y_last, which keep track of last known pen position
# The initial position is given by the expected initial pen position
self.y_last = 0
if (self.printPortrait):
self.x_last = self.svg_width
else:
self.x_last = 0
parent_vis='visible'
self.root_nodes = []
if self.options.preview_rendering == True:
# Remove old preview layers, if rendering is enabled
for node in self.svg:
if node.tag == inkex.addNS( 'g', 'svg' ) or node.tag == 'g':
if ( node.get( inkex.addNS( 'groupmode', 'inkscape' ) ) == 'layer' ):
LayerName = node.get( inkex.addNS( 'label', 'inkscape' ) )
if LayerName == '% Preview':
self.svg.remove( node )
preview_transform = simpletransform.parseTransform(
'translate({2:.6E},{3:.6E}) scale({0:.6E},{1:.6E})'.format(
1.0/sx, 1.0/sy, -ox, -oy))
path_attrs = { 'transform': simpletransform.formatTransform(preview_transform)}
self.preview_layer = etree.Element(inkex.addNS('g', 'svg'),
path_attrs, nsmap=inkex.NSS)
self.preview_layer.set( inkex.addNS('groupmode', 'inkscape' ), 'layer' )
self.preview_layer.set( inkex.addNS( 'label', 'inkscape' ), '% Preview' )
self.svg.append( self.preview_layer )
# Preview stroke width: 1/1000 of page width or height, whichever is smaller
if self.svg_width < self.svg_height:
width_du = self.svg_width / 1000.0
else:
width_du = self.svg_height / 1000.0
"""
Stroke-width is a css style element, and cannot accept scientific notation.
Thus, in cases with large scaling (i.e., high values of 1/sx, 1/sy)
resulting from the viewbox attribute of the SVG document, it may be necessary to use
a _very small_ stroke width, so that the stroke width displayed on the screen
has a reasonable width after being displayed greatly magnified thanks to the viewbox.
Use log10(the number) to determine the scale, and thus the precision needed.
"""
log_ten = math.log10(width_du)
if log_ten > 0: # For width_du > 1
width_string = "{0:.3f}".format(width_du)
else:
prec = int(math.ceil(-log_ten) + 3)
width_string = "{0:.{1}f}".format(width_du, prec)
self.p_style = {'stroke-width': width_string, 'fill': 'none',
'stroke-linejoin': 'round', 'stroke-linecap': 'round'}
self.svg = self.parse_svg(self.svg, matCurrent)
def parse_svg(self, input_node, mat_current=None, parent_vis='visible'):
"""
Input: An SVG node (usually) containing other nodes:
The SVG root, a layer, sublayer, or other group.
Output: The re-ordered node. The contents are reordered with the greedy
algorithm, except:
- Layers and sublayers are preserved. The contents of each are
re-ordered for faster plotting.
- Groups are either preserved, broken apart, or re-ordered within
the group, depending on the value of group_mode.
"""
coord_dict = {}
# coord_dict maps a node ID to the following data:
# Is the node plottable, first coordinate pair, last coordinate pair.
# i.e., Node_id -> (Boolean: plottable, Xi, Yi, Xf, Yf)
group_dict = {}
# group_dict maps a node ID for a group to the contents of that group.
# The contents may be a preserved nested group or a flat list, depending
# on the selected group handling mode. Example:
# group_dict = {'id_1': ,
# 'id_2':
nodes_to_delete = []
counter = 0 # TODO: Replace this with better unique ID system
# Account for input_node's transform and any transforms above it:
if mat_current is None:
mat_current = [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0]]
try:
matNew = simpletransform.composeTransform( mat_current,
simpletransform.parseTransform( input_node.get( "transform" )))
except AttributeError:
matNew = mat_current
for node in input_node:
# Step through each object within the top-level input node
if node.tag is etree.Comment:
continue
try:
id = node.get( 'id' )
except AttributeError:
id = self.svg.get_unique_id("1",True)
node.set( 'id', id)
if id == None:
id = self.svg.get_unique_id("1",True)
node.set( 'id', id)
# First check for object visibility:
skip_object = False
# Check for "display:none" in the node's style attribute:
style = dict(inkex.Style.parse_str(node.get('style')))
if 'display' in style.keys() and style['display'] == 'none':
skip_object = True # Plot neither this object nor its children
# The node may have a display="none" attribute as well:
if node.get( 'display' ) == 'none':
skip_object = True # Plot neither this object nor its children
# Visibility attributes control whether a given object will plot.
# Children of hidden (not visible) parents may be plotted if
# they assert visibility.
visibility = node.get( 'visibility', parent_vis )
if 'visibility' in style.keys():
visibility = style['visibility'] # Style may override attribute.
if visibility == 'inherit':
visibility = parent_vis
if visibility != 'visible':
skip_object = True # Skip this object and its children
# Next, check to see if this inner node is itself a group or layer:
if node.tag == inkex.addNS( 'g', 'svg' ) or node.tag == 'g':
# Use the user-given option to decide what to do with subgroups:
subgroup_mode = self.options.reordering
# Values of the parameter:
# subgroup_mode=="1": Preserve groups
# subgroup_mode=="2": Reorder within groups
# subgroup_mode=="3": Break apart groups
if node.get(inkex.addNS('groupmode', 'inkscape')) == 'layer':
# The node is a layer or sub-layer, not a regular group.
# Parse it separately, and re-order its contents.
subgroup_mode = 2 # Always sort within each layer.
self.layer_index += 1
layer_name = node.get( inkex.addNS( 'label', 'inkscape' ) )
if sys.version_info < (3,): # Yes this is ugly. More elegant suggestions welcome. :)
layer_name = layer_name.encode( 'ascii', 'ignore' ) #Drop non-ascii characters
else:
layer_name = str(layer_name)
layer_name.lstrip # Remove leading whitespace
if layer_name:
if layer_name[0] == '%': # First character is '%'; This
skip_object = True # is a documentation layer; skip plotting.
self.layer_index -= 1 # Set this back to previous value.
if skip_object:
# Do not re-order hidden groups or layers.
subgroup_mode = 1 # Preserve this group
if subgroup_mode == 3:
# Break apart this non-layer subgroup and add it to
# the set of things to be re-ordered.
nodes_to_delete.append(node)
nodes_inside_group = self.group2NodeDict(node)
for a_node in nodes_inside_group:
try:
id = a_node.get( 'id' )
except AttributeError:
id = self.uniqueId("1",True)
a_node.set( 'id', id)
if id == None:
id = self.uniqueId("1",True)
a_node.set( 'id', id)
# Use getFirstPoint and getLastPoint on each object:
start_plottable, first_point = self.getFirstPoint(a_node, matNew)
end_plottable, last_point = self.getLastPoint(a_node, matNew)
coord_dict[id] = (start_plottable and end_plottable,
first_point[0], first_point[1], last_point[0], last_point[1] )
# Entry in group_dict is this node
group_dict[id] = a_node
elif subgroup_mode == 2:
# Reorder a layer or subgroup with a recursive call.
node = self.parse_svg(node, matNew, visibility)
# Capture the first and last x,y coordinates of the optimized node
start_plottable, first_point = self.group_first_pt(node, matNew)
end_plottable, last_point = self.group_last_pt(node, matNew)
# Then add this optimized node to the coord_dict
coord_dict[id] = (start_plottable and end_plottable,
first_point[0], first_point[1], last_point[0], last_point[1] )
# Entry in group_dict is this node
group_dict[id] = node
else: # (subgroup_mode == 1)
# Preserve the group, but find its first and last point so
# that it can be re-ordered with respect to other items
if skip_object:
start_plottable = False
end_plottable = False
first_point = [(-1.), (-1.)]
last_point = [(-1.), (-1.)]
else:
start_plottable, first_point = self.group_first_pt(node, matNew)
end_plottable, last_point = self.group_last_pt(node, matNew)
coord_dict[id] = (start_plottable and end_plottable,
first_point[0], first_point[1], last_point[0], last_point[1] )
# Entry in group_dict is this node
group_dict[id] = node
else: # Handle objects that are not groups
if skip_object:
start_plottable = False
end_plottable = False
first_point = [(-1.), (-1.)]
last_point = [(-1.), (-1.)]
else:
start_plottable, first_point = self.getFirstPoint(node, matNew)
end_plottable, last_point = self.getLastPoint(node, matNew)
coord_dict[id] = (start_plottable and end_plottable,
first_point[0], first_point[1], last_point[0], last_point[1] )
group_dict[id] = node # Entry in group_dict is this node
# Perform the re-ordering:
ordered_element_list = self.ReorderNodeList(coord_dict, group_dict)
# Once a better order for the svg elements has been determined,
# All there is do to is to reintroduce the nodes to the parent in the correct order
for elt in ordered_element_list:
# Creates identical node at the correct location according to ordered_element_list
input_node.append(elt)
# Once program is finished parsing through
for element_to_remove in nodes_to_delete:
try:
input_node.remove(element_to_remove)
except ValueError:
inkex.errormsg(str(element_to_remove.get('id'))+" is not a member of " + str(input_node.get('id')))
return input_node
def break_apart_path(self, path):
"""
An SVG path may contain multiple distinct portions, that are normally separated
by pen-up movements.
This function takes the path data string from an SVG path, parses it, and returns
a dictionary of independent path data strings, each of which represents a single
pen-down movement. It is equivalent to the Inkscape function Path > Break Apart
Input: path data string, representing a single SVG path
Output: Dictionary of (separated) path data strings
"""
MaxLength = len(path)
ix = 0
move_to_location = []
path_dictionary = {}
path_list = []
path_number = 1
# Search for M or m location
while ix < MaxLength:
if(path[ix] == 'm' or path[ix] == 'M'):
move_to_location.append(ix)
ix = ix + 1
# Iterate through every M or m location in our list of move to instructions
# Slice the path string according to path beginning and ends as indicated by the
# location of these instructions
for counter, m in enumerate(move_to_location):
if (m == move_to_location[-1]):
# last entry
path_list.append(path[m:MaxLength].rstrip())
else:
path_list.append(path[m:move_to_location[counter + 1]].rstrip())
for counter, current_path in enumerate(path_list):
# Enumerate over every entry in the path looking for relative m commands
if current_path[0] == 'm' and counter > 0:
# If path contains relative m command, the best case is when the last command
# was a Z or z. In this case, all relative operations are performed relative to
# initial x, y coordinates of the previous path
if path_list[counter -1][-1].upper() == 'Z':
current_path_x, current_path_y,index = self.getFirstPoint(current_path, matNew)
prev_path_x, prev_path_y,ignore = self.getFirstPoint(path_list[counter-1])
adapted_x = current_path_x + prev_path_x
adapted_y = current_path_y + prev_path_y
# Now we can replace the path data with an Absolute Move to instruction
# HOWEVER, we need to adapt all the data until we reach a different command in the case of a repeating
path_list[counter] = "m "+str(adapted_x)+","+str(adapted_y) + ' ' +current_path[index:]
# If there is no z or absolute commands, we need to parse the entire path
else:
# scan path for absolute coordinates. If present, begin parsing from their index
# instead of the beginning
prev_path = path_list[counter-1]
prev_path_length = len(prev_path)
jx = 0
x_val, y_val = 0,0
# Check one char at a time
# until we have the moveTo Command
last_command = ''
is_absolute_command = False
repeated_command = False
# name of command
# how many parameters we need to skip
accepted_commands = {
'M':0,
'L':0,
'H':0,
'V':0,
'C':4,
'S':2,
'Q':2,
'T':0,
'A':5
}
# If there is an absolute command which specifies a new initial point
# then we can save time by setting our index directly to its location in the path data
# See if an accepted_command is present in the path data. If it is present further in the
# string than any command found before, then set the pointer to that location
# if a command is not found, find() will return a -1. jx is initialized to 0, so if no matches
# are found, the program will parse from the beginning to the end of the path
for keys in 'MLCSQTA': # TODO: Compare to last_point; see if we can clean up this part
if(prev_path.find(keys) > jx):
jx = prev_path.find(keys)
while jx < prev_path_length:
temp_x_val = ''
temp_y_val = ''
num_of_params_to_skip = 0
# SVG Path commands can be repeated
if (prev_path[jx].isdigit() and last_command):
repeated_command = True
else:
repeated_command = False
if (prev_path[jx].isalpha() and prev_path[jx].upper() in accepted_commands) or repeated_command:
if repeated_command:
#is_relative_command is saved from last iteration of the loop
current_command = last_command
else:
# If the character is accepted, we must parse until reach the x y coordinates
is_absolute_command = prev_path[jx].isupper()
current_command = prev_path[jx].upper()
# Each command has a certain number of parameters we must pass before we reach the
# information we care about. We will parse until we know that we have reached them
# Get to start of next number
# We will know we have reached a number if the current character is a +/- sign
# or current character is a digit
while jx < prev_path_length:
if(prev_path[jx] in '+-' or prev_path[jx].isdigit()):
break
jx = jx + 1
# We need to parse past the unused parameters in our command
# The number of parameters to parse past is dependent on the command and stored
# as the value of accepted_command
# Spaces and commas are used to deliniate paramters
while jx < prev_path_length and num_of_params_to_skip < accepted_commands[current_command]:
if(prev_path[jx].isspace() or prev_path[jx] == ','):
num_of_params_to_skip = num_of_params_to_skip + 1
jx = jx + 1
# Now, we are in front of the x character
if current_command.upper() == 'V':
temp_x_val = 0
if current_command.upper() == 'H':
temp_y_val = 0
# Parse until next character is a digit or +/- character
while jx < prev_path_length and current_command.upper() != 'V':
if(prev_path[jx] in '+-' or prev_path[jx].isdigit()):
break
jx = jx + 1
# Save each next character until we reach a space
while jx < prev_path_length and current_command.upper() != 'V' and not (prev_path[jx].isspace() or prev_path[jx] == ','):
temp_x_val = temp_x_val + prev_path[jx]
jx = jx + 1
# Then we know we have completely parsed the x character
# Now we are in front of the y character
# Parse until next character is a digit or +/- character
while jx < prev_path_length and current_command.upper() != 'H':
if(prev_path[jx] in '+-' or prev_path[jx].isdigit()):
break
jx = jx + 1
## Save each next character until we reach a space
while jx < prev_path_length and current_command.upper() != 'H' and not (prev_path[jx].isspace() or prev_path[jx] == ','):
temp_y_val = temp_y_val + prev_path[jx]
jx = jx + 1
# Then we know we have completely parsed the y character
if is_absolute_command:
if current_command == 'H':
# Absolute commands create new x,y position
try:
x_val = float(temp_x_val)
except ValueError:
pass
elif current_command == 'V':
# Absolute commands create new x,y position
try:
y_val = float(temp_y_val)
except ValueError:
pass
else:
# Absolute commands create new x,y position
try:
x_val = float(temp_x_val)
y_val = float(temp_y_val)
except ValueError:
pass
else:
if current_command == 'h':
# Absolute commands create new x,y position
try:
x_val = x_val + float(temp_x_val)
except ValueError:
pass
elif current_command == 'V':
# Absolute commands create new x,y position
try:
y_val = y_val + float(temp_y_val)
except ValueError:
pass
else:
# Absolute commands create new x,y position
try:
x_val = x_val + float(temp_x_val)
y_val = y_val + float(temp_y_val)
except ValueError:
pass
last_command = current_command
jx = jx + 1
x,y,index = self.getFirstPoint(current_path,None)
path_list[counter] = "m "+str(x_val+x)+","+str(y_val+y) + ' ' + current_path[index:]
for counter, path in enumerate(path_list):
path_dictionary['ad_path'+ str(counter)] = path
return path_dictionary
def getFirstPoint(self, node, matCurrent):
"""
Input: (non-group) node and parent transformation matrix
Output: Boolean value to indicate if the svg element is plottable and
two floats stored in a list representing the x and y coordinates we plot first
"""
# first apply the current matrix transform to this node's transform
matNew = simpletransform.composeTransform( matCurrent, simpletransform.parseTransform( node.get( "transform" ) ) )
point = [float(-1), float(-1)]
try:
if node.tag == inkex.addNS( 'path', 'svg' ):
pathdata = node.get('d')
point = plot_utils.pathdata_first_point(pathdata)
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if node.tag == inkex.addNS( 'rect', 'svg' ) or node.tag == 'rect':
"""
The x,y coordinates for a rect are included in their specific attributes
If there is a transform, we need translate the x & y coordinates to their
correct location via applyTransformToPoint.
"""
point[0] = float( node.get( 'x' ) )
point[1] = float( node.get( 'y' ) )
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if node.tag == inkex.addNS( 'line', 'svg' ) or node.tag == 'line':
"""
The x1 and y1 attributes are where we will start to draw
So, get them, apply the transform matrix, and return the point
"""
point[0] = float( node.get( 'x1' ) )
point[1] = float( node.get( 'y1' ) )
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if node.tag == inkex.addNS( 'polyline', 'svg' ) or node.tag == 'polyline':
pl = node.get( 'points', '' ).strip()
if pl == '':
return False, point
pa = pl.replace(',',' ').split() # replace comma with space before splitting
if not pa:
return False, point
pathLength = len( pa )
if (pathLength < 4): # Minimum of x1,y1 x2,y2 required.
return False, point
d = "M " + pa[0] + " " + pa[1]
i = 2
while (i < (pathLength - 1 )):
d += " L " + pa[i] + " " + pa[i + 1]
i += 2
point = plot_utils.pathdata_first_point(d)
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if (node.tag == inkex.addNS( 'polygon', 'svg' ) or
node.tag == 'polygon'):
"""
We need to extract x1 and y1 from these:
We accomplish this with Python string strip
and split methods. Then apply transforms
"""
# Strip() removes all whitespace from the start and end of p1
pl = node.get( 'points', '' ).strip()
if (pl == ''):
# If pl is blank there has been an error, return False and -1,-1 to indicate a problem has occured
return False, point
# Split string by whitespace
pa = pl.split()
if not len( pa ):
# If pa is blank there has been an error, return False and -1,-1 to indicate a problem has occured
return False, point
# pa[0] = "x1,y1
# split string via comma to get x1 and y1 individually
# then point = [x1,x2]
point = pa[0].split(",")
point = [float(point[0]),float(point[1])]
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if node.tag == inkex.addNS( 'ellipse', 'svg' ) or \
node.tag == 'ellipse':
cx = float( node.get( 'cx', '0' ) )
cy = float( node.get( 'cy', '0' ) )
rx = float( node.get( 'rx', '0' ) )
point[0] = cx - rx
point[1] = cy
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if node.tag == inkex.addNS( 'circle', 'svg' ) or \
node.tag == 'circle':
cx = float( node.get( 'cx', '0' ) )
cy = float( node.get( 'cy', '0' ) )
r = float( node.get( 'r', '0' ) )
point[0] = cx - r
point[1] = cy
simpletransform.applyTransformToPoint(matNew, point)
return True, point
if node.tag == inkex.addNS('symbol', 'svg') or node.tag == 'symbol':
# A symbol is much like a group, except that
# it's an invisible object.
return False, point # Skip this element.
if node.tag == inkex.addNS('use', 'svg') or node.tag == 'use':
"""
A