Группировка точек с помощью триангуляции

Язык: MATLAB

Определение проблемы:

У меня есть набор 2D-точек в пространстве. Я хотел бы сгруппировать точки на основе их евклидова расстояния. Мои данные имеют такое свойство, что две группы всегда разделены как минимум R единицами. Следовательно, для данной точки все точки, которые находятся ближе, чем на 50 единиц, могут считаться ее соседями. Объединение точек, имеющих общих соседей, приведет к группам (по крайней мере, такова идея).

Предлагаемый метод:

Используйте триангуляцию Делоне в Matlab и получите список ребер полученных треугольников. Удалите все ребра, длина которых превышает R единиц. Каждая группа оставшихся точек - это группы, которые я ищу. Оставшиеся несоединенные точки можно игнорировать.

Попытка: я попытался реализовать описанное выше в MATLAB, но я делаю ошибку, группируя оставшиеся точки. Прикрепляю свой код.

DT      = delaunayTriangulation(double(frame(:,1:2)));
edgeList   = edges(DT);

edgeVertex1 = frame(edgeList(:,1),:); 
edgeVertex2 = frame(edgeList(:,2),:); 

dVec = edgeVertex1 - edgeVertex2;
edgeLengths = sqrt(sum(abs(dVec).^2,2));
requiredEdges = edgeLengths < NEIGH_RADIUS;

edgeLengthsFiltered = edgeLengths(requiredEdges);
edgeListFiltered = edgeList(requiredEdges,:);

% Clustering
edgeOrigins = edgeListFiltered(:,1);
edgeEndings = edgeListFiltered(:,2);
nodeList = unique(edgeOrigins);

if isempty(nodeList)
    Result = struct([]);
    super_struct(i).result = Result;
else
    groups = cell(10,1);
    groups{1} = nodeList(1);
    groupLength = 2;
    flag = 0;

    % grouping
    for j = 1:1:length(nodeList);
        neighbourList = [nodeList(j); edgeEndings(edgeOrigins==nodeList(j))];
        % add current node as part of neighbourList
        for k = 1:1:groupLength-1
           te =  ismembc(groups{k}, neighbourList);
           if sum(te) ~=0
                temp = sort([groups{k}; neighbourList]);
                groups{k} = temp([true;diff(temp(:))>0]);
                flag = 1;
                break;
            end
        end

        if ~flag
            groups{groupLength} = neighbourList;
            groupLength = groupLength + 1;
        end

        flag = 0;
    end

    largeGroups = cell(1,1);
    largeGroups_c = 1;
    for j = 1:1:groupLength -1;
        if ~ isempty(groups{j})

        for k = j+1:1:groupLength - 1
            te = ismembc(groups{j}, groups{k});
            if sum(te) ~= 0
                temp = sort([groups{j}; groups{k}]);
                groups{j} = temp([true;diff(temp(:))>0]);
                groups{k} =[];
            end    
        end

        % ignore small groups
        if length(groups{j}) > MIN_PTS_IN_GROUP
            largeGroups{largeGroups_c} = groups{j};
            largeGroups_c = largeGroups_c+1;
        end

        end
    end

в приведенном выше коде frame — это переменная со списком точек. Константы NEIGH_RADIUS представляют R из вопроса. Другая константа MIN_PTS_IN_GROUP определяется пользователем для выбора минимального количества точек, необходимого для того, чтобы считать его интересующим кластером.

Когда я запускаю приведенный выше код, все еще есть случаи, когда одна группа точек по-прежнему представлена ​​​​в виде нескольких групп.

Красные линии ограничивают одну группу, как указано в приведенном выше коде. Ясно, что есть пересекающиеся группы, что неправильно.

Вопрос 1 Может ли кто-нибудь предложить лучший (и правильный) способ группировки?

Вопрос 2 Любые другие альтернативные методы получения групп быстрее, чем Триангуляция, также были бы великолепны!

заранее спасибо