Эффективный алгоритм, чтобы вернуть все прямоугольники на поверхности

Question

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

У меня уже есть функция, которая возвращает прямоугольник для заданной координаты, если он существует

GetRectangle( int row, int col )

Вот как я бы назвал полученный код.

foreach( var rect in GetRectangles( row, col, rowCount, colCount ) ) {
   //..  my processing code here
}

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

Вам известен такой алгоритм?

ОБНОВЛЕНИЕ: Поверхность не обязательно покрыта прямоугольниками, но это может быть для некоторых особых случаев.Итак, функция GetRectangle( int row, int col ) может возвращать ноль.

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

Спасибо

Answer 1

Для получения наилучших результатов организуйте свою коллекцию прямоугольников в пространственную структуру поиска .В этом случае звучит так, как будто R-дерево будет хорошей ставкой.Но если вы не можете этого сделать, и GetRectangle - это все, что у вас есть, то вот что я буду делать:

План состоит в том, чтобы вести список целых чисел x _j для 0 ≤ j <<code>rowCount, где x _j это самая левая точка в строке j , для которой я еще не нашел прямоугольник, закрывающий ее.

1. Начните с инициализации x _j : = 0 для всех j .

2. Если x _j = colCount для всех j , все готово.Стоп.

3. Пусть J = мин ( j | x _j = мин ( x _i )).Тогда x _J - самая верхняя левая точка, которую я еще не нашел прямоугольника, который ее покрывает.

4. Звоните GetRectangle ( x _J , J ).Если это не возвращает прямоугольник, то точка не раскрыта.Установите x _J : = x _J + 1 и перейдите к шагу 2.

5. В противном случае у нас есть прямоугольник с верхним левым углом в ( x _J , J).Назовите его ширину ш и высоту ч .Для J ≤ j <<em> J + ч , установите x _j : = x _j + w .Переходите к шагу 2.

Вот пример выполнения этого алгоритма.Список x _j показан номерами слева, а крайний левый край выделен жирным шрифтом.Оранжевый прямоугольник - это тот, который обнаружен на этом шаге алгоритма.

Для эффективного обнаружения минимума на шаге 3 может потребоваться сохранить список x _j в куче .