История изменений

А как точки распределены? Если бол-мен равномерно, то вводите равномерную d-мерную сетку с шагом половина от расстояния отсечки, распределяете по ней точки, и дальше смотрите ячейки ближайшие к данной (это боян, см. слой Верле в молек. динамике).

Если точки распределены не равномерно, то некоторые ячейки этой сетки откажутся пустыми. Если таких ячеек много, получаем разреженный массив. Проще всего для хранения использовать std::map - в качестве ключа D целых чисел (индекс ячейки в D-мерном пр-ве), в качестве значения содержимое ячейки. Ключи сортируются сначала по одной координате, потом по другой и пр - в общем пишете структуру для ключа и определяете оператор < (я про С++, на других ЯП тоже как то так можно). При распределении частиц по ячейкам индекс ячейки находится сразу, если знать координаты нулевого узла и шаг сетки. По скорости поиска это то же самое что всякие деревья, только даже лучше - реализуется проще, а работать будет быстрее чем d-дерево;-)

А как точки распределены? Если бол-мен равномерно, то вводите равномерную d-мерную сетку с шагом половина от расстояния отсечки, распределяете по ней точки, и дальше смотрите ячейки ближайшие к данной (это боян, см. слой Верле в молек. динамике).

Если точки распределены не равномерно, то некоторые ячейки этой сетки откажутся пустыми. Если таких ячеек много, получаем разреженный массив. Проще всего для хранения использовать std::map - в качестве ключа D целых чисел (индекс ячейки в D-мерном пр-ве), в качестве значения содержимое ячейки. Ключи сортируются сначала по одной координате, потом по другой и пр - в общем пишете структуру для ключа и определяете оператор < (я про С++, на других ЯП тоже как то так можно). При распределении частиц по ячейкам индекс ячейки находится сразу, если знать координаты нулевого узла и шаг сетки. По скорости поиска это то же самое что всякие деревья, только даже лучше;-)