Проверка принадлежности окружности группе квадратов.
 

Задача на стороне модели. Есть группа квадратов со стороной 1, есть окружность представленная координатами и радиусом, который может быть меньше или больше единицы. Нужно проверить, находится ли данная окружность внутри квадратов.
Квадраты представлены двумерным массивом, ячейки которого = null – нет квадрата, не null – есть квадрат.
Точнее так:
Есть одномерный array и пара переменных width, height. Проверка на существование квадрата для точки x,y: array[x+y*width]!=null.
Естественно можно построить какие то промежуточные данные по поверхности квадратов.
Задача происходит часто, по сути по событию mouseMove, в определенном режиме(создание/перемещение объектов).
Подскажите решение?

А можешь нарисовать "окружность внутри квадратов", а то я шота нифига не могу визуализировать задачу.

http://cs11491.vkontakte.ru/u1006614...x_49f4be2f.jpg
Серые квадраты - есть квадрат, белые квадраты - нет квадрата.

Добавлено через 6 минут
На основе квадратов нельзя построить один выпуклый многоугольник... К тому что они не выпуклые, еще добавляется то, что внутри могут быть пустые квадраты, и это не обязательно одна группа квадратов, т.е. внутри матрицы может быть несколько групп квадратов... в общем жесть :(
Например так:
http://cs11491.vkontakte.ru/u1006614...x_3aa35e98.jpg

Добавлено через 11 минут
P.S. Картинки выложил вконтакте... так что что бы отображались надо быть залогиненым... Как выкладывать файлы на форуме, не в курсе :)

Сори, сейчас с реализацией не помогу, но я бы действовал по следующему алгоритму.
Пляшем не от квадратов, а от окружности. Первым шагом находим все квадраты, которые она пересекает. Вторым шагом проверяем найденную группу квадратов на "серость" )
Нам нужно определиться, что координатой квадрата мы будем считать координату его верхнего левого угла. Таким образом для первого шага находим все квадраты, которые удовлетворяют условиям:


P.S.
код написан прямо тут есличё )

Ага, спасибо. Неплохой вариант.

Зая, не позорь семью, приду все напишу )))

Сейчас понял, что можно еще проще — алгоритм будет быстрее, если просто тупо найти координаты самого верхнего левого квадрата, пересекающего окр. и самого правого нижнего. В этих пределах пройтись вложенными циклами и сделать только часть с allGrayFlag.

Добавлено через 3 минуты
а координаты собственно такие:

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

Zebestov ксати вариант не очень хорош его сложность n^2 где n размерность сетки, для алгоритма который выполняется несколько раз в секуду это многовато, нужно построить промежуточные данные о "пограничных с серыми клетках" и отслеживать пересечение с ними - тогда алгоритм станет линейным

А на сколько больше может быть диаметр кругов чем сторона квадрата? Т.е. может быть такая ситуация, что круг полностью "закрывает" незакрашеный квадрат, и должна ли такая ситуация "дисквалифицировать" круг?

crazylena, если ты о первом, то его оптимальность уже подверглась критике самого автора ;)
А вот с "поправкой" алгоритм (именно алгоритм) претендует на звание "оптимальный" — быстрее не будет.

Добавлено через 3 минуты
wvxvw круг с диаметром больше 1 не может просто полностью закрыть незакрашенный квадрат — он автоматически зацепит соседние 3-8 квадратов.