Перераспределить точки между списками в Python по условию

Рейтинг: 0Ответов: 1Опубликовано: 01.02.2023

Имеется список со списками (больше двух), в которых даны координаты точек:

Задача заключается в том, чтобы сравнить координаты точек одного списка с координатами точек другого списка, и, если хотя бы одна точка одного из списков будет находиться на расстоянии ближе чем 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)]]

python list итераторы
Источник: Stack Overflow на русском

Ответы

▲ 0

Для уменьшения количества проверок нужно создать какую-либо геометрическую структуру данных. При более-менее равномерном или случайном распределении точек в пространстве неплохо работает простое разделение пространства на кубики, каждая точка относится к одному кубику соответственно её координатам (p(x,y,z)=>cube[x/L, y/L, z/L]). Проверяются точки в одном кубике и в соседних восьми (размер куба должен быть больше допуска). При удачном выборе размера куба) количество проверок сокращается в среднем в m^2/9 раз, где m - количество кубов по одной координате.

Если распределение плохое, может понадобиться строить что-то вроде kd-tree - в этом случае для каждой точки быстро выполняется запрос о ближайшей. Вероятно, для Python есть готовые реализации.

При обнаружении близости точек из разных списков списки объединяются , вначале виртуально, с помощью метода Union-Find, по окончанию работы списки с общим представителем сливаются физически.