function [ centers ] = clusterizeVertices( vertices , distance)
%CLUSTERIZEVERTICES
%   The function clusterizes the vertices given in [x,y;...] pairs and
%   consecutive along the hull. Returns the clusters in the form of 
%   cluster center coordinates and. They are ordered along the hull.

distancesqr = distance^2;
cs = 1; % cluster start
ce = 1; % cluster end

centers = [];

while true
    
    isin = true;
    while isin && ce < length(vertices)
        isin = isSingleLinkagePresent(vertices(cs:ce,:), vertices(ce+1,:), distancesqr);
        ce = ce + 1;
    end
    
    if ~isin
        ce = ce - 1;
    end
    
    %plot(vertices(cs:ce,1),vertices(cs:ce,2),'gx');
    
    if ce == length(vertices) && isSingleLinkagePresent(vertices(cs:ce,:), vertices(1,:), distancesqr);
        % looping cluster
        
        centers = centers(2:end,:);
        
        cpart = vertices(cs:end,:);
        lastcs = cs;
        cs = 1;
        ce = 1;
        isin = true;
        while isin && ce < lastcs
            isin = isSingleLinkagePresent([vertices(cs:ce,:); cpart], vertices(ce+1,:), distancesqr);
            ce = ce + 1;
        end
        
        centers = [ centers; ( sum( [vertices(cs:ce,:); cpart], 1 ) ) ./ (ce-cs+1+length(vertices)-lastcs+1) ];
        
        return;
    else
       % normal cluster
       centers = [ centers; ( sum( vertices(cs:ce,:), 1 ) ) ./ (ce-cs+1) ];
       
       if ce == length(vertices)
           return;
       end
    end
    
    cs = ce + 1;
    ce = cs;
    
end

function isin = isSingleLinkagePresent(cluster,vertex,distancesqr)
%( min(sum( (vertices(cs:ce,:)-vertices(ce+1,:)).^2, 2)) < distancesqr );
vectors = cluster-ones(size(cluster))*diag(vertex);
vectors = vectors.^2;
isin = min( sum( vectors, 2 ) ) < distancesqr;
