|
|
|||||
Быстрый поиск соседей
Возник такой вопрос. Есть n частиц(много). Вероятность столкновения велика. Есть теоритически бесграничное поле. Есть статья, где достаточно хорошо описан метод для поиска соседей(там всё поле разбивается на ячейки нужного нам размера, ну и всё такое. Хз как называется этот метод).
Всё бы хорошо, но все моменты, где применяется запись и поиск в объекте разных значений очень тормозит. Есть ли идеи, как сделать хранение бесконечного количества ячеек не в переменной Object, а в другом быстром виде, чтобы избавиться от всех длинных циклов? Вот примерно мой код: 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 раз .... |
|
|||||
Вход:
Массив точек pt[] длины ptCount. Точки имеют координаты - свойства xx,yy Выход: Для каждой точки pt[i] массив индексов соседей i-ой точки с индексами < i. Под соседом понимается такая точка, для которой расстояние от неё до i-ой точки < R. Просто, стандартный поиск соседей, особого смысла метод писать нету. |
|
|||||
блогер
Регистрация: May 2008
Адрес: (0, 10, 185) в локальной системе
Сообщений: 721
Записей в блоге: 6
|
Лучше конечно упростить вначале задачу настолько, насколько возможно — например, сделать поле не бесконечного размера а конечного. Тогда и таблицу можно будет задать двумерным массивом.
Ну раз вы хотите бесконечное поле, то придется извращаться. Один из вариантов, создать класс разряженной таблицы и хранить элементы в двунаправленных списках. Также очень хорошее упрощение это разделение статичной и динамичной геометрии — статичные точки можно предрасчитать и заранее записать в таблицу. |
|
|||||
хм.. про разреженные матрицы и не подумал) спасибо) статичных точек нет. Моделирую жидкость.
|
Часовой пояс GMT +4, время: 22:37. |
|
« Предыдущая тема | Следующая тема » |
Теги |
object , Столкновения , частицы |
Опции темы | |
Опции просмотра | |
|
|