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

[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);

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

[JackFromChaos]

Сообщение от Zebestov

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

Ну собственно я сразу о чем то таком подумал, правда не успел сформулировать
Вариант по моему нормальный, вряд ли его можно принципиально улучшить...
Зато здесь можно легко и просто все проверять, и не только на Null, а скажем на тип квадрата... если поверхность может быть разного типа, например вода... На которой тоже нельзя строить... Или если сооружение может строится только на поверхностях какого то определенного типа. Правда пока так задача не стоит, но потенциально можно применять

Добавлено через 15 минут

Сообщение от wvxvw

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

Диаметр круга может быть любого размера...

Добавлено через 28 минут
Кстати, как мне кажется, вполне доказательство, что красиво могут выгладить не только изометрические и хексагональные тайлы

[crazylena]

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

[wvxvw]

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