Алгоритм стека (масштабируемый)

Question

Вот проблема. У меня есть прямоугольный холст, который имеет размер 1. Таким образом, он имеет систему координат (0,0 ... 1,0 - х и 0,0 ... 1,0 - у).

У меня также есть несколько плиток. Плитки тоже прямоугольники. У них разные размеры и количество плиток является переменной.

Я хочу укладывать плиток в прямоугольный холст, от 0,0 до 1,0 ( слева направо, сверху вниз ):

1) плитки должны помещаться на холсте (но заполнять как можно больше места)

2) плитки должны масштабироваться (если они не умещаются), каждая плитка должна масштабироваться на одинаковое количество (они должны оставаться в одинаковых пропорциях).

3) представьте, что у вас в руке есть эти «плитки», и вы помещаете их в этот холст один за другим

4) это почти как «алгоритм TreeMap» но - форма плиток должна быть одинаковой ( прямоугольники ) и мне не нужно заполнять все пространство холст

Есть ли кто-нибудь, кто может показать мне алгоритм на любом языке, подобном C (C, C ++, Java, C #)?

* Я пробовал это.

1) я вычислил площадь плитки, затем я вычислил сумму областей плитки (например: у меня есть две плитки, одна имеет площадь 2, другая область 1, они означают, что у меня есть общая сумма 3)

2) затем я вычисляю, какую «пропорцию» имеет каждая плитка в «общей сумме площадей» (например: 2/3 и 1/3)

3) затем вычислите размер прямоугольной плитки с помощью Math.sqrt (x) (например: Math.sqrt (2/3))

4) затем нарисуйте плитку одну за другой ...

Но это не всегда работает. Иногда я получаю плитки вне холста .. *

Answer 1

Может показаться, что это проблема упаковки, однако, если мы попытаемся решить эту проблему в точности так, как она описана, это не так.Другими словами, нет решения, потому что, опять же, нет проблемы в вопросе, который описан.Если у нас есть ТОЛЬКО ОДИН бокс и фиксированный набор плиток и требование, чтобы они ВСЕ должны были помещаться в бокс, нет места для оптимизации.Я вижу несколько проблем, связанных с оптимизацией:

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

2.Для данного отдельного блока произвольного размера и набора плиток найдите оптимальный (максимальный) набор плиток, который можно уместить в ящик.

3.Если у вас есть коробка и набор плиток - ответьте на вопрос, можно ли вписать их в коробку или нет.

Какой из них вы пытаетесь решить?

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

Answer 2

Я не думаю, что это проблема (bin) -пакетирования, потому что я написал для проблемы 1D-bin-pack.Я думаю, что проблема здесь решена с помощью 2D-заготовки, может быть, есть также 2D-упаковка.То, что вы хотите, это попробовать проблему с рюкзаком.Эту проблему трудно решить (NP), и нет решения.Это немного похоже на проблему Travelsalesman, где количество решений экспоненциально по отношению к количеству городов.Если вы можете уменьшить сложность до проблемы 1D, вы можете попробовать мой алгоритм упаковки бинов на phpclasses.org.

Answer 3

Попробуйте алгоритм Монте-Карло:

Repeat until result is good enough or until you aren't seeing any improvement
  Select (with removal) a random first tile
  Place the first tile at a random position
  Repeat until no remaining tiles
    Select (with removal) a random tile
    Place it adjoining to the existing "tile blob" 
      (you might have to do a search here to find the best place to plug it in)
  Check to see if you have a new best filled-area percentage

Все случайные выборки плиток должны быть взвешены по площади плитки, чтобы вы, как правило, размещали более крупные плитки в первую очередь.

Answer 4

Как отмечали другие - описание проблемы не очень понятно. Но я предполагаю, что вы можете масштабировать каждую плитку по мере необходимости (по крайней мере, ваши примеры показывают, что масштабирование плитки возможно). Таким образом, мое решение будет простым (но, возможно, не тем, что вы хотите, ни оптимальным):

• Масштаб каждой плитки по коэффициенту:

  EDGE<sub>space</sub> / (EDGE<sub>tile</sub> * N<sup> ½</sup>)

• Поместите каждый тайл в текущий ряд, если тайл выходит за пределы пространства - перейдите к следующему ряду.

Здесь N является ближайшим идеальным квадратом больше или равно общему количеству плиток.

p.s. Если вам нужен промежуток между плитками - просто сделайте выше масштабный коэффициент немного меньше.

Надеюсь, это поможет.

Answer 5

Я не уверен, что это то, что вам нужно, но вы можете взглянуть на алгоритм TreeMap.

Определение Википедии

C ++ реализация