Ich benötige für mein Programm einen Algorithmus, um Rechtecke (Pakete) in einem größeren Rechteck (Container) anzuordnen. Ich hatte auch einen Algorithmus gefunden, der ganz nett funktioniert hat und den ich deswegen in mein Programm eingebaut habe. Leider ist er jetzt in der Praxis gähnend langsam. Die problematische Stelle habe ich schnell gefunden, und nun suche ich nach einer Lösungsmöglichkeit.
Es gibt eine Container-Klasse, die zum Anordnen der Pakete verwendet wird und zum Prüfen, ob eine Anordnung zulässig ist. Hauptbestandteil ist ein 2dimensionales boolean-Feld, das den Container repräsentiert und für jedes "Pixel" angibt, ob es belegt ist oder nicht. Ein Paket im Container wird dargestellt, in dem die Postionen im boolean-Feld, die dem Paketrand entsprechen, auf true gesetzt werden.
Für den Algorithmus gibt es zwei Funtionen, die ein Paket soweit wie möglich nach links bzw. unten schieben, also solange, bis der Containerrand erreicht ist oder ein anderes Paket im Weg ist. Und diese beiden Funktionen sind der Performance-Killer, denke ich.
Wie könnte ich nun das Verschieben beschleunigen? Eine erste Idee war, nicht jedes Pixel der jeweiligen Kante zu Prüfen, da die Pakete eine gewissen Mindestgröße haben. Aber welche weitern Ansätze gibt es?
Es gibt eine Container-Klasse, die zum Anordnen der Pakete verwendet wird und zum Prüfen, ob eine Anordnung zulässig ist. Hauptbestandteil ist ein 2dimensionales boolean-Feld, das den Container repräsentiert und für jedes "Pixel" angibt, ob es belegt ist oder nicht. Ein Paket im Container wird dargestellt, in dem die Postionen im boolean-Feld, die dem Paketrand entsprechen, auf true gesetzt werden.
Für den Algorithmus gibt es zwei Funtionen, die ein Paket soweit wie möglich nach links bzw. unten schieben, also solange, bis der Containerrand erreicht ist oder ein anderes Paket im Weg ist. Und diese beiden Funktionen sind der Performance-Killer, denke ich.
Code:
class Container
{
private boolean mStack[][];
// ...
public Container(int pStackWidth, int pStackHeight)
{
// ...
mStack = new boolean[pStackWidth][pStackHeight];
for(int i=0; i<pStackWidth; ++i)
for(int j=0; j<pStackHeight; ++j)
mStack[i][j] = false;
// ...
}
// ...
public void moveLeft(Chromosome pChr)
{
if(pChr.getTopY()>=mStackHeight) return;
boolean tMoveLeft = true;
while(tMoveLeft && (pChr.mPosition.x>0)) {
for(int j=pChr.mPosition.y; j<=pChr.getTopY(); ++j)
if(mStack[pChr.mPosition.x-1][j]) { // Schieben nach links nicht mehr möglich ...
tMoveLeft = false; // ... (dort liegt bereits ein anderes Paket)
break;
}
if(tMoveLeft) // Verschiebe um eine Position nach links
pChr.setPosition(pChr.mPosition.x - 1, pChr.mPosition.y);
}
}
public void moveDown(Chromosome pChr)
{
if(pChr.getRightX()>=mStackWidth) return;
boolean tMoveDown = true;
while(tMoveDown && (pChr.mPosition.y>0)) {
for(int i=pChr.mPosition.x; i<=pChr.getRightX(); ++i)
if(mStack[i][pChr.mPosition.y-1]) { // Schieben nach unten nicht mehr möglich
tMoveDown = false;
break;
}
if(tMoveDown) // Verschiebe um eine Position nach unten; Links-Überprüfung aktivieren;
pChr.setPosition(pChr.mPosition.x, pChr.mPosition.y - 1);
}
}
}
Wie könnte ich nun das Verschieben beschleunigen? Eine erste Idee war, nicht jedes Pixel der jeweiligen Kante zu Prüfen, da die Pakete eine gewissen Mindestgröße haben. Aber welche weitern Ansätze gibt es?