Разбить прямоугольник на почти квадраты заданных областей - PullRequest
Новая
       5

Разбить прямоугольник на почти квадраты заданных областей

7 голосов
/ 28 марта 2010

У меня есть набор N положительных чисел и прямоугольник с размерами X и Y , которые мне нужно разделить на N меньшие прямоугольники, такие что:

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

Мне нужны указания по этому вопросу. Знаете ли вы о таком алгоритме, описанном в Интернете? У вас есть идеи (псевдокод в порядке)?

Спасибо.

Ответы [ 2 ]

9 голосов
/ 28 марта 2010

То, что вы описываете, звучит как древовидная карта :

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

Эта страница Википедии ссылается на страницу Бена Шнейдермана , которая дает хороший обзор и ссылки на реализации Java:

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

Википедия также «Квадратные древовидные карты» Марка Брюлса, Киса Хьюзинга и Джарка Дж. Ван Вейка (PDF), в которых представлен один из возможных алгоритмов:

Как мы можем рекурсивно разделить прямоугольник на прямоугольники так, чтобы их пропорции (например, max (высота / ширина, ширина / высота)) приближались к 1 как можно ближе? Количество всевозможных тесселяций очень велико. Эта проблема попадает в категорию NP-сложных задач. Однако для нашего приложения нам не нужно оптимальное решение, хорошее решение это может быть вычислено в короткие сроки.

Вы не упоминаете никакой рекурсии в этом вопросе, поэтому ваша ситуация может быть только одним уровнем древовидной карты; но поскольку алгоритмы работают на одном уровне одновременно, это не должно быть проблемой.

1 голос
/ 17 июня 2010

Я работал над чем-то похожим. Я отдаю приоритет простоте, а не получаю максимально возможное соотношение сторон. Это должно (в теории) работать. Протестировано на бумаге для некоторых значений N от 1 до 10.

N = общее количество создаваемых ректов, Q = max (ширина, высота) / min (ширина, высота), R = N / Q

Если Q> N / 2, разбить прямоугольник на N частей вдоль его самой длинной стороны. Если Q <= N / 2, разделите прямоугольник на R (округленные int) части вдоль его самой короткой стороны. Затем разделите субрекции на N / R (округленные до int) части вдоль его самой короткой стороны. Вычтите округленное значение из результата следующего подразделения subrects. Повторите эти действия для всех подразделов или до тех пор, пока не будет создано необходимое количество повторений. </p>

...