Mon algorithme qui extrait la plus grande boîte qui peut être faite de petites boîtes, est trop lent

Imaginez un monde basé sur des cubes (comme Minecraft, Trove ou Cube World) où tout est composé de cubes de taille identique et tous les cubes sont du même type .

L'objectif est de représenter le monde avec le moins de boîtes rectangulaires (en fusionnant des cubes mais en conservant une forme convexe (aka, une forme de boîte rectangulaire)). Mon algorithme y parvient, mais ses performances sont trop lentes pour l'usage auquel il est destiné. Existe-t-il des algorithmes plus rapides?

Le pseudo-code C # de mon algorithme est essentiellement:

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;
}

Essentiellement, pour chaque bloc du monde, il trouve d'abord le nombre de blocs contigus dans chacune des trois dimensions positives (+ X, + Y, + Z). Et puis il remplit un peu ce volume et vérifie quel est le plus grand remplissage qui ne manque aucun bloc.

Vous pouvez utiliser le fait que lorsque

 BoxIsFilledWithCubes(c,x,y,z)

renvoie true, il n'est donc pas nécessaire de réarchiver BoxIsFilledWithCubes(c,x+1,y,z)tous ces cubes dans la plage de coordonnées "(c, x, y, z)". Il vous suffit de vérifier ces cubes avec la nouvelle coordonnée x c.x + (x+1). (Il en va de même pour y+1, ou z+1). Plus généralement, en divisant une boîte en deux petites boîtes (pour lesquelles vous savez peut-être déjà si elles sont toutes deux remplies de cubes, ou pas toutes les deux), vous pouvez appliquer ici une technique de division et de conquête, qui devient plus rapide que votre approche originale lorsque vous mettez en cache les résultats intermédiaires.

Pour ce faire, vous commencez à implémenter BoxIsFilledWithCubes(c,x,y,z)récursivement, par exemple:

 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

 }

puis utilisez la mémorisation (comme cela est discuté ici ) pour éviter tout appel répété à BoxIsFilledWithCubesavec les mêmes paramètres. Notez que vous devrez vider le cache de mémorisation lorsque vous appliquez une modification à votre worldconteneur, comme par world.RemoveRange. Néanmoins, je suppose que cela rendra votre programme plus rapide.

Construisez un octree avec un nœud de feuille de la taille de votre boîte. En parcourant l'octree, vous pouvez fusionner des nœuds à moindre coût. Les nœuds complètement remplis sont faciles à fusionner (nouvelle boîte = parent aabb), tandis que pour les nœuds partiellement remplis, vous pouvez utiliser une variante de votre algorithme actuel pour vérifier la capacité de fusion.

Vous semblez être au moins O (n ^ 2) (voir la grande notation O ) lorsque vous bouclez sur toutes les cases du monde dans "Begin ()", puis pour chaque case, vous bouclez sur toutes les cases du monde dans ExtractLargest ( ). Ainsi, un monde avec 10 cases indépendantes prendra 4 fois plus de temps qu'un monde avec 5 cases indépendantes.

Vous devez donc limiter le nombre de cases que ExtractLargest () doit regarder, pour ce faire, vous devez utiliser un certain type de recherche spatiale , comme vous travaillez en 3D, vous devrez peut-être une recherche spatiale 3D. Cependant, commencez par comprendre la recherche spatiale 2D.

Ensuite, demandez-vous si vous aurez jamais beaucoup de cases les unes sur les autres, sinon une recherche spatiale 2D qui ne couvre que x, y peut être suffisante pour réduire votre boucle.

Octree / quadtree sont une option, mais il existe de nombreuses autres options pour le partitionnement de l'espace ,

Mais vous pouvez peut-être simplement utiliser un tableau de listes bidimensionnel ( indice spatial de la grille ), où toutes les cases qui couvrent le point (a, b) sont dans le tableau [a, b] .list. Mais surtout, cela conduirait à un tableau trop grand, alors qu'en est-il du tableau [mod (a, 100), mob (b, 100)]. List? Tout dépend de la nature de vos données .

(J'ai vu la solution de grille fonctionner très bien dans la vie réelle.)

Ou faites ce que Wilbert dit avec un octree avec un nœud feuille taille de la taille de votre boîte, mais plus tard, vous devrez probablement trouver la boîte vers laquelle la souris de l'utilisateur pointe, etc., encore une fois un cas de recherche spatiale.

( Vous devez décider si vous essayez simplement de faire fonctionner ce logiciel, ou si vous essayez de comprendre comment être un meilleur programmeur et que vous êtes donc plus intéressé par l'apprentissage que par une solution rapide. )