Найдите самую маленькую область, содержащую все прямоугольники

Ответ 1

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

Ответ 2

Оптимальная упаковка прямоугольников на неквадратных тестах:

Учитывая набор прямоугольников, наша задача - найти все закрывающие прямоугольники минимальной площади, которые будут содержать их без перекрытия. Мы обратитесь к замкнутому прямоугольнику в качестве ограничивающего прямоугольника. Оптимизация проблема NP-hard, в то время как проблема определения того, является ли набор прямоугольники могут быть упакованы в заданный ограничивающий прямоугольник NP-complete, через сокращение от бин-упаковки (Korf 2003).

Новые улучшения в оптимальной упаковке прямоугольника:

Корф [2003] разделил проблему упаковки прямоугольника на две подзадачи: проблема минимального ограничивающего прямоугольника и сдерживание проблема. Первый находит ограничивающий прямоугольник наименьшей площади, который может содержат заданный набор прямоугольников, в то время как последний пытается упаковать заданные прямоугольники в заданной ограничивающей рамке. Алгоритм, который решает задача минимального ограничивающего прямоугольника вызывает алгоритм, который решает проблема сдерживания как подпрограмма.

Задача с минимальным ограничением полетов

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

См. также Оптимальная упаковка прямоугольника: новые результаты.

Ответ 3

Прежде всего, вы должны проверить, может ли быть включен прямоугольник или нет? В любом случае, вы можете игнорировать условие "прямоугольники" и разрешать задачу в точках. У вас есть массив точек (которые являются вершинами прямоугольников). Ваша задача - найти прямоугольник с минимальной площадью. Если прямоугольник с прямоугольником не может быть повернут, то решение глупо и имеет сложность O (n).

Сгенерированный массив прямоугольников и создайте массив точек, которые являются вершинами прямоугольников. Далее просто:

long n; // Number of vertexes
point arr[SIZE]; //Array of vertexes
long minX = MAXNUMBER, minY = MAXNUMBER, maxX = -MAXNUMER, maxY = -MAXNUMBER;
for (long i = 0; i < 4 * n; i++)
{
    minX = MIN(minX, arr[i].x);
    minY = MIN(minY, arr[i].y);
    maxX = MIN(maxX, arr[i].x);
    maxY = MIN(maxY, arr[i].y);
}
long width = maxX - minX, height = maxY - minY;
printf("%ddX%ld", width, height);

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

• Построить минимальный выпуклый многоугольник всех точек в прямоугольнике. Ты можешь используйте любой из существующих алгоритмов. Сложность O (n log n). Как exmaple "Graham Scan": http://en.wikipedia.org/wiki/Graham%27s_scan
• Используйте простой алгоритм для выпуклого многоугольника. Ссылка: http://cgm.cs.mcgill.ca/~orm/maer.html

Ссылка на вашу задачу в wiki: http://en.wikipedia.org/wiki/Minimum_bounding_rectangle