Сопоставление между двумя группами точек в 3D-пространстве в R

#r #nearest-neighbor

#r #ближайший сосед

Вопрос:

У меня есть несортированная группа из N синих точек и M красных точек в 3D-пространстве, где M <= N (каждая точка представлена координатами X, Y, Z). Существует ли в R «готовый» алгоритм, который может найти для каждой красной точки ближайшую синюю точку? Алгоритм должен минимизировать сумму квадратов евклидовых расстояний между M подобранными парами, при условии ограничения того, что отображение является взаимно однозначным, что означает, что каждая синяя точка сопоставляется не более чем с одной красной точкой. Обратите внимание, что, поскольку M<= N, будут некоторые синие точки без совпадений.

1. можете ли вы добавить некоторые тестовые данные.

2. Если вы «находите для каждой красной точки ближайшую синюю точку», то некоторая синяя точка может быть присоединена к нескольким красным точкам. Это то, что вы хотите?

3. Посмотрите на сопоставление двудольных графов

4. @user31264 — обратите внимание, что сопоставление должно быть один к одному, что означает, что каждая синяя точка может быть присоединена только к одной красной точке или вообще не иметь красной точки (поскольку красных точек меньше, чем синих точек)

Ответ №1:

Кажется, то, что вам нужно, близко к задаче назначения, решаемой венгерским алгоритмом. Вы должны (1) переформулировать это как проблему назначения и (2) проверить, реализовано ли это в R (google для задачи назначения R или венгерского алгоритма R и т. Д.).