k означает — c ++ Нахождение ближайших четырех из набора точек
У меня есть набор точек, каждая с координатами X и Y. Я хотел бы найти 4 из этих точек, которые находятся ближе всего друг к другу (если бы на графике все точки были в разных местах, но 4 из этих точек всегда ближе друг к другу, и я хочу иметь возможность определить, какая из указывает эти четыре программно). Как мне это сделать? Мне сказали, что это связано с k-средних или ближайшими соседями, но пока из результатов поиска я не вижу, как я могу заставить его работать для моего случая, так как я нахожу близость точек по отношению друг к другу, а не к какой-то фиксированной точке. Будем весьма благодарны за любые предложения относительно того, какую тему / алгоритм следует изучить или какие фрагменты кода.
Я думал, что изображение точной проблемы может помочь. Таким образом, эти 8 точек содержатся в векторе, и я хотел бы иметь возможность определить, какие из четырех сгруппированы справа.
Заранее спасибо.
Решение
Метод грубой силы должен был бы выбрать каждый возможный выбор четырех точек (каждая перестановка) и вычислить, например:
1) площадь, окруженная точками,
2) периметр выпуклой оболочки точек,
3) …
и вы найдете свои четыре балла, получив минимум значений, рассчитанных как 1), 2) или 3).
Другие решения
Постройте граф Триангуляции Делоне с сложностью nlog (n), для перехода к четырем кратчайшим из них потребуется менее 2n ребер.
ты можешь попробовать poly2tri.
Вы хотели бы пройтись по краям следующим образом: выберите ребро, пройдите три раза к самому короткому соединенному ребру и суммируйте длины ребер. сохраните вершины и сумму длин минимальной суммы ребер, встреченной до сих пор, и исчерпайте все возможные кратчайшие комбинации соседних длин.