Какой существует алгоритм для объединения точек в области?

#алгоритм

Есть область с кучей разбросанных точек, нам нужно объединить в области те точки,
которые находятся на расстоянии меньше определенной константы друг от друга.

Как-то вот так:


    

Ответы

Ответ 1

Использование матрицы расстояний в качестве решения задачи кластеризации во многих
случаях вполне оправданно, хотя и ведёт, в общем-то, к излишнему резервированию памяти
в связи с так называемым эффектом зеркалирования данных. Впрочем, рассмотрим именно
этот метод.

В тегах вопроса отсутствует упоминание о языке реализации, а потому, наверное, допустимо
использовать любой, в частности С++.

Для начала создадим традиционно используемую в таких случаях структуру (можно и класс,
но особого смысла нет):

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

    int _x, _y;
};


Экспериментировать будем с теми же точками, что указаны в вопросе (разумеется, можно
любые иные):

std::vector 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));


Матрица расстояний создаётся перебором каждой точки с каждой и сохранением, собственно,
расстояния между ними:

const int n = pnts.size();

std::vector > distances(n);

for(int i = 0; i < n; ++i) {
    const Point &p1 = pnts.at(i);

    // По умолчанию заполняем каждую колонку нулями.
    std::vector 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;
}


Получившаяся матрица на имеющемся наборе данных будет выглядеть так:

 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


Как хорошо заметно, она зеркальна, а значит избыточна, и именно этот фактор может
стать основной причиной невозможности использования рассматриваемого метода. 

Я намеренно не использую для хранения расстояния тип double, поскольку точности с
целым (int) более чем достаточно, плюс некоторая экономия памяти, плюс этот же самый
вектор можно будет легко задействовать как матрицу индексов.

Матрица индексов служит аккурат задаче снижения количества итераций массива точек.
Это фактически карта индексов, отсортированных по возрастанию расстояния. Таким образом
получится, что для каждой точки самые близкие к ней иные точки будут всегда на первых
местах.

// Здесь можно сэкономить и не создавать отдельный вектор
// под матрицу индексов, просто перезаписав значения вектора расстояний,
// если конечно не планируется его использовать далее.
std::vector > indexes(n);

// Шаблон колонки индексов.
std::vector tpl(n);
for(int i = 0; i < n; ++i) tpl[i] = i;

for(int i = 0; i < n; ++i) {
    std::vector vct = tpl;

    const std::vector &dist = distances[i];
    std::sort(vct.begin(), vct.end(), [&dist](int i1, int i2) {
        return dist[i1] < dist[i2];
    });

    indexes[i] = vct;
}


Получится следующий набор индексов точек:

 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


В первой колонке (индекс "0") рассматриваемой матрицы содержатся индексы точек по
отношению самих к себе. Расстояние здесь очевидно нулевое и именно по этой причине
после сортировки цикл формирования кластера можно начинать с колонки под индексом "1".

Вторая колонка (индекс "1") - это индекс самой близкой точки по отношению к точке
с индексом в первой колонке. Аналогично содержимое и всех последующих колонок, но с
увеличением расстояния.

Имея на руках матрицу отсортированных индексов, ничего более не остаётся, как приступить,
собственно, к кластеризации.

У автора вопроса задача содержит особенность, которая требует учёта различных максимумов
для горизонтальных и вертикальных пиксельных расстояний:

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


Кластеризацию удобно производить рекурсивно:

void check(const std::vector &pnts
    , const std::vector > &indexes
    , int pnt_idx, std::vector &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;
        }
    }
}


Аргументы функции:

const std::vector &pnts - вектор исходных точек;

const std::vector > &indexes - матрица индексов;

int pnt_idx - индекс точки, для которой формируем кластер;

std::vector &d - вектор, который будет содержать индексы точек одного кластера.


Ответ 2

написал свой велосипед на javascript, может кому еще пригодится




Вывод:

матрица расстояний

0,64,34,23,57,17,7,49,35,61,28
64,0,30,41,7,47,57,113,28,3,35
34,30,0,11,23,17,27,83,1,27,6
23,41,11,0,34,6,16,72,13,38,6
57,7,23,34,0,40,49,106,21,4,28
17,47,17,6,40,0,10,66,18,44,11
7,57,27,16,49,10,0,57,28,54,21
49,113,83,72,106,66,57,0,85,110,78
35,28,1,13,21,18,28,85,0,25,7
61,3,27,38,4,44,54,110,25,0,33
28,35,6,6,28,11,21,78,7,33,0


матрица близости

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,9,6,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,7,1
7,0,6,5,3,10,2,8,4,9,1
8,2,10,3,5,4,9,6,1,0,7
9,1,4,8,2,10,3,5,6,0,7
10,3,2,8,5,6,0,4,9,1,7


матрица кластеров

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