Il mio algoritmo che estrae la scatola più grande che può essere fatta da scatole più piccole, è troppo lento

Question

Il mio algoritmo che estrae la scatola più grande che può essere fatta da scatole più piccole, è troppo lento

#1 da (6 voti)
#2 da (5 voti)
#3 da (1 voti)

9

Immagina un mondo basato su cubi (come Minecraft, Trove o Cube World) in cui tutto è costituito da cubi di dimensioni identiche e tutti i cubi sono dello stesso tipo .

L'obiettivo è rappresentare il mondo con il minor numero di caselle rettangolari (unendo cubi ma mantenendo una forma convessa (ovvero una forma rettangolare a forma di parallelepipedo)). Il mio algoritmo ci riesce, ma le sue prestazioni sono troppo lente per lo scopo previsto. Ci sono algoritmi più veloci?

Il codice pseudo-C # per il mio algoritmo è fondamentalmente:

struct Coordinate { int x,y,z; }; //<-- integer based grid
HashSet<Coordinate> world; // <-- contains all the cubes

//width, height, and length represent how many cubes it spans
struct RectangularBox { Coordinate coord; int width,height,length; }

void Begin()
{
    List<RectangularBox> fewestBoxes = new List<RectangularBox>();
    while(world.Count > 0)
    {
         RectangularBox currentLargest = ExtractLargest();
         fewestBoxes.Add(currentLargest);
         world.RemoveRange(currentLargest.ContainedCubes());
    }
    //done; 'fewestBoxes' contains the fewest rectangular boxes needed.
}

private RectangularBox ExtractLargest()
{
    RectangularBox largestBox = new RectangularBox();
    foreach (Coordinate origin in world)
    {
        RectangularBox box = FindMaximumSpan(origin);
        if (box.CalculateVolume() >= largestBox.CalculateVolume())
            largestBox = box;
    }
    return largestBox;
}

private RectangularBox FindMaximumSpan(Coordinate origin)
{
    int maxX, maxY,maxZ;
    while (world.Contains(origin.Offset(maxX, 0, 0))) maxX++;
    while (world.Contains(origin.Offset(0, maxY, 0))) maxY++;
    while (world.Contains(origin.Offset(0, 0, maxZ))) maxZ++;

    RectangularBox largestBox;
    for (int extentX = 0; extentX <= maxX; extentX++)
        for (int extentY = 0; extentY <= maxY; extentY++)
            for (int extentZ = 0; extentZ <= maxZ; extentZ++)
            {
                int lengthX = extentX + 1;
                int lengthY = extentY + 1;
                int lengthZ = extentZ + 1;
                if (BoxIsFilledWithCubes(origin, lengthX, lengthY, lengthZ))
                {
                    int totalVolume = lengthX * lengthY * lengthZ;
                    if (totalVolume >= largestBox.ComputeVolume())
                        largestBox = new RectangularBox(origin, lengthX, lengthY, lengthZ);
                }
                else
                    break;
            }
    return largestBox;
}

private bool BoxIsFilledWithCubes(Coordinate coord, 
    int lengthX, int lengthY, int lengthZ)
{
    for (int gX = 0; gX < lengthX; gX++)
        for (int gY = 0; gY < lengthY; gY++)
            for (int gZ = 0; gZ < lengthZ; gZ++)
                if (!world.Contains(coord.Offset(gX, gY, gZ)))
                    return false;
    return true;
}

Essenzialmente, per ogni blocco nel mondo, trova prima quanti blocchi contendenti ci sono in ciascuna delle tre dimensioni positive (+ X, + Y, + Z). E poi riempie quel volume e controlla che è il riempimento più grande che non manca nessun blocco.

Aggiornamento: Poiché mi sembrava di aver implicito che questo era per il motore di rendering di un gioco, voglio solo chiarire, questo non è per il motore di rendering di un gioco; è per un convertitore di file; nessuna GUI.

algorithms optimization 3d

posta Mr. Smith 21.07.2015 - 11:12

fonte

3 risposte

Leggi altre domande sui tag algorithms optimization 3d

Disporre correttamente gli oggetti al termine del server Cosa c'è di veramente diverso tra SOA e Microservices

score 6 · Answer 1

Puoi usare il fatto che quando

 BoxIsFilledWithCubes(c,x,y,z)

restituisce true, quindi non è necessario controllare BoxIsFilledWithCubes(c,x+1,y,z) tutti quei cubi nell'intervallo di coordinate "(c, x, y, z)" di nuovo. Devi solo controllare quei cubi con la nuova coordinata x c.x + (x+1) . (Lo stesso vale per y+1 o z+1 ). Più in generale, suddividendo una scatola in due scatole più piccole (per le quali potresti già sapere se sono entrambe piene di cubi o non entrambe riempite), puoi applicare una tecnica di divide et impera qui, che diventa più veloce della tua approccio originale quando memorizzi nella cache i risultati intermedi.

Per fare ciò, inizi a implementare ricorsivamente BoxIsFilledWithCubes(c,x,y,z) , ad esempio:

 bool BoxIsFilledWithCubes(coord,lx,ly,lz)
 {
     if(lx==0|| ly==0 || lz==0)
        return true;
     if(lx==1 && ly==1 && lz==1)
          return world.Contains(coord);
     if(lx>=ly && lx>=lz)  // if lx is the maximum of lx,ly,lz ....
         return BoxIsFilledWithCubes(coord,lx/2,ly,lz) 
             && BoxIsFilledWithCubes(coord.Offset(lx/2,0,0), lx-lx/2, ly, lz);
     else if(ly>=lz && ly>=lx)  
         // ... analogously when ly or lz is the maximum

 }

e quindi usa memoization (come se fosse discusso qui ) per evitare chiamate ripetute a BoxIsFilledWithCubes con gli stessi parametri. Nota che dovrai cancellare la cache di memoizzazione quando applichi una modifica al tuo contenitore world , come per world.RemoveRange . Tuttavia penso che questo renderà il tuo programma più veloce.

score 5 · Answer 2

Costruisci un albero con un nodo foglia a una dimensione della dimensione della tua scatola. Mentre attraversi l'albero puoi unire a buon mercato i nodi. I nodi completamente riempiti sono banali da unire (nuova casella = parent aabb), mentre per i nodi parzialmente pieni, è possibile utilizzare una variante dell'algoritmo corrente per verificare l'univocità.

score 1 · Answer 3

Sembra che tu sia almeno O (n ^ 2) (vedi notazione O grande ) mentre esegui il loop su tutte le caselle del mondo in "Begin ()", quindi per ogni casella, esegui il loop su tutte le caselle del mondo in ExtractLargest (). Quindi un mondo con 10 caselle non correlate impiegherà 4 volte più a lungo di un mondo con 5 caselle non correlate.

Devi quindi limitare il numero di caselle che ExtractLargest () deve guardare, per farlo devi usare qualche tipo di ricerca spaziale , visto che stai lavorando in 3d, potresti aver bisogno di una ricerca spaziale 3d. Tuttavia, per prima cosa inizia a comprendere la ricerca spaziale 2D.

Quindi considera se avrai mai più caselle sopra l'altra, altrimenti una ricerca spaziale 2D che copre solo x, y potrebbe essere sufficiente per ridurre il loop.

Octree / quadtree sono un'opzione, ma ci sono molte altre opzioni per partizionamento dello spazio ,

Ma potresti essere in grado di utilizzare solo un array bidimensionale di elenchi ( Indice spaziale griglia ) , dove tutte le caselle che coprono il punto (a, b) sono in array [a, b] .list. Ma la cosa più lenta potrebbe portare a un array troppo grande, quindi per quanto riguarda l'array [mod (a, 100), mob (b, 100)]. Lista? Tutto dipende da come sono i tuoi dati .

(Ho visto che la soluzione della griglia funziona molto bene nella vita reale.)

O fai quello che Wilbert dice con un albero con un nodo foglia a dimensione della tua scatola, ma in seguito probabilmente dovrai trovare la scatola su cui punta il mouse dell'utente ecc., ancora una volta un caso di ricerca spaziale.

( Devi decidere se stai solo cercando di far funzionare questo software, o se stai cercando di capire come essere un programmatore migliore e quindi sei più interessato all'apprendimento di una soluzione rapida. )