suche Algorithmus für nesting Problem.

[blauton.com]

Hallo!

gegeben: Eine Fläche A und ein Set von Rechtecken R1..Rn mit gegebenen Kantenlängen, wobei die die Fläche der r's << A.

Problem: Plazieren die r's sodass sie in A passen. Die Rechtecke dürfen sich nicht überschneiden und nicht gedreht werden.

Die optimale Plazierung der r's ist NP-vollst, also gebe ich mich mit einer supoptimalen Lösung zufrieden. Die r's müssen ja auch nur in A reinpassen.

Ich habe mir da eine ganz einfache lokal optimierende greedy Methode vorgestellt: Sortiere die Elemente nach ihrer Größe. Plaziere die ELmente ihrer Größe nach (größte zuerst) möglichst plazsparend.

Hier liegt schon das erste Problem was bedeutet möglichst Plazsparend? Sinnvoll ist es natürlich möglichst große zusammenhängende Flächen zu ermöglichen.

Zeitens: Selbst ein lokales Optimum zu finden ist sehr rechenintensiv: Das Rechteck muss an jede mögliche Stelle gelegt werden und die resultierenden freien Flächen müssen berechnet werden. Bei einer hohen Auflösung der Fläche A gibt es hier ja schon sehr viele Möglichkeiten.

Ein weitere Idee war folgende: Man erhält große freie Flächen wenn man die r's an bestehende Kanten (entweder von A oder von anderen r's) anlegt, vorzugsweise in Ecken. Somit sind die sinnvollen Möglichkeiten deutlich eingeschränkt.

Ich habe allerdings noch keine Idee für eine gute DAtenstruktur mit der ich das alles modellieren könnte. Sollte man freie Kanten oder Flächen oder gar Ecken irgendwo speichern, diese vielleicht noc gewichten? Und wie durchsuche ich nun diese Datenstruktur nach der optimalen Plazierung eines Rechtecks?

[kibble]

Um wie grosse Flächen geht es denn und was ist die einheit, in der sich die Flächen unterscheiden können.
Wenn die Flächen nicht zu gross sind und die Einheiten nicht zu klein könnte man die Fläche doch einfach durch ein 2DArray darstellen 0 gleich frei und eine zahl gehört zu einem rechteck, dann kann man das hinterher auch wieder auseinanderfriemeln.

Um einen guten Platz für die Rechtecke zu finden würde ich auch ecken bevorzugen und dann auch noch, ab es rechts und links und/oder oben und unten passt. Dazu würde sich vielleicht anbieten erst die summe alle kanten vertikal und horizontal zu ermitteln, dann das rechteck zu plazieren wie die summe bilden und dann vergleichen, die Plazierung bei der am wenigsten kanten hinzukommen, oder sogar verschwinden wäre wohl die beste.
vorher wäre bestimmt noch eine gobauswahl der plazierungen sinnvoll, da sonst viel zu viele durchgetestet werden.
aber das überlasse ich dem geneigten leser.

kibble