Алгоритм для размещения сетки поверх неупорядоченного набора точек
Учитывая большой набор (от десятков тысяч до миллионов) неупорядоченных точек, представленных в виде трехмерных декартовых векторов, какой хороший алгоритм для создания регулярной квадратной сетки (с определяемым пользователем интервалом) что включает в себя все точки? Некоторые ограничения:
- Сетка должна быть квадратной и регулярной
- Мне нужно иметь возможность регулировать интервал сетки (длину стороны одного из квадратов), в идеале с помощью одной переменной
- Я хочу сетка минимального размера, т.е. каждый «блок» в сетке должен содержать по крайней мере одну из неупорядоченных точек, и каждая неупорядоченная точка должна быть заключена в «блок»
- . Возвращаемое значение алгоритма должно быть списком координаты точек сетки
Для иллюстрации в 2D, учитывая этот набор точек:
для некоторого шага сетки X, одним из возможных возвращаемых значений алгоритма будут координаты этих красных точек (пунктирные линии только для иллюстративных целей ):
и для шага сетки X / 2 одним из возможных возвращаемых значений алгоритма будут координаты этих красных точек (пунктирные линии только для иллюстрации):
Для всех, кому интересно, неупорядоченные точки, которые я Я работаю с координатами атомов больших белковых молекул, вроде того, что вы можете получить из a. pdb файл.
Python предпочтительнее для решений, хотя псевдокод тоже хорош.
РЕДАКТИРОВАТЬ: Я думаю, что мое первое описание того, что мне было нужно, было, возможно, немного нечетким, поэтому я добавил некоторые ограничения и изображения, чтобы прояснить ситуацию.