Add tool path optimization example

Add example demonstrating use of tsp-solver with pcb-tools to optimize
tool paths in an excellon file. This is based on @koppi's script in #30

5 files changed, 469 insertions, 10 deletions

diff --git a/examples/excellon_optimize.py b/examples/excellon_optimize.py
new file mode 100644
index 0000000..5f0adbc
--- /dev/null
+++ b/examples/excellon_optimize.py
@@ -0,0 +1,90 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+# Example using pcb-tools with tsp-solver (github.com/dmishin/tsp-solver) to
+# optimize tool paths in an Excellon file.
+#
+#
+# Copyright 2015 Hamilton Kibbe <ham@hamiltonkib.be>
+# Based on a script by https://github.com/koppi
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations under
+# the License.
+
+import sys
+import math
+import gerber
+from operator import sub
+from gerber.excellon import DrillHit
+
+try:
+    from tsp_solver.greedy import solve_tsp
+except ImportError:
+    print('\n=================================================================\n'
+          'This example requires tsp-solver be installed in order to run.\n\n'
+          'tsp-solver can be downloaded from:\n'
+          '    http://github.com/dmishin/tsp-solver.\n'
+          '=================================================================')
+    sys.exit(0)
+
+
+if __name__ == '__main__':
+
+    # Get file name to open
+    if len(sys.argv) < 2:
+        fname = 'gerbers/shld.drd'
+    else:
+        fname = sys.argv[1]
+
+    # Read the excellon file
+    f = gerber.read(fname)
+
+    positions   = {}
+    tools   = {}
+    hit_counts = f.hit_count()
+    oldpath = sum(f.path_length().values())
+
+    #Get hit positions
+    for hit in f.hits:
+        tool_num = hit.tool.number
+        if tool_num not in positions.keys():
+            positions[tool_num]   = []
+        positions[tool_num].append(hit.position)
+
+    hits = []
+
+    # Optimize tool path for each tool
+    for tool, count in iter(hit_counts.items()):
+
+        # Calculate distance matrix
+        distance_matrix = [[math.hypot(*tuple(map(sub, 
+                                                  positions[tool][i], 
+                                                  positions[tool][j]))) 
+                            for j in iter(range(count))] 
+                            for i in iter(range(count))]
+
+        # Calculate new path
+        path = solve_tsp(distance_matrix, 50)
+
+        # Create new hits list
+        hits += [DrillHit(f.tools[tool], positions[tool][p]) for p in path]
+
+    # Update the file
+    f.hits = hits
+    f.filename = f.filename + '.optimized'
+    f.write()
+    
+    # Print drill report
+    print(f.report())
+    print('Original path length:  %1.4f' % oldpath)
+    print('Optimized path length: %1.4f' % sum(f.path_length().values()))
+
diff --git a/examples/excellon_optimize_after.PNG b/examples/excellon_optimize_after.PNG
new file mode 100644
index 0000000..0f16387
--- /dev/null
+++ b/examples/excellon_optimize_after.PNG
diff --git a/examples/excellon_optimize_before.PNG b/examples/excellon_optimize_before.PNG
new file mode 100644
index 0000000..26a36ab
--- /dev/null
+++ b/examples/excellon_optimize_before.PNG
diff --git a/examples/gerbers/shld.drd b/examples/gerbers/shld.drd
new file mode 100644
index 0000000..a919b5b
--- /dev/null
+++ b/examples/gerbers/shld.drd
@@ -0,0 +1,354 @@
+%
+M48
+M72
+T01C0.03200
+T02C0.03543
+T03C0.04000
+%
+T01
+X11212Y16343
+X80212Y16343
+X21212Y16343
+X99212Y22143
+X99212Y12143
+X40212Y16343
+T02
+X10812Y191043
+X70812Y111043
+X130812Y111043
+X80812Y141043
+X110812Y71043
+X160812Y51043
+X20812Y171043
+X30812Y91043
+X50812Y111043
+X50812Y121043
+X20812Y161043
+X90812Y111043
+X70812Y61043
+X40812Y171043
+X50812Y81043
+X160812Y61043
+X40812Y191043
+X30812Y31043
+X90812Y131043
+X10812Y31043
+X150812Y111043
+X170812Y51043
+X110812Y151043
+X10812Y51043
+X150812Y51043
+X140812Y121043
+X170812Y61043
+X30812Y61043
+X70812Y91043
+X70812Y101043
+X160812Y161043
+X40812Y81043
+X220812Y151043
+X180812Y71043
+X30812Y151043
+X50812Y161043
+X150812Y131043
+X40812Y61043
+X130812Y91043
+X90812Y61043
+X80812Y101043
+X30812Y191043
+X130812Y151043
+X60812Y31043
+X50812Y91043
+X40812Y111043
+X220812Y141043
+X30812Y81043
+X140812Y81043
+X60812Y61043
+X210812Y131043
+X160812Y71043
+X90812Y41043
+X120812Y151043
+X10812Y161043
+X80812Y151043
+X50812Y71043
+X160812Y151043
+X110812Y111043
+X30812Y121043
+X10812Y41043
+X20812Y41043
+X40812Y51043
+X10812Y151043
+X200812Y101043
+X70812Y41043
+X120812Y51043
+X40812Y41043
+X80812Y91043
+X170812Y161043
+X100812Y71043
+X40812Y31043
+X30812Y141043
+X180812Y131043
+X10812Y61043
+X120812Y141043
+X200812Y151043
+X90812Y121043
+X50812Y31043
+X170812Y121043
+X170812Y111043
+X60812Y121043
+X40812Y101043
+X120812Y121043
+X100812Y161043
+X10812Y81043
+X130812Y131043
+X60812Y81043
+X200812Y111043
+X140812Y51043
+X150812Y71043
+X160812Y111043
+X120812Y111043
+X130812Y101043
+X20812Y51043
+X20812Y201043
+X90812Y71043
+X190812Y61043
+X170812Y81043
+X70812Y71043
+X50812Y101043
+X150812Y81043
+X60812Y131043
+X190812Y121043
+X170812Y131043
+X130812Y121043
+X20812Y91043
+X70812Y151043
+X70812Y141043
+X180812Y111043
+X10812Y181043
+X40812Y131043
+X80812Y121043
+X120812Y61043
+X160812Y101043
+X90812Y31043
+X10812Y91043
+X80812Y71043
+X100812Y121043
+X100812Y51043
+X160812Y121043
+X40812Y71043
+X50812Y51043
+X180812Y81043
+X90812Y51043
+X60812Y71043
+X40812Y161043
+X190812Y141043
+X20812Y31043
+X100812Y151043
+X200812Y141043
+X180812Y151043
+X60812Y51043
+X120812Y131043
+X150812Y141043
+X180812Y51043
+X150812Y101043
+X170812Y101043
+X150812Y151043
+X30812Y111043
+X90812Y151043
+X80812Y131043
+X170812Y151043
+X80812Y51043
+X10812Y201043
+X60812Y151043
+X140812Y111043
+X100812Y91043
+X90812Y161043
+X130812Y81043
+X190812Y111043
+X140812Y101043
+X20812Y71043
+X150812Y121043
+X90812Y141043
+X60812Y111043
+X110812Y121043
+X30812Y71043
+X30812Y51043
+X210812Y141043
+X50812Y61043
+X140812Y131043
+X30812Y201043
+X190812Y101043
+X70812Y81043
+X20812Y121043
+X20812Y191043
+X80812Y161043
+X80812Y81043
+X20812Y151043
+X40812Y121043
+X80812Y31043
+X80812Y111043
+X190812Y151043
+X30812Y181043
+X60812Y91043
+X110812Y61043
+X180812Y61043
+X10812Y141043
+X50812Y131043
+X130812Y51043
+X50812Y151043
+X110812Y51043
+X70812Y131043
+X60812Y41043
+X200812Y161043
+X80812Y61043
+X140812Y161043
+X190812Y81043
+X20812Y141043
+X70812Y161043
+X140812Y151043
+X20812Y61043
+X20812Y81043
+X100812Y131043
+X200812Y131043
+X140812Y141043
+X40812Y151043
+X40812Y91043
+X60812Y101043
+X160812Y81043
+X130812Y71043
+X30812Y41043
+X10812Y71043
+X180812Y141043
+X170812Y141043
+X180812Y91043
+X180812Y101043
+X150812Y61043
+X120812Y161043
+X90812Y101043
+X200812Y121043
+X190812Y91043
+X160812Y141043
+X130812Y161043
+X20812Y101043
+X90812Y81043
+X190812Y161043
+X30812Y171043
+X40812Y181043
+X70812Y51043
+X110812Y101043
+X60812Y141043
+X120812Y101043
+X30812Y161043
+X100812Y141043
+X220812Y131043
+X50812Y141043
+X30812Y101043
+X60812Y161043
+X150812Y161043
+X20812Y131043
+X150812Y91043
+X100812Y61043
+X10812Y131043
+X30812Y131043
+X100812Y41043
+X140812Y61043
+X210812Y151043
+X70812Y121043
+X100812Y101043
+X180812Y121043
+X40812Y201043
+X190812Y71043
+X10812Y171043
+X110812Y141043
+X130812Y61043
+X110812Y81043
+X80812Y41043
+X50812Y41043
+X110812Y131043
+X190812Y131043
+X130812Y141043
+X140812Y91043
+X20812Y111043
+X140812Y71043
+X170812Y91043
+X120812Y91043
+X190812Y51043
+X120812Y81043
+X160812Y91043
+X100812Y81043
+X120812Y71043
+X10812Y121043
+X170812Y71043
+X110812Y91043
+X100812Y111043
+X110812Y161043
+X70812Y31043
+X90812Y91043
+X40812Y141043
+X20812Y181043
+X210812Y161043
+X180812Y161043
+X160812Y131043
+T03
+X86712Y189043
+X213012Y23043
+X126732Y201114
+X96712Y189043
+X86732Y201114
+X56732Y201114
+X142812Y23443
+X106712Y189043
+X112754Y11450
+X182720Y200950
+X106732Y201114
+X207259Y55639
+X207259Y81239
+X203131Y11150
+X76732Y201114
+X192720Y200950
+X66712Y189043
+X96732Y201114
+X193131Y11150
+X66732Y201114
+X203012Y23043
+X122754Y11450
+X76712Y189043
+X173131Y11150
+X192712Y188843
+X116712Y189043
+X116732Y201114
+X213131Y11150
+X162720Y200950
+X225059Y55639
+X183131Y11150
+X126712Y189043
+X183012Y23043
+X212712Y188843
+X163131Y11150
+X213563Y110846
+X122812Y23443
+X132812Y23443
+X182712Y188843
+X212720Y200950
+X202720Y200950
+X193012Y23043
+X213563Y120846
+X172720Y200950
+X225059Y81239
+X223563Y120846
+X56712Y189043
+X172712Y188843
+X213563Y100846
+X142720Y200950
+X163012Y23043
+X142754Y11450
+X223563Y110846
+X132754Y11450
+X142712Y188843
+X162712Y188843
+X152712Y188843
+X223563Y100846
+X202712Y188843
+X112812Y23443
+X173012Y23043
+X152720Y200950
+M30
diff --git a/gerber/excellon.py b/gerber/excellon.py
index 65d014f..d89b349 100755
--- a/gerber/excellon.py
+++ b/gerber/excellon.py
@@ -136,17 +136,18 @@ class ExcellonFile(CamFile):
         rprt += '  Code      Size     Hits    Path Length\n'

         rprt += '  --------------------------------------\n'

         for tool in iter(self.tools.values()):

-            rprt += toolfmt.format(tool.number, tool.diameter, tool.hit_count, self.tool_path_length(tool.number))

+            rprt += toolfmt.format(tool.number, tool.diameter, tool.hit_count, self.path_length(tool.number))

         if filename is not None:

             with open(filename, 'w') as f:

                 f.write(rprt)

         return rprt

 

-    def write(self, filename):

+    def write(self, filename=None):

+        filename = filename if filename is not None else self.filename

         with open(filename, 'w') as f:

+            

             # Copy the header verbatim

             for statement in self.statements:

-                print(statement)

                 if not isinstance(statement, ToolSelectionStmt):

                     f.write(statement.to_excellon(self.settings) + '\n')

                 else:

@@ -198,18 +199,32 @@ class ExcellonFile(CamFile):
         for hit in self. hits:

             hit.position = tuple(map(operator.add, hit.position, (x_offset, y_offset)))

 

-    def tool_path_length(self, tool_number):

+    def path_length(self, tool_number=None):

         """ Return the path length for a given tool

         """

-        length = 0.0

-        pos = (0, 0)

+        lengths = {}

+        positions = {}

         for hit in self.hits:

             tool = hit.tool

-            if tool.number == tool_number:

-                length = length + math.hypot(*tuple(map(operator.sub, pos, hit.position)))

-                pos = hit.position

-        return length

+            num = tool.number

+            positions[num] = (0, 0) if positions.get(num) is None else positions[num]

+            lengths[num] = 0.0 if lengths.get(num) is None else lengths[num]

+            lengths[num] = lengths[num] + math.hypot(*tuple(map(operator.sub, positions[num], hit.position)))

+            positions[num] = hit.position

+        

+        if tool_number is None:

+            return lengths

+        else:

+            return lengths.get(tool_number)

 

+    def hit_count(self, tool_number=None):

+            counts = {}

+            for tool in iter(self.tools.values()):

+                counts[tool.number] = tool.hit_count

+            if tool_number is None:

+                return counts

+            else:

+                return counts.get(tool_number)

 

     def update_tool(self, tool_number, **kwargs):

         """ Change parameters of a tool