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

[JackFromChaos]

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

[Zebestov]

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

[JackFromChaos]

Серые квадраты - есть квадрат, белые квадраты - нет квадрата.

Добавлено через 6 минут
На основе квадратов нельзя построить один выпуклый многоугольник... К тому что они не выпуклые, еще добавляется то, что внутри могут быть пустые квадраты, и это не обязательно одна группа квадратов, т.е. внутри матрицы может быть несколько групп квадратов... в общем жесть
Например так:


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

[Zebestov]

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

if ((squareX >= circleX - R) && ((squareX + 1) < circleX + R) && (squareY >= circleY - R) && ((squareY + 1) < circleY + R)) {
    allGrayFlag = allGrayFlag && array[squareX + squareY * width];
    if (!allGrayFlag) break;
}
if (allGrayFlag) {
    trace("Принадлежит!");
} else {
    trace("Облом.");
}

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

[JackFromChaos]

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

[crazylena]

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

[Zebestov]

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

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

topLeftX = Math.floor(circleX - R);
topLeftY = Math.floor(circleY - R);
bottomRightX = Math.floor(circleX + R);
bottomRightY = Math.floor(circleY + R);

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

[crazylena]

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

[wvxvw]

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

[Zebestov]

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

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