Хорошо, поскольку вы не ответили на мой второй комментарий, я пойду с ответом.Ваш вопрос был "Есть ли более разумный подход, который я использую?"и ответ «Да», потому что ваш код не выполняет задачу, которую он должен делать.
Вы хотите объединить элементы, которые попадают в квадрат со стороны 1. Тогда эти точки:
matched_points.push_back(std::make_pair(100, cv::Point2d(0.0, 0.0 )));
matched_points.push_back(std::make_pair(101, cv::Point2d(0.0, 0.9 )));
matched_points.push_back(std::make_pair(102, cv::Point2d(0.0, 1.8 )));
matched_points.push_back(std::make_pair(103, cv::Point2d(0.0, 2.7 )));
matched_points.push_back(std::make_pair(104, cv::Point2d(0.0, 3.6 )));
matched_points.push_back(std::make_pair(105, cv::Point2d(0.0, 4.5 )));
matched_points.push_back(std::make_pair(106, cv::Point2d(0.0, 5.4 )));
matched_points.push_back(std::make_pair(200, cv::Point2d(0.0, 6.3)));
matched_points.push_back(std::make_pair(201, cv::Point2d(0.0, 7.2)));
matched_points.push_back(std::make_pair(202, cv::Point2d(0.0, 8.1)));
matched_points.push_back(std::make_pair(203, cv::Point2d(0.0, 9.0)));
matched_points.push_back(std::make_pair(204, cv::Point2d(0.0, 9.9)));
matched_points.push_back(std::make_pair(205, cv::Point2d(0.0, 10.8)));
matched_points.push_back(std::make_pair(206, cv::Point2d(0.0, 11.6)));
должны все попасть в один кластер.Учитывая ваш вывод, это не так.
Так что проблема здесь в том, что вы не можете повторно соединять наборы точек вместе.Это очень известная проблема, называемая структура данных с несвязным множеством , и фактически она используется для поиска связанных компонентов графа.
В вашем случае вы должны использовать первую часть вашего кода для создания граничной матрицы графа, а затем найти его связанные компоненты с помощью алгоритма union-find.
Реализация Union-Find
Здесь вы можете найти пример реализации структуры данных Union-Find, основанной на индексах, которые сопоставляются с точками в вашем векторе.Не такой умный, но он должен работать.
// Union-find (UF)
struct UF {
std::vector<int> P_;
UF(size_t size) : P_(size) {
iota(begin(P_), end(P_), 0);
}
int operator[](int i) {
return P_[i];
}
void Merge(int i, int j) {
// FindRoot(i)
while (P_[i] < i) {
i = P_[i];
}
// FindRoot(j)
while (P_[j] < j) {
j = P_[j];
}
if (i < j)
P_[j] = i;
else
P_[i] = j;
}
int Flatten() {
int k = 0;
int size = P_.size();
for (int i = 0; i < size; ++i) {
if (P_[i] < i) {
P_[i] = P_[P_[i]];
}
else {
P_[i] = k;
k = k + 1;
}
}
return k;
}
};
Поиск подключенных компонентов
Хитрость заключается в построении матрицы смежности (кто с кем связан) и при этом, если два элементасвязаны слияния их наборов.Операция сглаживания просто перенумеровывает наборы от 0 до n-1, поэтому проще переназначить ваши элементы в их кластеры.
int main(int argc, char** argv)
{
using elem = std::pair<int, cv::Point2d>;
std::vector<elem> matched_points;
// fill the matched_points vector here
auto connected = [](const elem& a, const elem& b) {
return abs(a.second.x - b.second.x) < 1 && (abs(a.second.y - b.second.y)) < 1;
};
UF uf(matched_points.size());
for (size_t i = 0; i < matched_points.size() - 1; ++i) {
for (size_t j = i + 1; j < matched_points.size(); ++j) {
if (connected(matched_points[i], matched_points[j])) {
uf.Merge(i, j);
}
}
}
int ncc = uf.Flatten();
std::vector<std::vector<elem>> clusters(ncc);
for (size_t i = 0; i < matched_points.size(); ++i) {
clusters[uf[i]].push_back(matched_points[i]);
}
}
Вектор кластеров будет содержать векторы точек, соединенных вместе (в произвольном порядке).