Chiming in because this is something I've tried (and failed) a couple of weeks ago
I had tried to make a similar optimization macro, my goal was to tweak multiple parameters so that some 2D shapes fill a rectangle without overlapping, optimizing e.g. for the scale of the shapes.
I used an App::FeaturePython object, which describes some tweakable parameters with their ranges, the first parameter is the goal (to minimize or maximize), and the Mapping field tells it how to assign tweakable parameters to the position, rotation, scale of the objects. This allows to bind the same scale to two objects. In retrospect, I should have used simple properties, and used expressions in the objects-to-be-moved to copy these properties.
My approach was to use a genetic algorithm. This was probably not the best idea, as combining the rotation of one solution with the position of another is unlikely to give a valid result, when the rectangle is getting cramped.
Another problem is that I didn't implement a good fitness function for the tweakable parameters, so the algorithm is just groping in the dark really.
So the code below requires a valid starting position otherwise it takes forever to find one, and even with that it converges at a horrendously slow speed. Please file this in the "failed experiments" folder
I'll probably revive this in the future and use some insights from this thread (use Scipy, make sure the fitness function has a smooth gradient close to the optimum), and give the algorithm a hand:
* instead of fitting in a fixed rectangle, it makes sense rotate the group of shapes as a whole a few times until its bounding box is the smallest, and use that as a metric
* instead of maximizing the scale (which adds an extra parameter) I should minimize the delta between the best bounding box's aspect ratio and the target aspect ratio; it's easy to scale to get the desired size once the aspect ratio is optimal
* minimize the number of parameters: since the bounding box should be measured, the absolute position doesn't matter, only the relative positions of the objects, so one object can be fixed in (0,0), the same applies to the rotation.
* rotate objects around their centre of mass instead of rotating around an arbitrary object origin
* try to find a way to "fix" an invalid solution instead of discarding it (e.g. if the shapes intersect, shift one until they don't anymore)
Surely these problem-specific tricks can be generalized to have decent guidelines for an optimization problem, I'll have to think about this.
Code: Select all
# TODO:
# fitness: distance to other shapes
# compute rotated bounding box witù minimum area and rotate the page to fit (+portrait or landscape)
from functools import cmp_to_key
import random
def applyConfiguration(configuration, mapping, objects):
for i,o in enumerate(objects):
x,y,angle,scale = mapping[i]
o.Placement.Base.x = configuration[x][1]
o.Placement.Base.y = configuration[y][1]
o.Placement.Rotation.Angle = configuration[angle][1]
o.Scale = configuration[scale][1]
def isValid(page, configuration, mapping, objects):
applyConfiguration(configuration, mapping, objects)
for object in objects:
if object.Shape.cut(page.Shape).Area > 0:
return False
for other in objects:
if object != other and object.Shape.common(other.Shape).Area > 0:
return False
return True
def compare(configuration1, configuration2, tolerance):
if configuration2 is None:
return True
if configuration1 is None:
return False
"""True if configuration1 is better than configuration2. This is not a proper rder because of the tolerance"""
for ((name, vx, min, max, goal),(_, vy, _, _, _)) in zip(configuration1,configuration2):
if goal == 'max':
v1, v2 = vx, vy
elif goal == 'min':
v1, v2 = vy,vx
elif goal == '':
break # uncomparable
else:
raise ValueError("Optimize2D: Invalid goal:" + str(goal) + " in configuration " + str(configuration1) + ". Expected 'min' or 'max'.")
if v1 > v2 + tolerance:
return 1
elif v1 < v2 - tolerance:
return -1
else:
continue
return 0
def evolve(configuration, best, population, generation, tolerance):
configuration = list(configuration) # copy to prevent mutation
r = random.random()
if r < 0.05:
# completely random starting point
for i in range(len(configuration)):
name, v, min, max, goal = configuration[i]
v = random.uniform(min, max)
configuration[i] = (name, v, min, max, goal)
elif r < 0.3:
# completely randomize a gene trying to improve the best case
for attempt in range(50):
i = random.randrange(len(configuration))
name, v, min, max, goal = configuration[i]
v = random.uniform(min, max)
configuration[i] = (name, v, min, max, goal)
if compare(configuration, best, tolerance)> 0:
break
elif r < 0.5:
# slightly randomize all genes
for i in range(len(configuration)):
name, v, min, max, goal = configuration[i]
delta = (max-min)*(1.0/(generation+1))
v = v + random.uniform(-delta,delta)
if v < min: v = min
if v > max: v = max
configuration[i] = (name, v, min, max, goal)
elif r < 0.7:
# mix with other from population
other = random.randrange(len(population))
for i in range(len(configuration)):
name, v1, min, max, goal = configuration[i]
_, v2, _, _, _= population[other][i]
if random.random() < 0.5:
v = v1
else:
v = v2
configuration[i] = (name, v, min, max, goal)
else:
# slightly randomize a gene
i = random.randrange(len(configuration))
name, v, min, max, goal = configuration[i]
delta = (max-min)*(1.0/(generation+1))
v = v + random.uniform(-delta,delta)
if v < min: v = min
if v > max: v = max
configuration[i] = (name, v, min, max, goal)
return configuration
def auto(page, initialConfiguration, min, max, mapping, objects, tolerance, maxPopulation, promote, generations):
#random.uniform(min, max)
population = [initialConfiguration]
prevbest = initialConfiguration
best = initialConfiguration
for generation in range(generations):
prevbest = best
best = population[0]
print("score=" + str(best[0][1])+', pop=' + str(len(population)), ', better?' + str(compare(best, prevbest, tolerance)) + "prev=" + str(prevbest[0][1]))
offsprings = [evolve(configuration, best, population, generation, tolerance) for configuration in population]
offsprings = [configuration for configuration in offsprings if isValid(page, configuration, mapping, objects)]
random.shuffle(population)
population = population + offsprings + [initialConfiguration]
population = sorted(population, reverse = True, key = cmp_to_key(lambda x,y: compare(x,y,tolerance)))
population = population[:promote] + random.choices(population = population, k = maxPopulation-promote)
return population[0]
def line(name, v, min, max, goal = ''):
return (name, float(v), float(min), float(max), goal)
def main(o):
configuration = [line(*l.strip().split()) for l in o.Configuration if l.strip()]
mapping = [tuple(l.strip().split()) for l in o.Mapping if l.strip()]
page = o.Page
objects = o.Objects
tolerance = o.Tolerance
maxPopulation = o.MaxPopulation
promote = o.Promote
generations = o.Generations
configuration_indices = dict((name, i) for i, (name,_,_,_,_) in enumerate(configuration))
mapping = [tuple(configuration_indices[ref] for ref in m) for m in mapping]
best = auto(page, configuration, min, max, mapping, objects, tolerance, maxPopulation, promote, generations)
if best:
applyConfiguration(best, mapping, objects)
o.Configuration = [' '.join([str(x) for x in c]) for c in best]
else:
applyConfiguration(configuration, mapping, objects)
raise ValueError("Couldn't find a suitable configuration (not a ValueError)")
def mk():
o = App.ActiveDocument.addObject('App::FeaturePython', 'Optimize2D')
o.addProperty("App::PropertyStringList", "Configuration")
o.Configuration = """scale 0.1 0.1 5 max
rot1 0 0 0
x1 120 0 300
y1 60 0 400
rot2 0 0 90
x2 90 0 300
y2 190 0 400""".split('\n')
o.addProperty("App::PropertyStringList", "Mapping")
o.Mapping = """x1 y1 rot1 scale
x2 y2 rot2 scale""".split('\n')
o.addProperty("App::PropertyLinkList", "Objects")
o.Objects = [App.ActiveDocument.Link, App.ActiveDocument.Link001]
o.addProperty("App::PropertyFloat", "Tolerance")
o.Tolerance = 0.00001
o.addProperty("App::PropertyLink", "Page")
o.Page = App.ActiveDocument.Binder
o.addProperty("App::PropertyInteger", "MaxPopulation", "Genetic algorithm")
o.MaxPopulation = 30
o.addProperty("App::PropertyInteger", "Promote", "Genetic algorithm")
o.Promote = 10
o.addProperty("App::PropertyInteger", "Generations", "Genetic algorithm")
o.Generations = 20
if not hasattr(App.ActiveDocument, 'Optimize2D'):
mk()
main(App.ActiveDocument.Optimize2D)
Code: Select all
OS: Ubuntu 20.04.1 LTS (XFCE/xubuntu)
Word size of OS: 64-bit
Word size of FreeCAD: 64-bit
Version: 0.19.23756 (Git) AppImage
Build type: Release
Branch: master
Hash: 9c6e9184930a52b165a0b7274e3a45d1006bfe67
Python version: 3.8.6
Qt version: 5.12.5
Coin version: 4.0.0
OCC version: 7.4.0
Locale: English/United Kingdom (en_GB)