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

Добрый день, столкнулся со следущей проблемой.
Есть игровое поле IGameField, которое состоит из клеток (IGameCell).
IGameField умеет возвращать клетку по опреденным координатам:
Имеется класс для выделения области SelectionArea, который умеет возвращать выделенную область Вопрос: каким наиболее правильным алогритмом можно реализовать метод который возвращает выделенные клетки из этой области Пока на ум приходит только определять клетки на вершинах выделенной области и как-то хитро бегать циклами по ним (как именно пока не придумал). Кто нибудь сталкивался с подобной проблемой? Что можно почитать по этой теме?

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

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

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

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

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

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

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

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

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

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

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

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

Ширина и высота клетки фиксированы или нет?

Задаются перемеными в XML, полученного от сервера. После построения поля и инициализцации клеток, измениться не может. Т.е. фикисированные - все GameCell имеют одинаковые размеры:

Он уже ответил что ему известны координаты клеток. Т.е. два противоположных угла прямоугольника.
2Sneg
ну почему код не работает-то?
Вот у тебюя массив строк
mas= [1, 2, 3, 4, 5];
каждый элемент массива тоже массив, содержащий координаты х
например
mas[1] = [1, 2, 3, 4, 5];
Нам известна координаты верхней левой точки, и правой нижней (X1, Y1 и X2, Y2 соответсвенно)
тебе нужно из каждого массива mas[Y1], mas[Y1+1]...mas[Y2] вырезать елементы принадлежащие интервалу от X1 до X2 . Т.е
mas[Y1][X1]
mas[Y1][X1+1]
.....
mas[Y1][X2]
и добавить их в массив
Я думал ты сам сможешь всё дописать, ну так и быть приведу более полный вариант

Это подчёркивает мой эстетический вкус :mosking:
К тому же посты с приятными аватарами взор быстрее находит на странице и их внимательнее читают :D

2miramax: Откуда ты взял что у меня это двумерный массив? Я где-нибудь писал это? Вот тебе кусочек кода интефейса IGameField:
Игровое поле может только вернуть только клетку на определенной position, а positionесть порядковый номер клетки : от 1 до (длина поля в клетках)*(ширина поля в клетках).

сори, если не въехал в проблему, а чего по-простому нельзя напихать в массив этих клеток?

Здесь я вообще не вижу проблемы. Сработает обыкновенная арифметика вместе с методом массива push(); Лень пример приводить...

если у каждой клетки есть своя позиция x и y (я говорю не о пикселях, а о их порядковых номерах от верхнего левого углу)
просто на onPress засекаешь xy начальной клетки, и потом на onRelease смотришь xy конечной клетки, у тебя получается твой массив

не получается, в него попадут клетки за гранцей области..

То ли я не понимаю о чем речь, то ли вы мудрите. Можно еще раз описать проблему, но без затрагивания классов (они тут вроде бы не причем), то есть саму суть?

1. Он знает начальную и конечную координаты клеток
2. Ему нужно вернуть массив клеток входящ в прямоугольник, диоганаль которого проходит по этим клеткам.
3. Двумерного и вообще никакого массива у него нет.
Днём лень было писать:

Вот 12 клеток в сетке и я могу их разместить 6-ю разными способами (указал 4). Указывая одни и теже координаты (возможные конечно), я буду получать разные числа выделения.
[ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12]

[ 1][ 2][ 3][ 4][ 5][ 6]
[ 7][ 8][ 9][10][11][12]

[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]

[ 1][ 2][ 3]
[ 4][ 5][ 6]
[ 7][ 8][ 9]
[10][11][12]
...

Тьфу блин, заплёлся
W - Я имел ввиду количество клеток в ряду, строчке. А сколько всего клеток в сетке не важно и не нужно.

2iNils: Рассказываю, что имеется и что нужно получить ,как можно более понятно. Есть игровое поле с ячейками, произвольного размера. Все ячейки пронумерованы целыми числами от 1 до (размер поля в ячейках по горизонтали)*(размер поля в ячейках по вертикали). Именно так как в твоем примере про 12 клеток, все предложенные тобой варанты возможны. Мы знаем любые параметры поля: размер его ячеек, размер самого и т.п.
Имеется прямоугольная область (знаем все её параметры: координаты левого верхнего угла, длину и высоту).
Задача получить массив номеров ячеек, которое перекрывает эта область.

p.s. Все объекты это данные визуального представления они не имеют поэтому hitTest не подходит.

2maxmara: есть просто массив всех ячеек, кто тебе сказал что вообще никакого массива нет? Нет массива двумерного. Твой код забивает массив координатами (а речь идет о номерах ячейках) - если тебе, как ты говоришь "лень писать" - то не пиши вообще такого кода. Спасибо за помощь.

2silin: Спасибо, сейчас подумаю попробую.

Я бы сначала посмотрел что делает код maxmara, а делает он как раз то что нужно.

я слегка код переделал (не люблю я while)

Туплю уже страшно - пора домой, утром разберусь с кодом - спасибо всем за ответы.

Чуть-чуть подкоректировал код - все работает как нужно. Вот только на полях больше чем 100x100 при выделении большой области. Flash при таком алгоритме очень долго обрабатывает данные :-(

2miramax: твой код был абсолютно верным, но из-за стиля написания и "while" мой мозг категорически отказывался его понимать. Спасибо, прошу прощения за не дружелюбный тон.

2iNils: отдельная благодарность :-)

Чтобы не возникало проблем при построении тайлов надо иметь две координатных сетки:
1. Реальная
2. Тайловая
и метод перехода от одной к другой.
Допустим все тайла имеют атрибуты xx и yy , где xx - порядковый номер по иксу а yy порядковый номер по y. Имена тоже удобней строить из этой концепции например ["tile_"+xx+"_"+yy] будет легче обращятся на прямую.
Тогда если нам известен левый ферхний тайл выделения tile1 и нижний правй тайл выделения tile2 имеем простейшую систему перебора:

Конечно удобнее, но к сожалению интерфейс ячейки сетки и самой сетки не предоставляет такой возможности, поэтому приходится делать несколько иным способом.