Мне нужен алгоритм, который будет принимать n прямоугольников любых размеров и вычисляет прямоугольник, достаточно большой, чтобы соответствовать всем этим, сводя к минимуму его площадь, чтобы потерянная площадь была минимальной, а также возвращала положение всех меньших прямоугольников внутри.
Конкретная задача, для которой мне нужно это реализовать, заключается в компиляторе листа спрайтов, который будет принимать отдельные PNG файлы и создавать большой PNG со всеми изображениями в нем, поэтому отдельные кадры могут быть смешаны с этой поверхности во время выполнения.
Приятно иметь особенность в том, что она нацелена на конкретное заданное отношение ширины/высоты, но это не обязательно.
Я бы предпочел простой, общий код, который я могу переносить на другой язык.
Petruza,
Я бы начал с этой статьи: http://www.codeproject.com/KB/web-image/rectanglepacker.aspx#basic
Он имеет большое объяснение проблемного пространства применительно к вашему конкретному использованию (упаковка Sprite). Он также подробно описывает алгоритм, и в нижней части статьи есть образец кода С#.
Счастливое кодирование.
Это то, что я собрал для своих нужд. Параметр T - это любой объект, который вы хотите связать с результатами (подумайте об этом как свойство Tag). Он принимает список размеров и возвращает список Rect, которые расположены
static class LayoutHelper
{
static public List<Tuple<T, Rect>> BestFitRects<T>(double desiredWidthToHeightRatio,
List<Tuple<Size, T>> rectsToArrange)
{
var CheckIfRectsIntersect = new Func<Rect, List<Rect>, double, bool>((Rect one, List<Rect> list,
double containerHeight) =>
{
if (one.Y + one.Height > containerHeight) return true;
return list.Any(two =>
{
if ((one.Top > two.Bottom) ||
(one.Bottom < two.Top) ||
(one.Left > two.Right) ||
(one.Right < two.Left)) return false;
return true;
});
});
var sync = new object();
var containingRectHeight = Convert.ToInt32(rectsToArrange.Max(a => a.Item1.Height));
var largestToSmallest = rectsToArrange.OrderByDescending(a => a.Item1.Height).ToList();
var totalHeight = Convert.ToInt32(rectsToArrange.Sum(a => a.Item1.Height));
List<Tuple<T, Rect>> bestResults = null;
var bestResultsProximityToDesiredRatio = double.MaxValue;
Parallel.For(containingRectHeight, totalHeight, currentHeight =>
{
var results = new List<Tuple<T, Rect>>();
largestToSmallest.ForEach(currentSize =>
{
var leftMostFit = new Rect(double.MaxValue, double.MaxValue,
currentSize.Item1.Width, currentSize.Item1.Height);
results.ForEach(placedRect =>
{
var belowBottomLeftPoint = new Point(placedRect.Item2.BottomLeft.X,
placedRect.Item2.BottomLeft.Y + 1);
var newRect = new Rect(belowBottomLeftPoint,
new Point(belowBottomLeftPoint.X + currentSize.Item1.Width,
belowBottomLeftPoint.Y + currentSize.Item1.Height));
if (!CheckIfRectsIntersect(newRect, results.Select(a => a.Item2).ToList(), currentHeight))
{
if (newRect.X < leftMostFit.X) leftMostFit = newRect;
}
else
{
var besideTopRightPoint = new Point(placedRect.Item2.TopRight.X + 1,
placedRect.Item2.TopRight.Y);
newRect = new Rect(besideTopRightPoint,
new Point(besideTopRightPoint.X + currentSize.Item1.Width,
besideTopRightPoint.Y + currentSize.Item1.Height));
if (!CheckIfRectsIntersect(newRect, results.Select(a => a.Item2).ToList(), currentHeight))
if (newRect.X < leftMostFit.X) leftMostFit = newRect;
}
});
if (leftMostFit.Top == double.MaxValue) leftMostFit =
new Rect(0, 0, currentSize.Item1.Width, currentSize.Item1.Height);
results.Add(Tuple.Create(currentSize.Item2, leftMostFit));
});
var ratioProximity = Math.Abs((results.Max(a => a.Item2.X + a.Item2.Width) /
currentHeight) - desiredWidthToHeightRatio);
lock (sync)
{
if (ratioProximity < bestResultsProximityToDesiredRatio)
{
bestResults = results;
bestResultsProximityToDesiredRatio = ratioProximity;
}
}
});
return bestResults;
}
}