What is the algorithm for combining points in a region?

The use of the distance matrix as a solution to the clustering problem in many cases is justified, although it leads, in general, to redundant memory reservation due to the so-called data mirroring effect. However, consider this method.

In the question tags there is no mention of the implementation language, and therefore, probably, it is permissible to use any, in particular C ++.

To begin with, we will create a structure traditionally used in such cases (it is possible and a class, but there is no special sense):

struct Point { Point() : _x(0), _y(0) {} Point(int x, int y) : _x(x), _y(y) {} int _x, _y; }; 

We will experiment with the same points that are indicated in the question (of course, any others are possible):

 std::vector<Point> pnts; pnts.push_back(Point(45,45)); pnts.push_back(Point(0,0)); pnts.push_back(Point(21,21)); pnts.push_back(Point(29,29)); pnts.push_back(Point(5,5)); pnts.push_back(Point(33,33)); pnts.push_back(Point(40,40)); pnts.push_back(Point(80,80)); pnts.push_back(Point(20,20)); pnts.push_back(Point(2,2)); pnts.push_back(Point(25,25)); 

The distance matrix is ​​created by enumerating each point with each and saving, in fact, the distance between them:

 const int n = pnts.size(); std::vector<std::vector<int> > distances(n); for(int i = 0; i < n; ++i) { const Point &p1 = pnts.at(i); // По умолчанию заполняем каждую колонку нулями. std::vector<int> dist(n,0); for(int j = 0; j < n; ++j) { const Point &p2 = pnts.at(j); if(i == j) { // Если речь об одной и той же точке, // то и нечего вычислять, расстояние - 0. continue; } else if(i > j) { // Если уже ранее успели вычислить расстояние между // двумя точками, то просто копируем значение. dist[j] = distances[j][i]; } else { // Собственно, вычисление расстояния. dist[j] = std::sqrt(std::pow(p1._x-p2._x,2) + std::pow(p1._y-p2._y,2)); } } distances[i] = dist; } 

The resulting matrix on the existing data set will look like this:

  0 63 33 22 56 16 7 49 35 60 28 63 0 29 41 7 46 56 113 28 2 35 33 29 0 11 22 16 26 83 1 26 5 22 41 11 0 33 5 15 72 12 38 5 56 7 22 33 0 39 49 106 21 4 28 16 46 16 5 39 0 9 66 18 43 11 07 56 26 15 49 9 0 56 28 53 21 49 113 83 72 106 66 56 0 84 110 77 35 28 1 12 21 18 28 84 0 25 7 60 2 26 38 4 43 53 110 25 0 32 28 35 5 5 28 11 21 77 7 32 0 

As is well seen, it is mirror, and therefore redundant, and it is this factor that can be the main reason for the impossibility of using the method in question.

I deliberately do not use double type for distance storage, since accuracy with an integer ( int ) is more than enough, plus some memory savings, plus this same vector can be easily used as an index matrix.

The matrix of indices serves exactly the task of reducing the number of iterations of an array of points. This is actually a map of indices, sorted by distance. Thus, it turns out that for each point the closest to it other points will always be in the first places.

 // Здесь можно сэкономить и не создавать отдельный вектор // под матрицу индексов, просто перезаписав значения вектора расстояний, // если конечно не планируется его использовать далее. std::vector<std::vector<int> > indexes(n); // Шаблон колонки индексов. std::vector<int> tpl(n); for(int i = 0; i < n; ++i) tpl[i] = i; for(int i = 0; i < n; ++i) { std::vector<int> vct = tpl; const std::vector<int> &dist = distances[i]; std::sort(vct.begin(), vct.end(), [&dist](int i1, int i2) { return dist[i1] < dist[i2]; }); indexes[i] = vct; } 

The result is the following set of indices of points:

  0 6 5 3 10 2 8 7 4 9 1 1 9 4 8 2 10 3 5 6 0 7 2 8 10 3 5 4 6 9 1 0 7 3 5 10 2 8 6 0 4 9 1 7 4 9 1 8 2 10 3 5 6 0 7 5 3 6 10 0 2 8 4 9 1 7 6 0 5 3 10 2 8 4 9 1 7 7 0 6 5 3 10 2 8 4 9 1 8 2 10 3 5 4 9 1 6 0 7 9 1 4 8 2 10 3 5 6 0 7 10 2 3 8 5 6 0 4 9 1 7 

The first column (index "0") of the matrix under consideration contains the indices of points in relation to themselves. The distance here is obviously zero and it is for this reason that after sorting the cluster formation cycle can be started from the column under the index "1".

The second column (index "1") is the index of the closest point with respect to the point with the index in the first column. Similarly, the contents of all subsequent columns, but with increasing distance.

Having on hand a matrix of sorted indexes, nothing more remains, how to proceed, in fact, to clustering.

The problem's author has a feature that requires consideration of different maxima for horizontal and vertical pixel distances:

 const int hrz_max = 10; const int vrt_max = 10; 

Clustering is convenient to perform recursively:

 void check(const std::vector<Point> &pnts , const std::vector<std::vector<int> > &indexes , int pnt_idx, std::vector<int> &d) { const Point &p1 = pnts[pnt_idx]; d.push_back(pnt_idx); // ... со второй колонки. for(int i = 1, n = pnts.size(); i < n; ++i) { const int pnt2_idx = indexes[pnt_idx][i]; if(std::find(d.begin(),d.end(),pnt2_idx) != d.end()) continue; const Point &p2 = pnts[pnt2_idx]; if(std::abs(p1._x-p2._x) <= hrz_max && std::abs(p1._y-p2._y) <= vrt_max) { check(pnts, indexes, pnt2_idx, d); } else { // Незачем крутить цикл далее, т.к. расстояния // отсортированы по возрастанию значения. break; } } } 

Function Arguments:

const std::vector<Point> &pnts - source point vector;

const std::vector<std::vector<int> > &indexes - matrix of indices;

int pnt_idx - index of the point for which we are forming the cluster;

std::vector<int> &d is a vector that will contain indices of points of a single cluster.