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

4 files changed, 444 insertions, 0 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