Форум Flasher.ru - Быстрый поиск соседей

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Быстрый поиск соседей (http://www.flasher.ru/forum/showthread.php?t=126737)

Быстрый поиск соседей

Возник такой вопрос. Есть n частиц(много:)). Вероятность столкновения велика. Есть теоритически бесграничное поле. Есть статья, где достаточно хорошо описан метод для поиска соседей(там всё поле разбивается на ячейки нужного нам размера, ну и всё такое. Хз как называется этот метод).

Всё бы хорошо, но все моменты, где применяется запись и поиск в объекте разных значений очень тормозит. Есть ли идеи, как сделать хранение бесконечного количества ячеек не в переменной Object, а в другом быстром виде, чтобы избавиться от всех длинных циклов?

Вот примерно мой код:

Код AS3:

                        all_sectors=new Object();

 

                        for (i=0; i<ptCount; i++)

                        {

                                p=pt[i];

                                for (dx=-1; dx<=1; dx+=1)

                                      for (dy=-1; dy<=1; dy+=1)

                                        { 

                                                x1 = p.xx*rinv - dx;     //rinv=1/радиус частицы

                                                y1 = p.yy*rinv - dy;

                                                s = Math.floor(x1)+"_"+Math.floor(y1);

                                                if(! all_sectors[s])

                                                        all_sectors[s] = new Object(); 

                                                all_sectors[s][i]=p;

                                        }

                                 ... //Ещё кое-какой код

                         }

 

 

                        for(s in all_sectors)

                        {

                                sector=all_sectors[s];

                                for(su in sector)

                                {

                                        i=parseInt(su);

                                        for(sv in sector)

                                        {

                                                j=parseInt(sv);

                                                if(i>j)

                                                {

                                                 //До сюда при тестировании выполнение дошло примерно 5000 раз

                                                 ....

Спасибо

Какой ужас :eek: Напишите метод целиком. И опишите что на входе, а что должно быть на выходе.

Вход:
Массив точек pt[] длины ptCount.
Точки имеют координаты - свойства xx,yy
Выход:
Для каждой точки pt[i] массив индексов соседей i-ой точки с индексами < i.
Под соседом понимается такая точка, для которой расстояние от неё до i-ой точки < R.

Просто, стандартный поиск соседей, особого смысла метод писать нету.

Лучше конечно упростить вначале задачу настолько, насколько возможно — например, сделать поле не бесконечного размера а конечного. Тогда и таблицу можно будет задать двумерным массивом.
Ну раз вы хотите бесконечное поле, то придется извращаться. Один из вариантов, создать класс разряженной таблицы и хранить элементы в двунаправленных списках.
Также очень хорошее упрощение это разделение статичной и динамичной геометрии — статичные точки можно предрасчитать и заранее записать в таблицу.

хм.. про разреженные матрицы и не подумал) спасибо) статичных точек нет. Моделирую жидкость.