найти минимальное количество прямоугольников для покрытия 2D точечного массива

Question

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

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

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

Answer 1

Как может сделать только эвристическое решение, я бы попытался сделать следующее:

• найти глобальную ограничивающую рамку точек;

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

• , если прямоугольник окажется пустым, отбросьте его.

Вы можете добавить шаг постобработки, пытаясь улучшить:

• выделите пары соседних прямоугольников и найдите ограничивающий прямоугольник точек, которые они покрывают;если этот блок помещается в один прямоугольник, объедините два прямоугольника.

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

Answer 2

Прежде всего, координаты могут быть переведены / спроецированы таким образом, чтобы размер прямоугольника был 1x1, а ориентация - 0 ° (выровнена по оси X / Y).Поэтому я буду предполагать эту ситуацию.

Тогда вы могли бы действовать следующим образом:

1. Сортировать точки по их x -координате
2. Создатьориентированный граф следующим образом:
   • Для каждой точки a взять точки в интервале x [a _x ,a _x + 1] , за исключением самого a
   • Исключить из этого списка те точки, чья координата y не входит вдиапазон [a _y -1, a _y + 1]
   • Сортировать эти точки по y -координировать
   • Поместите эти точки в список смежности для точки a .
3. Пометить все точки как непосещенные
4. Если не было посещенийточки, верните 0, чтобы указать, что (больше) прямоугольники не нужны.
5. Возьмите следующую непосещенную точку a из отсортированного списка точек: отметьте a как посещенные.
6. Если у a нет соседей, то увеличьте прямоугольниксосчитайте и повторите с шага 4
7. Переместите прямоугольник с его левой x -координатой, всегда равной _x , по соседям, так что:
   • первый выбранный прямоугольник имеет свою низкую y -координату, общую с первой не посещенной соседней точкой
   • поддерживает список L соседей, которые посещаются (толькоесли они еще не были помечены как посещенные) путем охвата этим прямоугольником
   • все последующие позиции прямоугольника получают по одной непосещаемой точке на их высоком - y -координированном конце.
   • Точки в L , которые обнаруживаются на нижней стороне скользящего прямоугольника * y , удаляются из L и снова помечаются как непосещенные
   • Каждый раз, когда определяется новая позиция прямоугольника, выполняется рекурсивный вызов (DFS), который начинается на шаге 4.
   • Вызов DFS возвращает количество прямоугольников, которые все еще были необходимы для покрытия всех оставшихся, не посещенныхОчки
   • Держитеминимальное значение, возвращаемое всеми этими рекурсивными вызовами, и добавление 1 (для текущего прямоугольника)
   • Примечание: дерево рекурсии можно удалить, передав текущий минимальный результат в качестве точки отсечения, чтобы избежать поиска, который увеличиваетсяслишком большое количество прямоугольников.
8. Когда все позиции прямоугольников были обработаны, отметьте все точки в L как не посещенные.
9. Вернитенайдено минимальное количество прямоугольников.

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

Потенциальным улучшением могло бы стать использование вместо этого BFS.DFS, используя приоритетную очередь (например, Min Heap).Число, которое нужно минимизировать, - это количество уже использованных прямоугольников (т.е. стоимость до настоящего времени) плюс разность по оси X между самой правой (не посещенной) точкой и самой левой не посещенной точкой, округленной в большую сторону (т.е. нижней границей стоимостивсе еще впереди).Это алгоритм A *, поэтому вы можете остановить поиск, как только возникнет ситуация, когда все точки были охвачены (посещены).

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