Разделите прямоугольник в почти квадраты данных областей
У меня есть ряд N положительные числа и прямоугольник X и Y размеров, которых я должен разделить в меньшие прямоугольники N, таким образом что:
- площадь поверхности каждого меньшего прямоугольника пропорциональна своему соответствующему числу в данном наборе
- все место большого прямоугольника занято и между меньшими прямоугольниками нет никакого оставшегося пространства
- каждый маленький прямоугольник должен быть сформирован как близко к квадрату как выполнимый
- время выполнения должно быть довольно маленьким
Мне нужны направления на этом. Вы знаете о таком алгоритме, описанном в сети? У Вас есть какие-либо идеи (псевдокод прекрасен)?
Спасибо.
2 ответа
То, что вы описываете, звучит как древовидная карта :
Древовидная карта отображает иерархические (древовидные) данные в виде набора вложенных прямоугольников. Каждой ветви дерева дается прямоугольник, который затем выложен меньшими прямоугольниками, представляющими подветви. Прямоугольник конечного узла имеет площадь, пропорциональную указанному размеру данных.
Эта страница Википедии ссылается на страницу Бена Шнейдермана , которая дает хороший обзор и ссылки на реализации Java:
Затем, пока я ломал голову над этим в кабинете преподавателей, у меня была Ага! опыт разделения экрана на прямоугольники в чередующемся горизонтальном и вертикальном направлениях при перемещении вниз по уровням. Этот рекурсивный алгоритм казался привлекательным, но мне потребовалось несколько дней, чтобы убедить себя, что он всегда будет работать, и написать алгоритм из шести строк.
Википедия также к «Квадратные карты деревьев» Марка Брюльса, Киса Хейзинга и Джарка Дж. Ван Вейка (PDF), который представляет один из возможных алгоритмов:
Как мы можем рекурсивно разбить прямоугольник на прямоугольники, чтобы их соотношения сторон (например, max (высота / ширина, ширина / высота)) максимально приближались к 1? Количество всевозможных мозаик очень велико. Эта проблема относится к категории NP-сложных. Однако для нашего приложения оптимальное решение не требуется, требуется хорошее решение , которое можно вычислить за короткое время.
Вы не упоминаете никакой рекурсии в вопросе, поэтому ваша ситуация может быть только одним уровнем древовидной карты; но поскольку алгоритмы работают на одном уровне за раз, это не должно быть проблемой.
Я работал над чем-то похожим. Я отдаю предпочтение простоте, а не получению как можно более близких соотношений сторон. Это должно (теоретически) работать. Протестировал его на бумаге для некоторых значений N от 1 до 10.
N = общее количество создаваемых прямоугольников, Q = макс (ширина, высота) / мин (ширина, высота), R = N / Q
Если Q> N / 2, разделите прямоугольник на N частей по его самой длинной стороне. Если Q <= N / 2, разделите прямоугольник на части R (округленное целое число) по его кратчайшей стороне. Затем разделите субректы на части N / R (целое число с округлением вниз) по самой короткой стороне. Вычтите округленное значение из результата следующего деления на части. Повторите эти действия для всех частей или до тех пор, пока не будет создано необходимое количество прямоугольников.