Нужен алгоритм для расчета размера прямоугольника - PullRequest
Новая
       17

Нужен алгоритм для расчета размера прямоугольника

0 голосов
/ 14 февраля 2012

У меня есть логическая загадка, и мне нужен эффективный алгоритм для ее решения.

У меня большой прямоугольник (коробка) размером w * h (ширина * высота).

У меня также есть x других прямоугольников не размера, а с фиксированными пропорциями.

Какой самый быстрый способ получить x, который позволит каждому прямоугольнику X иметь максимальный размер внутри прямоугольника (большой прямоугольник)?

Пример:

Размер прямоугольника коробки составляет 150 * 50 (ширина * высота), и у меня есть 25 маленьких прямоугольников.

Фиксированная пропорция маленького прямоугольника равна 3 (если высота = 5, то ширина = 5 * 3 = 15). Позволяет назвать высоту прямоугольника х.

Я хочу найти тот самый большой X, который позволит мне вставить весь прямоугольник в большой прямоугольник (в поле).

(Маленькие прямоугольники будут размещены в строках и столбцах, например, 5 столбцов и 5 строк по пропорции и максимальной высоте)

Кто-нибудь знает эффективный алгоритм для решения этой проблемы?

Ответы [ 2 ]

0 голосов
/ 14 февраля 2012

Я бы попытался решить эту проблему эмпирически (решить, используя возврат ) вместо аналитического, то есть найти все возможности * (я объясню *).По сути, мы хотим поместить каждый прямоугольник, начиная с минимального размера этого прямоугольника, до его максимального размера (максимальный размер может быть определен по наибольшему прямоугольнику до столкновения с начальной точкой его соседей или роста до главного прямоугольника контейнера).Это означает, что если мы попытаемся поместить каждый прямоугольник во все его возможные размеры, одно из этих решений будет лучшим решением.Также обратите внимание, что это действительно одномерная проблема, так как высота и ширина канавок связаны соотношением;установка одного неявно устанавливает другого.

* - Когда я сказал все возможности, я действительно имел в виду наиболее разумные возможности.Поскольку мы находимся в пространстве с плавающей запятой, мы не можем проверить ВСЕ возможности.Мы можем проверять более высокую точность, но не сможем проверить все размеры.В связи с этим мы определяем размер шага для итерации по размеру ритов, которые мы попробуем.

const float STEP_SIZE = 0.0001;
float fLastTotalSize = 0;

int main()
{
  PlaceRect(myRects.begin(), myRects.end());
}

void PlaceRect(Iterator currentRect, Iterator end)
{
  if (currentRect == end)
  {
    return;
  }

  float fRectMaxSize = CalculateMaxPossibleRectSize(*currentRect);

  // find the number of steps it will take to iterate from the smallest 
  // rect size to the largest
  int nSteps = fRectMaxSize / STEP_SIZE;

  for(int i = 0; i < nSteps; ++i)
  {
    // based on the step index scale the rect size
    float fCurrentRectTestSize = i*STEP_SIZE;

    currentRect->SetSize(fCurrentRectTestSize);

    float fTotalSize = CalculateTotalSizesOfAllRects();
    if (fTotalSize > fLastTotalSize)
    {
      fLastTotalSize = fTotalSize;
      SaveRectConfiguration();
    }

    // Continue placing the rest of the rects assuming the size 
    // we just set for the current rect 
    PlaceRect(currentRect + 1, end);

    // Once we return we can now reset the current rect size to 
    // something else and continue testing possibilities 
  }
}

Исходя из размера шага и количества прямоугольников, этот процесс может выполняться очень долго, но он найдет вам эмпирическое решение.

0 голосов
/ 14 февраля 2012

Хм что?

Разве это не просто (ш * ч) / 75?

Да, скобки не нужны ... но разве это не то, что вы хотите? Или я тут кое-что упустил?

Где w и h - размеры большого или родительского прямоугольника. И 75 это 3 * 25.

...