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

Question

Учитывая двумерное пространство, ограниченное (белым) прямоугольником и набором (черных) прямоугольников, занимающих это пространство, я ищу способ как-то индексировать пустой (белый). Для этого я хотел бы создать набор (белых) прямоугольников, так что для любой данной точки в пространстве (точка, не принадлежащая ни одному «черному» прямоугольнику) в этом результирующем наборе белых прямоугольников существует максимальный пустой прямоугольник.

Благодаря

Answer 1

http://rd.springer.com/chapter/10.1007%2F3-540-53487-3_50 Настоящий документ описывает эффективный подход к моей проблеме.

С уважением, Damjan

Answer 2

Вы в сетке (т.е. изображение) или в непрерывном 2D пространстве? Мой ответ для случая, когда каждая точка имеет целочисленные координаты. В другом случае вы можете получить приближение с моим ответом.

Если я правильно понимаю ваш вопрос, вам нужно две вещи:

1. список всех крупнейших пустых прямоугольников (т.е. прямоугольник заполняется только белыми точками, которым не может быть продлен в любом направлении, не включая черная точка) (также называемая «максимальные пустые прямоугольники», или MER в литературе).
2. 2D-массив указателей прямоугольника, который указывает для каждой точки самый большой пустой прямоугольник, включающий эту точку. Другая структура данных также возможна, но я не буду описывать их, так как выбор зависит в основном от требований вашего целевого приложения.

Для того чтобы вычислить этот список, вы можете использовать алгоритм O (N), где N - количество пикселей в черно-белом изображении. Вы можете найти документ, описывающий такой алгоритм, в http://www.ulg.ac.be/telecom/rectangles, с некоторым (не оптимизированным) исходным кодом на C++. На практике это очень быстро.

Чтобы вычислить 2D-массив пинтов, вам необходимо пройти список всех самых больших пустых прямоугольников, а для каждого - обновить указатель (если необходимо) для всех включенных пикселей. Поскольку существует не более N наибольших пустых прямоугольников (для prrof, см. Бумагу, связанную с http://www.ulg.ac.be/telecom/rectangles), и каждый прямоугольник включает в себя большинство N пикселей, этот шаг в худшем случае O (N^2). Я не знаю, можно ли снизить стоимость этого шага.