Перераспределить точки между списками в Python по условию
Имеется список со списками (больше двух), в которых даны координаты точек:
Задача заключается в том, чтобы сравнить координаты точек одного списка с координатами точек другого списка, и, если хотя бы одна точка одного из списков будет находиться на расстоянии ближе чем 0.1 по отношению к точке другого списка, то эту точку и все другие точки этого списка, нужно перенести в список точки, с которой происходило сравнение.
Например:
[[(0.8, 0.7), (0.1, 0.1)], [(0.2, 0.9), (0.8, 0.1)], [(0.1, 0.1), (0.5, 0.5)]]
В первом и последнем списке есть точки с одинаковыми координатами, значит они будут удовлетворять условию, тогда результатом проверки будет список следующего вида:
[[(0.8, 0.7), (0.1, 0.1), (0.1, 0.1), (0.5, 0.5)], [(0.2, 0.9), (0.8, 0.1)]]
Ответы (1 шт):
Для уменьшения количества проверок нужно создать какую-либо геометрическую структуру данных. При более-менее равномерном или случайном распределении точек в пространстве неплохо работает простое разделение пространства на кубики, каждая точка относится к одному кубику соответственно её координатам (p(x,y,z)=>cube[x/L, y/L, z/L]). Проверяются точки в одном кубике и в соседних восьми (размер куба должен быть больше допуска). При удачном выборе размера куба) количество проверок сокращается в среднем в m^2/9 раз, где m - количество кубов по одной координате.
Если распределение плохое, может понадобиться строить что-то вроде kd-tree - в этом случае для каждой точки быстро выполняется запрос о ближайшей. Вероятно, для Python есть готовые реализации.
При обнаружении близости точек из разных списков списки объединяются , вначале виртуально, с помощью метода Union-Find, по окончанию работы списки с общим представителем сливаются физически.