Алгоритм определения пустых квадратов?

Question

[Дмитрий Калинин]

Добрый день.
Дана матрица квадратов. Общее поле условно от 0 до 100 ед. Каждый закрашенный квадрат представляет собой объект с целочисленными координатами (x1, y1, width, height). И есть пустые квадраты (белый цвет), которые никак не заданы. Какой наиболее оптимальный способ определения пустых квадратов и формирования из них таких же объектов?
Построчное сканирование всего поля с шагом 1? (на каждом шаге перебор всех объектов? ресурсоемко врое бы) Вычитание из матрицы существующих объектов и потом создание из оставшихся координат новых объектов?(тут пока не совсем понимаю как это реализовать. Создать массив 100 на 100 и вычитать координаты? а потом формировать объекты методом ближайших?).
Вродебы кажется несложная задача, но что то в ступор вошел(. Может есть простое решение, но я его не вижу. Помогите советом.

Answer 1

[Stalker_RED]

Например так:
Создаем "карту" - массив 100х100.
Проходим по списку ваших прямоугольников (не называйте их квадратами, плз).
Заносим в карту айди квадрата или цвет, или даже просто 1 для заполненных и 0 для пустых.

Когда нужно добавить новый прямоугольник перебираем "карту" пока не найдется 0, определяем сколько свободно по ширине и высоте, добавляем новый прямоугольник, и не забываем отметить его на "карте".

Comments

[Дмитрий Калинин]

ну на самом деле тут "квадрат" в значении территории, а не равнозначности сторон. то что вы предлагаете это то о чем в думаю в первую очередь, но есть вопросы.
Ок, вначале мы перебираем каждый элемент. На каждой итерации мы создаем 2 цикла и построчно проходим по элементу и отмечаем Х и У? (первый цикл - у+1 и до у2, а второй вложенный от х1 до х2).
Допустим отметили. А теперь что значит "определяем сколько свободно по ширине и высоте"?
Нам надо создать элемент, мы запускаем цикл построчно, проходимся по У и упираемся в Х, где есть 0. А в данном случае (картинка) мы должны просто поставить проверки что текущий У не равен (У-1) (ну или Х не равен Х-1, в зависимости почем изначально перебираем) и тогда это будет означать границу объекта?
Примерно из этой логики я и исходил, но ведь получится реально ресурсоемко, как по мне. Или это оптимальный вариант? Или рассуждениях выше я где то что то не правильно понял и есть способ делать эти вычисления как то быстрее?

upd. чтоб вы меня правильно поняли, у нас должны быть только квадраты/прямоугольники, такого L образного ничего быть не должно, т.е. это 2 отдельных прямоугольника должны тогда быть.

[Stalker_RED]

Дмитрий Калинин, преждевременная оптимизация - зло.

Задача в таком виде слишком абстрактная, и совершенно непонятно как ее оптимизировать. Можно создать какие-то индексы, но если у вас возможны мелкие цветные "квадраты" размером 1х1, то эти индексы только будут мешать. Если заранее известен какой-то минимальный размер квадратов, то можно перебирать не по одному пикселю за раз, а через один, что ускорит обход"карты". в 4 раза. Если через два - в 9 раз.