I am comparing coordinates of points. When the coordinates are similar, the respecting Point IDs (e.g. 102 and 202) are saved in a multimap structure.
If another Point has similar coordinates (e.g. ID 302) I want to form a Point ID triple (quadruple...) and so on.
The problem I have, is that ID 202 and ID 302 will also form a pair that is already in my triple. So I have to delete that pair. I only want to keep the largest sequence.
Right now I am using a combination of vectors, multimaps and multimap iterators and it seems quite bulky for such a "simple" operation.
Is there are smarter approach that the one I am using?
Here is the working code:
#include <iostream>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/core/core.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <map>
int main(int argc, char** argv)
{
std::vector<std::pair<int, cv::Point2d>> matched_points;
matched_points.push_back(std::make_pair(100, cv::Point2d(260.103, 1335.96)));
matched_points.push_back(std::make_pair(101, cv::Point2d(238.017, 1313.15)));
matched_points.push_back(std::make_pair(102, cv::Point2d(112.052, 1338)));
matched_points.push_back(std::make_pair(103, cv::Point2d(326.396, 1301.1)));
matched_points.push_back(std::make_pair(104, cv::Point2d(328.225, 1302.48)));
matched_points.push_back(std::make_pair(105, cv::Point2d(259.943, 1386.1)));
matched_points.push_back(std::make_pair(106, cv::Point2d(1033.7, 1197.04)));
matched_points.push_back(std::make_pair(200, cv::Point2d(1430.65, 1304.55)));
matched_points.push_back(std::make_pair(201, cv::Point2d(1185.66, 1032.1)));
matched_points.push_back(std::make_pair(202, cv::Point2d(112.052, 1338)));
matched_points.push_back(std::make_pair(203, cv::Point2d(326.396, 1301.1)));
matched_points.push_back(std::make_pair(204, cv::Point2d(328.225, 1302.48)));
matched_points.push_back(std::make_pair(205, cv::Point2d(259.943, 1386.1)));
matched_points.push_back(std::make_pair(206, cv::Point2d(1033.7, 1197.04)));
matched_points.push_back(std::make_pair(300, cv::Point2d(1430.65, 1304.55)));
matched_points.push_back(std::make_pair(301, cv::Point2d(1185.66, 1032.1)));
matched_points.push_back(std::make_pair(302, cv::Point2d(112.052, 1338)));
matched_points.push_back(std::make_pair(303, cv::Point2d(326.396, 1301.1)));
matched_points.push_back(std::make_pair(304, cv::Point2d(328.225, 1302.48)));
matched_points.push_back(std::make_pair(305, cv::Point2d(259.943, 1386.1)));
matched_points.push_back(std::make_pair(306, cv::Point2d(1033.7, 1197.04)));
// Possibly adding more points (400s, 500s ...)
// Save integer numbers of matching points
std::multimap<int, int> matches_map;
for (size_t i = 0; i < matched_points.size(); ++i) {
for (size_t j = 0; j <matched_points.size(); ++j) {
if (j > i) {
if (abs(matched_points[i].second.x - matched_points[j].second.x) < 1 && (abs(matched_points[i].second.y - matched_points[j].second.y)) < 1) {
//std::cout << " True " << std::endl;
//std::cout << " Point 1:" << " ID: " << Cam_4.unmatched_img_points[i].first << " X: " << Cam_4.unmatched_img_points[i].second.x << " Y: " << Cam_4.unmatched_img_points[i].second.y << std::endl;
//std::cout << " Point 2:" << " ID: " << Cam_4.unmatched_img_points[j].first << " X: " << Cam_4.unmatched_img_points[j].second.x << " Y: " << Cam_4.unmatched_img_points[j].second.y << std::endl;
matches_map.insert(std::pair<int, int>(matched_points[i].first, matched_points[j].first));
}
}
}
}
// Eliminate similar pairs and form triples/quadruples/quintuples... if possible
std::vector<int> unique_keys;
for (std::multimap<int, int>::iterator multimap_iterator = matches_map.begin(), end = matches_map.end(); multimap_iterator != end; multimap_iterator = matches_map.upper_bound(multimap_iterator->first)) {
unique_keys.push_back(multimap_iterator->first);
}
typedef std::multimap<int, int>::iterator MMAPIterator;
std::vector<std::vector<int>> final_values;
std::vector<int> helper_vector;
for (size_t i = 0; i < unique_keys.size(); ++i) {
std::pair<MMAPIterator, MMAPIterator> result = matches_map.equal_range(unique_keys[i]);
helper_vector.push_back(unique_keys[i]);
for (MMAPIterator it = result.first; it != result.second; it++) {
//std::cout << it->second << std::endl;
helper_vector.push_back(it->second);
}
final_values.push_back(helper_vector);
helper_vector.clear();
}
std::vector<int> v1, v2;
for (size_t i = 0; i < final_values.size(); ++i) {
for (size_t j = 0; j < final_values.size(); ++j) {
if (j > i) {
v1 = final_values[i];
v2 = final_values[j];
if (std::includes(v1.begin(), v1.end(), v2.begin(), v2.end())) {
std::cout << "Erased position " << j << std::endl;
final_values.erase(final_values.begin() + j);
}
v1.clear();
v2.clear();
}
}
}
for (size_t i = 0; i < final_values.size(); ++i) {
std::cout << "Printing column " << i << std::endl;
for (size_t j = 0; j < final_values[i].size(); ++j) {
std::cout << final_values[i][j] << std::endl;
}
}
}
Ok, since you didn't follow up on my second comment, I'll go with the answer. Your question was "Is there are smarter approach that the one I am using?" and the answer is "Yes", because your code is not doing the task it is supposed to do.
You want to cluster elements which fall in a square of side 1. Then these points:
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)));
should all fall in one single cluster. Given your output, it's not the case.
So the problem here is that you are failing to repeatedly join sets of points together. This is a very famous problem called Disjoint-set data structure and in fact it is used to find the connected components of a graph.
In your case you should use the first part of your code to create the edge matrix of a graph, then find its connected-components with the union-find algorithm.
Here you can find an example implementation of the Union-Find data structure based on indices, which map to the points in your vector. Not so smart, but it should work.
// 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;
}
};
The trick is to build the adjacency matrix (who is connected to who) and while doing this, if two elements are connected merge their sets. The flatten operation, simply renumbers the sets from 0 to n-1, so it's easier to remap your elements to their clusters.
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]);
}
}
The clusters vector will contain vectors of points connected together (in no particular order).