Алгоритм определения клеток сетки, закрытой какой-либо областью.

[Sneg]

Добрый день, столкнулся со следущей проблемой.
Есть игровое поле IGameField, которое состоит из клеток (IGameCell).
IGameField умеет возвращать клетку по опреденным координатам:

getCellByPosition(x:Number,y:Number):IGameCell;

Имеется класс для выделения области SelectionArea, который умеет возвращать выделенную область

getSelectionArea():Rectangle;

Вопрос: каким наиболее правильным алогритмом можно реализовать метод который возвращает выделенные клетки из этой области

getSelectionCells(rectangle:Rectangle):Array;

Пока на ум приходит только определять клетки на вершинах выделенной области и как-то хитро бегать циклами по ним (как именно пока не придумал). Кто нибудь сталкивался с подобной проблемой? Что можно почитать по этой теме?

Спасибо за ответы.

[scourge ' kangaroo]

если я правильно понял, что требуется...
В каждую выделенную клетку пишешь, например, selectedFlag = true
Потом циклом проверяешь значение selectedFlag начиная с правой верхней, заканчивая левой нижней...

[Sneg]

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

[FourSide]

Как нить при выделении области загонять клетки в отдельный массив...

[miramax]

Топорный метод : hitTest (коряво , не оптимально - за то просто)
Математический метод : если выделенные клетки всегда будут образовывать прямоугольник, то нужно найти две клетки (верхнюю левую, и нижную правую)

обсцисс верхней левой = Math.floor((прямоугольник.x)/(шаг сетки));
ординат верхней левой = Math.floor((прямоугольник.y)/(шаг сетки));
обсцисс нижней правой = Math.ceil((прямоугольник.x+прямоугольник.width)/(шаг сетки));
ординат нижней правой = Math.ceil((прямоугольник.y+прямоугольник.height)/(шаг сетки));

//шаг сетки=разность координат двух соседних клеток
//остально думаю понятно.
ЗЫ. а функция ближайшего целого числа больше данного - не помню как точно называется. Может и не ceil()

[Sneg]

2FourSide: Как-нибудь - это хороший совет: сейчас попробую.
2Miramax: Самое интересно, что использовать HitTest нельзя - http://flasher.ru/forum/showthread.php?t=84341
То что ты придложила, я описал в своем первом сообщении - но нет клеток как физических объектов типа MovieClip - это данные. Сейчас копаюсь в этом способ, не так очевидно как кажется - это первое что пришло в голову, возможно есть лучше и правильнее. особенно наверника будут бешенные тормоза кода придется пересчитывать при onMouseMove. Спасибо за ответ.
p.s. Math.ceil() - округляет в большую сторону , Math.floor() - округляет в меньшую сторону.
p.s. Как посчитать такими методом все клетки которые войдут в область. Мне не так очевидно, как тебе, имеем к примеру:

var cellWidth:Number; // длина клетки
var cellHeight:Number; // ширина клетки
var rectangleCell1:IGameCell; // клетка левого верхнего угла выделения 
var rectangleCell2:IGameCell; // клетка правого верхнего угла выделения 
var rectangleCell3:IGameCell; // клетка правого нижнего угла выделения  
var rectangleCell4:IGameCell; // клетка левого нижнего угла выделения

Если тебя не затруднит - как им образом представляешь дальнейший цикл занесения в массив клеток в этом прямоугольнике? Как поределить вершины выделения - просто, в первом сообщение еще опсал что такой метод уже реализовал getCellByPosition(x:Number,y:Number):IGameCell;

[miramax]

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

2FourSide: Как-нибудь - это хороший совет: сейчас попробую.
2Miramax: Самое интересно, что использовать HitTest нельзя - http://flasher.ru/forum/showthread.php?t=84341
То что ты придложила, я описал в своем первом сообщении - но нет клеток как физических объектов типа MovieClip - это данные. Сейчас копаюсь в этом способ, не так очевидно как кажется - это первое что пришло в голову, возможно есть лучше и правильнее. особенно наверника будут бешенные тормоза кода придется пересчитывать при onMouseMove. Спасибо за ответ.

Во-первых: я - МАЛЬЧИК!
Во-вторых: хит-тест работать будет, только после аттача мувиклипов и после обновления экрана (если shape=true то это зависит так же от fps. onEnterFrame поможет в этом случае)
В-тертьих: понятно что тебе нужно. Тогда дальше я бы сделал так

//mas[y][x]
//X1, Y1,
//X2, Y2
ar = []
tempY = Y1;
while(tempY<=Y2){
ar = ar.concat(mas[tempY].splice(X1, X2))
tempY+=1;
}

не пробовал компилить этот код. Но общая идея такова.
В каждой строчке (начиная с У1 , заканчивая У2) выбираем все клетки от Х1 до Х2 и записываем в массив

[Sneg]

За девочку - прости :-) Я ссылку дал на тот не просто так - если прочтешь, то поймешь почему нельзя использовать MovieClip'ы для клеток вообще, повторюсь, этот класс не имеет визуального представления и не будет иметь. Код какой-то совершенно жуткий :-) Думаю ты не стал въезжать в проблему и смотреть то, что я писал выше. Но все равно спасибо за участие: IGameCell имеет метод, который возвращает только номер ячейки

getPosition():Number;

[etc]

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

За девочку - прости :-)

Вот к чему приводят женские аватары =)

[Sneg]

Ага :-) Посоветуй что-нибудь, под конец дня голова уже трещит - а как нужно алгортим не работает.