clear; clc; close all;

rng(100);

X = [randn(100, 2) * 0.75 + ones(100,2);
     randn(100, 2) * 0.5 - ones(100,2);
     randn(100, 2) * 0.75];
 
k = 3;
N = size(X, 1);
labels = zeros(N, 2);
labels(1, 1) = -1;
T = zeros(N, k);
centers = X(randperm(N, k), :); % initial guess by random

iter = 0;
while true

    for i = 1 : k

        center = centers(i, :);
        
        for j = 1 : N
            
            T(j, i) = norm(X(j, :) - center);
            
        end

    end

    [~, idx] = min(T, [], 2);
    labels(:, 2) = idx;

    for i = 1 : k

        mask = labels(:, 2) == i;
        centers(i, 1) = mean(X(mask, 1));
        centers(i, 2) = mean(X(mask, 2));

    end
    
    plot(centers(:, 1), centers(:, 2), "kx", "markersize", 14); hold on; grid on;
    for i = 1 : k
        plot(X(labels(:, 2) == i, 1), X(labels(:, 2) == i, 2), "o", "color", [randi(256, 1, 3) - 1] / 255);
    end
    
    pause(0.5);
    
    if any(labels(:, 1) ~= labels(:, 2))
        fprintf("%d: %d changes\n", iter, sum(labels(:, 1) ~= labels(:, 2)));
        labels(:, 1) = labels(:, 2);
        clf;
    else
        break;
    end
    
    iter = iter + 1;

end

% [idx, C] = kmeans(X, k);
% 
% figure; hold on;
% gscatter(X(:, 1), X(:, 2), idx); grid on;
% plot(C(:, 1), C(:, 2), "kx");
% legend("Cluster 1", "Cluster 2", "Cluster 3", "Cluster Centroid");
