Algorithme pour maximiser la couverture de zone rectangulaire avec des carreaux d'échelle
https://stackoverflow.com/questions/3859891
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je N tuiles carrées extensibles (boutons) qui doivent être placé à l'intérieur de la surface rectangulaire de taille fixe (boîte à outils). Je voudrais présenter les boutons tous à la même taille.
Comment pourrais-je résoudre pour la taille optimale des tuiles qui fourniraient la plus grande surface de la surface rectangulaire étant recouverte par les tuiles.
La solution
Soit W et H soient la largeur et la hauteur du rectangle.
Soit s soit la longueur du côté du carré.
Ensuite, le nombre de places n(s) que vous pouvez entrer dans le rectangle est floor(W/s)*floor(H/s). Vous voulez trouver la valeur maximale de s pour lesquels n(s) >= N
Si vous tracez le nombre de places contre s vous obtiendrez une fonction constante par morceaux. Les discontinuités sont à la valeur W/i et H/j, où l'exécution de i et j à travers les entiers positifs.
Vous voulez trouver le plus petit i pour lequel n(W/i) >= N, et de même le plus petit j pour lequel n(H/j) >= N. Appelons ces plus petites valeurs i_min et j_min. Ensuite, le plus grand de W/i_min et H/j_min est le s que vous voulez.
i.e.. s_max = max(W/i_min,H/j_min)
Pour i_min et j_min, juste faire une recherche de force brute: pour chacun, commencer à partir de 1, le test et l'incrément.
Dans le cas où N est très grand, il peut être de mauvais goût pour rechercher les années de i et j à partir de 1 (bien qu'il soit difficile d'imaginer qu'il y aura une différence notable dans la performance). Dans ce cas, on peut estimer les valeurs de départ comme suit. Tout d'abord, une estimation approximative de la surface de la tuile est W*H/N, ce qui correspond à un côté de sqrt(W*H/N). Si W/i <= sqrt(W*H/N), i >= ceil(W*sqrt(N/(W*H))) alors, de même j >= ceil(H*sqrt(N/(W*H)))
Alors, plutôt que de commencer les boucles à i=1 et j=1, nous pouvons les lancer à i = ceil(sqrt(N*W/H)) et j = ceil(sqrt(N*H/W))). Et OP suggère que round fonctionne mieux que ceil - au pire une itération supplémentaire.
Voici l'algorithme épeautre en C ++:
#include <math.h>
#include <algorithm>
// find optimal (largest) tile size for which
// at least N tiles fit in WxH rectangle
double optimal_size (double W, double H, int N)
{
int i_min, j_min ; // minimum values for which you get at least N tiles
for (int i=round(sqrt(N*W/H)) ; ; i++) {
if (i*floor(H*i/W) >= N) {
i_min = i ;
break ;
}
}
for (int j=round(sqrt(N*H/W)) ; ; j++) {
if (floor(W*j/H)*j >= N) {
j_min = j ;
break ;
}
}
return std::max (W/i_min, H/j_min) ;
}
Ce qui précède est écrit pour plus de clarté. Le code peut être resserré suit considérablement:
double optimal_size (double W, double H, int N)
{
int i,j ;
for (i = round(sqrt(N*W/H)) ; i*floor(H*i/W) < N ; i++){}
for (j = round(sqrt(N*H/W)) ; floor(W*j/H)*j < N ; j++){}
return std::max (W/i, H/j) ;
}
Autres conseils
Je crois que cela peut être résolu comme un problème de minimisation sous contrainte, ce qui nécessite un calcul de base. .
Définitions:
a, l -> rectangle sides
k -> number of squares
s -> side of the squares
Vous devez minimiser la fonction:
f[s]:= a * l/s^2 - k
sous réserve des contraintes:
IntegerPart[a/s] IntegerPart[l/s] - k >= 0
s > 0
Je fonction un peu programmé Mathematica faire l'affaire
f[a_, l_, k_] := NMinimize[{a l/s^2 - k ,
IntegerPart[a/s] IntegerPart[l/s] - k >= 0,
s > 0},
{s}]
Facile à lire puisque les équations sont les mêmes que ci-dessus.
L'utilisation de cette fonction I constituée d'une table d'allocation 6 places
pour autant que je peux voir, les résultats sont corrects.
Comme je l'ai dit, vous pouvez utiliser un paquet de calcul standard pour votre environnement, ou vous pouvez également développer votre propre algorithme de minimisation et des programmes. Sonnez si vous décidez pour la dernière option et je vais fournir quelques bons pointeurs.
HTH!
Modifier
Juste pour le plaisir que je fait un terrain avec les résultats.
Et pour 31 tuiles:
Edit 2: paramètres caractéristiques
Le problème a trois paramètres caractéristiques:
- La taille résultante des tuiles
- Le nombre de tuiles
- le rapport L / a du rectangle englobant
Peut-être le dernier peut entraîner quelque peu surprenant, mais il est facile de comprendre: si vous avez un problème avec un rectangle de 7x5 et 6 tuiles en place, regardant dans le tableau ci-dessus, la taille des carrés sera 2,33. Maintenant, si vous avez un rectangle 70x50, évidemment les tuiles résultantes seront 23,33, mise à l'échelle isométriquement le problème.
Alors, nous pouvons prendre ces trois paramètres et construire un tracé 3D de leur relation, et éventuellement correspondre à la courbe avec une fonction plus facile à calculer (en utilisant les moindres carrés par exemple ou calcul régions iso-valeur).
Quoi qu'il en soit, le tracé mis à l'échelle résultante est:
Je sais que c'est un vieux fil, mais je récemment résolu ce problème d'une manière que je pense est efficace et donne toujours la bonne réponse. Il est conçu pour maintenir un rapport d'aspect donné. Si vous le souhaitez pour les enfants (boutons dans ce cas) pour être carré il suffit d'utiliser un rapport d'aspect de 1. Je suis actuellement en utilisant cet algorithme dans quelques endroits et il fonctionne très bien.
double VerticalScale; // for the vertical scalar: uses the lowbound number of columns
double HorizontalScale;// horizontal scalar: uses the highbound number of columns
double numColumns; // the exact number of columns that would maximize area
double highNumRows; // number of rows calculated using the upper bound columns
double lowNumRows; // number of rows calculated using the lower bound columns
double lowBoundColumns; // floor value of the estimated number of columns found
double highBoundColumns; // ceiling value of the the estimated number of columns found
Size rectangleSize = new Size(); // rectangle size will be used as a default value that is the exact aspect ratio desired.
//
// Aspect Ratio = h / w
// where h is the height of the child and w is the width
//
// the numerator will be the aspect ratio and the denominator will always be one
// if you want it to be square just use an aspect ratio of 1
rectangleSize.Width = desiredAspectRatio;
rectangleSize.Height = 1;
// estimate of the number of columns useing the formula:
// n * W * h
// columns = SquareRoot( ------------- )
// H * w
//
// Where n is the number of items, W is the width of the parent, H is the height of the parent,
// h is the height of the child, and w is the width of the child
numColumns = Math.Sqrt( (numRectangles * rectangleSize.Height * parentSize.Width) / (parentSize.Height * rectangleSize.Width) );
lowBoundColumns = Math.Floor(numColumns);
highBoundColumns = Math.Ceiling(numColumns);
// The number of rows is determined by finding the floor of the number of children divided by the columns
lowNumRows = Math.Ceiling(numRectangles / lowBoundColumns);
highNumRows = Math.Ceiling(numRectangles / highBoundColumns);
// Vertical Scale is what you multiply the vertical size of the child to find the expected area if you were to find
// the size of the rectangle by maximizing by rows
//
// H
// Vertical Scale = ----------
// R * h
//
// Where H is the height of the parent, R is the number of rows, and h is the height of the child
//
VerticalScale = parentSize.Height / lowNumRows * rectangleSize.Height;
//Horizontal Scale is what you multiply the horizintale size of the child to find the expected area if you were to find
// the size of the rectangle by maximizing by columns
//
// W
// Vertical Scale = ----------
// c * w
//
//Where W is the width of the parent, c is the number of columns, and w is the width of the child
HorizontalScale = parentSize.Width / (highBoundColumns * rectangleSize.Width);
// The Max areas are what is used to determine if we should maximize over rows or columns
// The areas are found by multiplying the scale by the appropriate height or width and finding the area after the scale
//
// Horizontal Area = Sh * w * ( (Sh * w) / A )
//
// where Sh is the horizontal scale, w is the width of the child, and A is the aspect ratio of the child
//
double MaxHorizontalArea = (HorizontalScale * rectangleSize.Width) * ((HorizontalScale * rectangleSize.Width) / desiredAspectRatio);
//
//
// Vertical Area = Sv * h * (Sv * h) * A
// Where Sv isthe vertical scale, h is the height of the child, and A is the aspect ratio of the child
//
double MaxVerticalArea = (VerticalScale * rectangleSize.Height) * ((VerticalScale * rectangleSize.Height) * desiredAspectRatio);
if (MaxHorizontalArea >= MaxVerticalArea ) // the horizontal are is greater than the max area then we maximize by columns
{
// the width is determined by dividing the parent's width by the estimated number of columns
// this calculation will work for NEARLY all of the horizontal cases with only a few exceptions
newSize.Width = parentSize.Width / highBoundColumns; // we use highBoundColumns because that's what is used for the Horizontal
newSize.Height = newSize.Width / desiredAspectRatio; // A = w/h or h= w/A
// In the cases that is doesnt work it is because the height of the new items is greater than the
// height of the parents. this only happens when transitioning to putting all the objects into
// only one row
if (newSize.Height * Math.Ceiling(numRectangles / highBoundColumns) > parentSize.Height)
{
//in this case the best solution is usually to maximize by rows instead
double newHeight = parentSize.Height / highNumRows;
double newWidth = newHeight * desiredAspectRatio;
// However this doesn't always work because in one specific case the number of rows is more than actually needed
// and the width of the objects end up being smaller than the size of the parent because we don't have enough
// columns
if (newWidth * numRectangles < parentSize.Width)
{
//When this is the case the best idea is to maximize over columns again but increment the columns by one
//This takes care of it for most cases for when this happens.
newWidth = parentSize.Width / Math.Ceiling(numColumns++);
newHeight = newWidth / desiredAspectRatio;
// in order to make sure the rectangles don't go over bounds we
// increment the number of columns until it is under bounds again.
while (newWidth * numRectangles > parentSize.Width)
{
newWidth = parentSize.Width / Math.Ceiling(numColumns++);
newHeight = newWidth / desiredAspectRatio;
}
// however after doing this it is possible to have the height too small.
// this will only happen if there is one row of objects. so the solution is to make the objects'
// height equal to the height of their parent
if (newHeight > parentSize.Height)
{
newHeight = parentSize.Height;
newWidth = newHeight * desiredAspectRatio;
}
}
// if we have a lot of added items occaisionally the previous checks will come very close to maximizing both columns and rows
// what happens in this case is that neither end up maximized
// because we don't know what set of rows and columns were used to get us to where we are
// we must recalculate them with the current measurements
double currentCols = Math.Floor(parentSize.Width / newWidth);
double currentRows = Math.Ceiling(numRectangles/currentCols);
// now we check and see if neither the rows or columns are maximized
if ( (newWidth * currentCols ) < parentSize.Width && ( newHeight * Math.Ceiling(numRectangles/currentCols) ) < parentSize.Height)
{
// maximize by columns first
newWidth = parentSize.Width / currentCols;
newHeight = newSize.Width / desiredAspectRatio;
// if the columns are over their bounds, then maximized by the columns instead
if (newHeight * Math.Ceiling(numRectangles / currentCols) > parentSize.Height)
{
newHeight = parentSize.Height / currentRows;
newWidth = newHeight * desiredAspectRatio;
}
}
// finally we have the height of the objects as maximized using columns
newSize.Height = newHeight;
newSize.Width = newWidth;
}
}
else
{
//Here we use the vertical scale. We determine the height of the objects based upong
// the estimated number of rows.
// This work for all known cases
newSize.Height = parentSize.Height / lowNumRows;
newSize.Width = newSize.Height * desiredAspectRatio;
}
A la fin de l'algorithme « newSize » tient la taille appropriée. Ceci est écrit en C # mais il serait assez facile au port à d'autres langues.
La première, heuristique très approximative est de prendre
s = floor( sqrt( (X x Y) / N) )
où s est le bouton du côté de longueur, X et Y sont la largeur et la hauteur de la boîte à outils, et N est le nombre de boutons.
Dans ce cas, s sera la longueur de côté maximum. Il est pas forcément possible de cartographier cet ensemble de boutons sur la barre d'outils, cependant.
Imaginons une barre d'outils qui est de 20 unités par une unité de 5 boutons. L'heuristique vous donnera une longueur de côté de 2 (zone 4), avec une zone de couverture totale de 20. Cependant, la moitié de chaque bouton sera à l'extérieur de la barre d'outils.
je prendrais une approche itérative ici. Je voudrais vérifier s'il est possible d'adapter à tout bouton dans une seule ligne. Sinon, vérifier s'il est possible d'insérer deux lignes, et ainsi de suite.
Say W est le petit côté de la boîte à outils. H est de l'autre côté.
Pour chaque itération, je vérifier les meilleurs et les pires cas possibles, dans cet ordre. Meilleur moyen de cas, disent que c'est la nième itération, tenterait une taille des touches W / n X W / n dimensions. Si la valeur h suffit alors nous avons fini. Dans le cas contraire, le pire des cas est d'essayer (W / (n + 1)) + 1 X (W / (n + 1)) + 1 boutons de taille. S'il est possible d'adapter à tous les boutons, alors je voudrais essayer une méthode bissectrice entre W / n et (W / (n + 1)) + 1. Dans le cas contraire itération continue à n + 1.
Soit n (s) le nombre de carrés qui peuvent convenir et s leur côté. Soit W, H les côtés du rectangle à remplir. Ensuite, n (s) = floor (W / s) * étage (H / s). Ceci est une fonction décroissante de façon monotone dans s et aussi constante par morceaux, de sorte que vous pouvez effectuer une légère modification de la recherche binaire pour trouver le plus petit s tel que n (s)> = N mais n (s + EPS)
Nous savons que toute solution optimale (il peut y avoir deux) remplira le rectangle horizontalement ou verticalement. Si vous avez trouvé une solution optimale qui n'a pas rempli le rectangle dans une dimension, vous pouvez toujours augmenter l'échelle des tuiles pour remplir une dimension.
Maintenant, toute solution qui maximise la surface recouverte aura un rapport d'aspect proche du rapport d'aspect du rectangle. Le rapport d'aspect de la solution est vertical tile count/horizontal tile count (et le rapport d'aspect du rectangle est Y/X).
Vous pouvez simplifier le problème en forçant Y>=X; autrement dit, si X>Y, transposer le rectangle. Cela vous permet de penser seulement des rapports d'aspect> = 1, aussi longtemps que vous vous souvenez de transposer le dos de la solution.
Une fois que vous avez calculé le ratio d'aspect, vous voulez trouver des solutions au problème de V/H ~= Y/X, où V est le nombre vertical de tuiles et H est le nombre de tuiles horizontal. Vous trouverez jusqu'à trois solutions: le plus proche V/H à Y/X et V+1, V-1. À ce moment-là, calculer simplement la couverture basée sur l'échelle en utilisant V et H et prendre le maximum (il pourrait y avoir plus d'un).
