Comments 1
«Не нужно перебирать список для каждого из его элементов. Можно перебрать его один раз, сразу помещая элемент (точку) в определенный список (кластер)»
Для корректной самогруппировки (то, что вы называете кластер, другие называют группа), когда корректные условия группировки непонятны, необходимо N + 1 (где N -- целое число выше нуля, т.е., натуральное) циклов сортировки (группировки), где при первой сортировке (по несколько произвольному значению, основанному на значениях и числе общей группы) создаются отдельные группы (кластеры), по которым уточняется параметр группировки, сортировка повторяется по новому параметру. Когда после двух последовательных сортировок группы остаются одними и теми же -- процесс самогруппировки останавливается.
Я создал на Python простой, но универсальный алгоритм линейной самогруппировки (по одному значению) и двумерной самогруппировки по двум независимым параметрам. У вас двумерная самогруппировки по двум зависимым параметрам (координатам), но и ее достаточно просто реализовать, когда каждый объект будет в одном из кластеров. Хотя, когда мне для одной софтинке понадобилось, я успешно использовал двумерную самогруппировку по двум независимым параметрам для работы с декартовы пространством. Ну, а дальше по группам можно уже строить и графы.
Уроки компьютерного зрения на Python + OpenCV с самых азов. Часть 5