How can I calculate the unique centroids along with its radius range ?

Suppose I've centroid coordinates stored in text files, and I extracted those coordinates and stored them in auxillary arrays. For example, the centroids are like these : (Also the Threshold = 2 and Radius range =4:10 )

1st array has centroids (radius 4) - 34.00 26.00

36.00 21.00

2nd array has centroids (radius 5) - 40.81 36.13

58.50 54.00

3rd array has centroids (radius 6) - 24.50 49.75

40.82 35.91

40.62 10.56

57.14 50.00

4th array has centroids (radius 7) - 24.00 49.00

40.73 35.94

40.75 10.75

5th array has centroids (radisu 8) - 40.86 35.69

6th array has centroids (radius 9) - 40.78 35.39

7th array has centroids (radius 10) - 40.71 35.20

Now, first all the centroids at every array are marked un-visited which is 0. Now we start with 1st centroid of 1st array (34.00 26.00) and checks it with other centroids from 2nd, 3rd, 4th, 5th, 6th, 7th array. The matched ones(i.e., if the distance between current centroid and other centroid is less than equal to the threshold) gets into a buffer array and the average of them are calculated and put into the text file, if no matches are found append the current centroid directly to the text file. Also, the matched centroids from every array are marked visited are turned 1. Then I move to next element (36.00 21.00) of 1st array and started checking with centroids from 2nd, 3rd, 4th, 5th, 6th, 7th array but couldn't found any matches. So, it's appended as it is in the text file. Next, I went to 2nd array and started comparing (40.81 36.13) with the un-visited centroids left in 3rd, 4th, 5th, 6th and 7th array. If found any matches put them in a buffer (for this case now the buffer wiil have - {40.81 36.13},{40.82 35.91},{40.73 35.95},{40.86 35.69},{40.78 35.39},{40.71 35.20}) calculate the average of them (for this case the average of them is coming out (40.78 35.71) and put them in the text file. Likewise, the average values that gets into the text file are called the unique centroids.

Also, I want the radius range along with the unique centroids in the text file. So, the 1st centroid of 1st array hasn't found any matches within 2nd,3rd,4th,5th,6th or 7th array. So the radius range will be 4 - 5, because the centroid belongs to radius 4 and since it has no matches so (current radius of the centroid +1). Also, for the 1st centroid of 2nd array has many matches, so its radius range is 5 - 11, becasue the centroid (40.81 36.13) belongs to radius 5 and since it has found matches upto the last array, i.e., 7th array which has the radius 10, so (last checked array radius +1).

So, my desired output coming for the above provided input of centroid arrays:

34.00 26.00 | 4 - 5

36.00 21.00 | 4 - 5

40.78 35.71 | 5 - 11

58.50 54.00 | 5 - 6

24.25 49.37 | 6 - 8

40.68 10.65 | 6 - 8

57.14 50.00 | 6 - 7

I've tried writtinf the code for the above explained logic, but I think there's some error in the logic.Here is the whole code:-

function step_stdA
centroidFiles = {'centroids1.txt','centroids2.txt','centroids3.txt','centroids4.txt','centroids5.txt','centroids6.txt','centroids7.txt'}; 
threshold = 2;
radiusRange = 4:10;
unique_centroids_A(centroidFiles, threshold,radiusRange);
end
function unique_centroids_A(centroidFiles, threshold,radiusRange)
% Initialize cell arrays to store centroid data and visited flags 
centroidsData = cell(1, numel(centroidFiles)); 
visitedFlags = cell(1, numel(centroidFiles));
% Read centroid data from files and initialize visited flags
for i = 1:numel(centroidFiles)
    centroidsData{i} = dlmread(centroidFiles{i}, ' ', 1, 1); % Read data
    numCentroids = size(centroidsData{i}, 1);
    visitedFlags{i} = zeros(numCentroids, 1); 
end
uniqueCentroidsAll = cell(1, numel(centroidFiles));
for i = 1:numel(centroidFiles)
    currentCentroids = centroidsData(i:end-1);
    subsequentArrays = centroidsData(i+1:end);
    uniqueCentroidsAll{i} = processCentroids(currentCentroids, subsequentArrays, threshold, visitedFlags, radiusRange);
end
fid = fopen('unique_centroids_A.txt', 'w');
for i = 1:numel(uniqueCentroidsAll)
    uniqueCentroids = uniqueCentroidsAll{i};
    for j = 1:size(uniqueCentroids, 1)
        fprintf(fid, '%.2f %.2f | %d - %d\n', uniqueCentroids(j, 1), uniqueCentroids(j, 2));
    end
end
fclose(fid);
end
function uniqueCentroids = processCentroids(currentCentroids, centroidsArray, threshold, visitedFlags,radiusRange)
buffer = [];
radiusRanges = zeros(size(currentCentroids, 1), 1);
order = [];
for j = 1:size(currentCentroids, 1)
    currentCentroid = currentCentroids(j, :); % jth row of the current array
    matches = [];
    for k = 1:length(centroidsArray)
        otherCentroids = centroidsArray{k};
        otherRadius = radiusRange(k);
        otherVisitedFlags = visitedFlags{k};
        for m = 1:size(otherCentroids, 1)
            if otherVisitedFlags(m) == 0
                otherCentroid = otherCentroids(m, :);
                distance = norm(currentCentroid - otherCentroid);
                if distance <= threshold
                    matches = [matches; otherCentroid];
                    otherVisitedFlags(m) = 1; % Mark as visited
                end
            end
        end
        visitedFlags{k} = otherVisitedFlags; % Update visited flags
    end
    if ~isempty(matches)
        averageCentroid = mean(matches);
        buffer = [buffer; averageCentroid]; % Add current centroid if matches found
        maxRadius = max(matches(:, 3)); % Get the maximum radius from matches
        radiusRanges(j) = maxRadius; % Set radius range to maximum radius
    else
        buffer = [buffer; currentCentroid]; % Add current centroid if no matches found
    end
    % Store the order of appearance
    order = [order; j]; 
end
% Remove duplicate centroids, if any
[~, uniqueIdx, ~] = unique(buffer, 'rows', 'stable');
uniqueCentroids = buffer(uniqueIdx, :);
% Sort unique centroids based on the order of appearance
[~, sortedOrder] = sort(order);
uniqueCentroids = uniqueCentroids(sortedOrder, :);
% Combine unique centroids with corresponding radius ranges
uniqueCentroids = [uniqueCentroids, radiusRanges];
end

It's highly appreciatable if you could come up with some help, I'm stuck with this problem for more than 2 weeks.

[Matt J]

How many centroids are there in total, from all of the text files? Is there a reason you don't load them all into the workspace and process them all simultaneously?

[Saumalya]

Actually I have some previous code to extract centroids from a simplicial complex, I tried to automate the process of directly calculating the centroids of the image for a particular radius and keep storing them in a matrix , but didn't work. So, I stored centroids of the image for different radius in different text files ("Centroids1.txt", "Centroids2.txt", ..).

So these text files contains centroid coordinates for a particular radius. In total I have 14 centroids. But I want to keep them in an auxillary array, so that comparing between 2 different centroids is easier (i.e., checking for the condition).

What are your thoughts, should I keep all the centroids in a single 2D matrix? Would that be a better option for comparison between two centroids?

[Matt J]

In total I have 14 centroids.

So the entirety of your data across all files could be put in a 14-row table like below? And your desired result could also be a 14-row table of "Unique Centroids" and "Radius Ranges"? If not, then please describe how the input and final result would look in table form.

Centroids=randn(14,2)*10; Radius=randi(4,14,1);  %Fake input

T=table(Centroids, Radius)

T = 14×2 table
          Centroids           Radius
    ______________________    ______

      -4.5445       15.833      3   
    -0.030277      -3.1684      2   
       4.4993       -6.175      3   
      -1.0987      -5.4377      1   
       15.147       7.1663      3   
      -12.891       12.225      4   
       19.663     -0.68147      3   
      -5.7882      -1.9686      1   
      -3.9719       14.912      1   
       5.5955       -5.325      2   
      -9.5993       -15.08      3   
       3.2406       6.9401      2   
      -2.5107     -0.34192      1   
       12.938      -16.354      2   

[Catalytic]

Now we start with 1st centroid of 1st array (34.00 26.00) and checks it with other centroids from 2nd, 3rd, 4th, 5th, 6th, 7th array.

That's how you start, but how do you continue? Do you then perform the same check starting with the 2nd centroid of the first array? Do all centroids in all arrays get compared with each other?

[Saumalya]

Actually the no.of centroids may change upon the input image, and keeping them in a single table will not help, since I can't compare between current centroid and the other subsequent centroid, and also keep a the flag variable for visited or un-visited together.

My desired output is 7 row, 3 column like this:

34.00 26.00 | 4 - 5

36.00 21.00 | 4 - 5

40.78 35.71 | 5 - 11

58.50 54.00 | 5 - 6

24.25 49.37 | 6 - 8

40.68 10.65 | 6 - 8

57.14 50.00 | 6 - 7

[Saumalya]

Yes, when I start with the 1st centroid of the 1st array and checks it with all other centroids from 2nd, 3rd, 4th, 5th, 6th, 7th array. So, as usual I didn't get any matches (based on the condition that the distance between current centroid and subsequent centroid should be less than equal to threshold) and this centroid gets appended to the text file as it is. Likewise, we perform the same check with the 2nd centroid of 1st array and couldn't get any matches. Now, before going to the 2nd array mark the 2 centroids of 1st array as visisted,i.e, make the variable =1.

Now, go the 1st centroid of 2nd array and start comparing with all other centroids of 3rd, 4th, 5th, 6th, 7th array. The matches are stored in an array called buffer and the average of all the elements in the buffer is calculated and put into the text file. Now mark the visited centroids as 1 from 2nd array till 7th array those are being visited. After calculating the average the buffer array gets empty again to insert the matches into it. Like this we find the unique centroids.

Answer 1

[Matt J]

load data; threshold=2;  %Example input

T=sortrows(table(Centroid, Radius),2)

T = 14×2 table
       Centroid       Radius
    ______________    ______

       34       26       4  
       36       21       4  
    40.81    36.13       5  
     58.5       54       5  
     24.5    49.75       6  
    40.82    35.91       6  
    40.62    10.56       6  
    57.14       50       6  
       24       49       7  
    40.73    35.94       7  
    40.75    10.75       7  
    40.86    35.69       8  
    40.78    35.39       9  
    40.71     35.2      10  

Centroid=T.Centroid; Radius=T.Radius;

D=pdist2(Centroid,Centroid)<threshold;

 G=findgroups(Radius);
 N=histcounts(G,1:max(G)+1);

D=D&(1:width(D)>repelem(cumsum(N)',N)); %Block uppper-triangular mask

uniqueCentroid=(D*Centroid)./sum(D,2);
maxRad=max(Radius(:).'.*D,[],2);

nomatch=~any(D,2);

uniqueCentroid(nomatch,:)=Centroid(nomatch,:);
maxRad(nomatch,:)=Radius(nomatch,:);

result=table(uniqueCentroid,[Radius,maxRad+1],'Var',["Unique Centroids","Range"])

result = 14×2 table
    Unique Centroids     Range  
    ________________    ________

        34        26     4     5
        36        21     4     5
     40.78    35.626     5    11
      58.5        54     5     6
        24        49     6     8
     40.77    35.555     6    11
     40.75     10.75     6     8
     57.14        50     6     7
        24        49     7     8
    40.783    35.427     7    11
     40.75     10.75     7     8
    40.745    35.295     8    11
     40.71      35.2     9    11
     40.71      35.2    10    11

[Saumalya]

Thanks for the answer, but the logic is a bit incorrect. Actually, there should be another column of visited (i.e., intially all the centroids is un-visited so marked 0, when any centroid gets visited it turns 1).

So the logic is, the 1st centroid (34.00 26.00) is compared with every centroids from radius 5 till radius 10. Since, there's no match it gets appended as it is. So, the visited column for this centroid truns 1. Next, (36.00 21.00) also has no match, so gets appended as it is. So, the visited column for this centroid turns 1. Next up, (40.81 36.13) is matched with [{40.82 35.91}, {40.73 35.94}, {40.86 35.69}, {40.78 35.39}, {40.71 35.20}] as because the condition (i.e., euclidian distance between the current centroid and the subsequent centroid should be less than equal to the threshold). So, now these values will be stored in a buffer [{40.81 36.13}, {40.82 35.91}, {40.73 35.94}, {40.86 35.69}, {40.78 35.39}, {40.71 35.20}] and the average of all these centroid coordinates is (40.78 35.71) which is gets into the result. So, the visited column of all these centroid are turned 1 and the buffer array becomes empty.

Next up is (58.50 54.00) which also has no matches. Marked visited so turned 1. Next up is (24.50 49.75) is checks with all the un-visited centroids,i.e., those left 0. and the matches in the buffer are [{24.50 49.75}, {24.00 49.00}] whose average comes out (24.25 49.37). Mark these visited (turns 1).

Next up is (40.62 10.56) because the previous centroid (40.82 35.91) is marked visited (i.e., shows 1 in the column, so we have to pick only the un-visited centroids and check with the other un-visited centroids). So, for this centroid the matches in the buffer are [{40.62 10.56}, {40.75 10.75}] and the average comes out to be (40.68 10.65).

Next up is (57.14 50.00) which also has no matches, marks it visited.

Ans now the final output is:

34.00 26.00 | 4 - 5

36.00 21.00 | 4 - 5

40.78 35.71 | 5 - 11

58.50 54.00 | 5 - 6

24.25 49.37 | 6 - 8

40.68 10.65 | 6 - 8

57.14 50.00 | 6 - 7

[Matt J]

So you're saying that once two centroids match, they are withdrawn from all future comparisons? If so, though, the final groupings will depend on which unvisited centroid you start with, which seems random.

[Matt J]

Actually, there should be another column of visited

The final output that you show here does not have any additional columns.

[Saumalya]

Yes, once 2 centroids are matched they're marked visited (turns the flag from 0 to 1). So, that we can comapre only the un-visited centroids with other un-visited centroids. At first every centroid is marked un-visited (flag 0). And likewise those centroids gets visited we turn the flag to 1. So that we should not visit the same centroids again and again.

In the final ouptut, consider the radius range after ' | ' sign as another column.

[Matt J]

load data; threshold=2;  %Example input

T=sortrows(table(Centroid, Radius),2);

D=pdist2(T.Centroid,T.Centroid)<threshold;

 G=findgroups(T.Radius);
 N=histcounts(G,1:max(G)+1);

D=D&(1:width(D)>repelem(cumsum(N)',N)); %Block uppper-triangular mask

Gr=digraph(D); Gr.Nodes=T;

T=parseGraph(Gr)

T = 7×2 table
    Unique Centroids     Range 
    ________________    _______

        34        26    4     5
        36        21    4     5
    40.785     35.71    5    11
      58.5        54    5     6
     24.25    49.375    6     8
    40.685    10.655    6     8
     57.14        50    6     7

function T=parseGraph(Gr)

    Centroid=Gr.Nodes.Centroid; Radius=Gr.Nodes.Radius;

    buffer=[1;successors(Gr,1)];

    maxrad=max(Radius(buffer))+1; 
    avgcentroid=mean(Centroid(buffer,:),1);

    T=table(avgcentroid, [Radius(1), maxrad],'Var', ["Unique Centroids","Range"]);
    
    Gr=rmnode(Gr,buffer);
    
    if numnodes(Gr)==0
        return
    else
        T=[T;parseGraph(Gr)];
    end

end

[Saumalya]

Yes, it worked. Thanksss a lot.