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