diff options
| -rw-r--r-- | embroider.py | 240 |
1 files changed, 0 insertions, 240 deletions
diff --git a/embroider.py b/embroider.py index 1becb571..c5b9ccb4 100644 --- a/embroider.py +++ b/embroider.py @@ -197,241 +197,6 @@ class PatchList: def __len__(self): return len(self.patches) - def sort_by_sortorder(self): - def by_sort_order(a,b): - return cmp(a.sortorder, b.sortorder) - self.patches.sort(by_sort_order) - - def partition_by_color(self): - self.sort_by_sortorder() - #dbg.write("Sorted by sortorder:\n"); - #dbg.write(" %s\n" % ("\n".join(map(lambda p: str(p.sortorder), self.patches)))) - out = [] - lastPatch = None - for patch in self.patches: - if (lastPatch!=None and patch.sortorder==lastPatch.sortorder): - out[-1].patches.append(patch) - else: - out.append(PatchList([patch])) - lastPatch = patch - #dbg.write("Emitted %s partitions\n" % len(out)) - return out - - def tsp_by_color(self): - list_of_patchLists = self.partition_by_color() - for patchList in list_of_patchLists: - if len(patchList) > 1: - patchList.traveling_salesman() - return PatchList(reduce(operator.add, - map(lambda pl: pl.patches, list_of_patchLists))) - -# # TODO apparently dead code; replaced by partition_by_color above -# def clump_like_colors_together(self): -# out = PatchList([]) -# lastPatch = None -# for patch in self.patches: -# if (lastPatch!=None and patch.color==lastPatch.color): -# out.patches[-1] = Patch( -# out.patches[-1].color, -# out.patches[-1].sortorder, -# out.patches[-1].stitches+patch.stitches) -# else: -# out.patches.append(patch) -# lastPatch = patch -# return out - - def get(self, i): - if (i<0 or i>=len(self.patches)): - return None - return self.patches[i] - - def cost(self, a, b): - if (a is None or b is None): - rc = 0.0 - else: - rc = (a.stitches[-1] - b.stitches[0]).length() - #dbg.write("cost(%s, %s) = %5.1f\n" % (a, b, rc)) - return rc - - def total_cost(self): - total = 0 - - for i in xrange(1, len(self.patches)): - total += self.cost(self.get(i-1), self.get(i)) - - return total - - def try_swap(self, i, j): - # i,j are indices; - #dbg.write("swap(%d, %d)\n" % (i,j)) - i, j = sorted((i, j)) - neighbors = abs(i - j) == 1 - if neighbors: - oldCost = sum((self.cost(self.get(i-1), self.get(i)), - self.cost(self.get(i), self.get(j)), - self.cost(self.get(j), self.get(j+1)))) - else: - oldCost = sum((self.cost(self.get(i-1), self.get(i)), - self.cost(self.get(i), self.get(i+1)), - self.cost(self.get(j-1), self.get(j)), - self.cost(self.get(j), self.get(j+1)))) - npi = self.get(j) - npj = self.get(i) - rpi = npi.reverse() - rpj = npj.reverse() - options = [ - (npi,npj), - (rpi,npj), - (npi,rpj), - (rpi,rpj), - ] - def costOf(np): - (npi,npj) = np - - if abs(i - j) == 1: - return sum((self.cost(self.get(i-1), npi), - self.cost(npi, npj), - self.cost(npj, self.get(j+1)))) - else: - return sum((self.cost(self.get(i-1), npi), - self.cost(npi, self.get(i+1)), - self.cost(self.get(j-1), npj), - self.cost(npj, self.get(j+1)))) - costs = map(lambda o: (costOf(o), o), options) - costs.sort() - (cost,option) = costs[0] - savings = oldCost - cost - if (savings > 0): - self.patches[i] = option[0] - self.patches[j] = option[1] - success = "!" - else: - success = "." - - #dbg.write("old %5.1f new %5.1f savings: %5.1f\n" % (oldCost, cost, savings)) - return success - - def try_reverse(self, i): - #dbg.write("reverse(%d)\n" % i) - oldCost = (self.cost(self.get(i-1), self.get(i)) - +self.cost(self.get(i), self.get(i+1))) - reversed = self.get(i).reverse() - newCost = (self.cost(self.get(i-1), reversed) - +self.cost(reversed, self.get(i+1))) - savings = oldCost - newCost - if (savings > 0.0): - self.patches[i] = reversed - success = "#" - else: - success = "_" - return success - - def traveling_salesman(self): - #print >> sys.stderr, "TSPing %s patches" % len(self) - - # shockingly, this is non-optimal and pretty much non-efficient. Sorry. - self.pointList = [] - for patch in self.patches: - def visit(idx): - ep = deepcopy(patch.stitches[idx]) - ep.patch = patch - self.pointList.append(ep) - - visit(0) - visit(-1) - - def linear_min(list, func): - min_item = None - min_value = None - for item in list: - value = func(item) - #dbg.write('linear_min %s: value %s => %s (%s)\n' % (func, item, value, value<min_value)) - if (min_value==None or value<min_value): - min_item = item - min_value = value - #dbg.write('linear_min final item %s value %s\n' % (min_item, min_value)) - return min_item - - sortedPatchList = PatchList([]) - def takePatchStartingAtPoint(point): - patch = point.patch - #dbg.write("takePatchStartingAtPoint angling for patch %s--%s\n" % (patch.stitches[0],patch.stitches[-1])) - self.pointList = filter(lambda pt: pt.patch!=patch, self.pointList) - reversed = "" - if (point!=patch.stitches[0]): - reversed = " (reversed)" - #dbg.write('patch.stitches[0] %s point %s match %s\n' % (patch.stitches[0], point, point==patch.stitches[0])) - patch = patch.reverse() - sortedPatchList.patches.append(patch) - #dbg.write('took patch %s--%s %s\n' % (patch.stitches[0], patch.stitches[-1], reversed)) - - # Try a greedy algorithm starting from each point in turn, and pick - # the best result. O(n^2). - - min_cost = None - min_path = [] - - def mate(point): - for p in self.pointList: - if p is not point and p.patch == point.patch: - return p - - start_time = time.time() - - for starting_point in random.sample(self.pointList, len(self.pointList)): - point_list = self.pointList[:] - last_point = mate(starting_point) - - point_list.remove(starting_point) - point_list.remove(last_point) - - path = [starting_point] - cost = 0 - - while point_list: - next_point = min(point_list, key=lambda p: (p - last_point).length()) - cost += (next_point - last_point).length() - - path.append(next_point) - last_point = mate(next_point) - - point_list.remove(next_point) - try: - point_list.remove(last_point) - except: - pass - - if min_cost is None or cost < min_cost: - min_cost = cost - min_path = path - - # timebox this bit to avoid spinning our wheels forever - if time.time() - start_time > 1.0: - break - - for point in min_path: - takePatchStartingAtPoint(point) - - # install the initial result - self.patches = sortedPatchList.patches - - if 1: - # Then hill-climb. - #dbg.write("len(self.patches) = %d\n" % len(self.patches)) - count = 0 - successStr = "" - while (count < 100): - i = random.randint(0, len(self.patches)-1) - j = random.randint(0, len(self.patches)-1) - successStr += self.try_swap(i,j) - - count += 1 - # tidy up at end as best we can - for i in range(len(self.patches)): - successStr += self.try_reverse(i) - - #dbg.write("success: %s\n" % successStr) - class EmbroideryObject: def __init__(self, patchList): self.patchList = patchList @@ -948,11 +713,6 @@ class Embroider(inkex.Effect): inkex.errormsg("Tip: use Path -> Object to Path to convert non-paths before embroidering.") return - dbg.write("starting tsp: %s" % time.time()) - self.patchList = self.patchList.tsp_by_color() - dbg.write("finished tsp: %s" % time.time()) - #dbg.write("patch count: %d\n" % len(self.patchList.patches)) - if self.options.hide_layers: self.hide_layers() |