Mercure1

function xyOut = solver(a, xyIn, wts)
global friendIndex


xy = xyIn;

%% General work on connectivity
nbSommet = length(wts);     % nb of points (int)
friendNb = sum(a);          % nb of friend (vect)
% friendIndex(k) is the vector (column) of friends of k (index)
friendIndex = cell(nbSommet);
for k=1:nbSommet
    friendIndex{k} = find(a(:,k));
end

%% General work on cost function
score = numKnots(a, xyIn);
distanceSq = 0;

%% some ideas
%oneIndex = find(friendNb == 1);
%twoIndex = find(friendNb == 2);

%Trouver le nb d'intersections pour chaque sommet
%Prioriser les sommets par une fonction genre nbINter/weight
%Suivant cet ordre, essayer plusieurs strat?gies (dans un des 4 coins, ou au barycentre)

%% Solution
for n=1:10
for k = 1:nbSommet
    bary = barycentre(xy, k);
    newXY = round( (bary+xy(k, :))/2 );
    if isPositionFree(xy, newXY)
        xy(k,:) = newXY;
    elseif isPositionFree(xy, round(bary)) 
        xy(k,:) = round(bary);
    end
end
end

xyOut = xy;

end


%% FUNCTIONS related to the current graph
function bool = isPositionFree(xy, pos)
% (verified)
% returns 1 if position is free, 0 otherwise
    bool = 1;
    xIndex = ( xy(:,1)==pos(1) );
    bool = ~any(xy(xIndex,2)==pos(2));
end


function vect = getOrderIndex(xy)
    vect = 1:size(xy,1);
end

function res = barycentre(xy, sommet)
global friendIndex
    res = mean(xy(friendIndex{sommet}, :),1);
end

function res = closestPositions(pos)
    res = zeros(9,2);
    k=1;
    for i=-1:1
        for j=-1:1
            res(k, :) = pos + [i, j];
            k=k+1;
        end
    end
end


function res = closestFreePositions(pos)
    
end

%% GEOMETRIC FUNCTIONS

function N = numKnots(A, xy)
    % Consider only unique lines (A is symmetric with ones on diagonal)
    A = triu(A,1);
    nLines = nnz(A);

    % Find xy coordinates for first and second point on each line
    [p1i,p2i] = find(A);
    segments = [xy(p1i,:) , xy(p2i,:)];
    N = 0;
    for i = 1:nLines-1
        seg1 = segments(i,:);     %[x1 y1 x2 y2]
        for j = i:nLines
            seg2 = segments(j,:); %[x3 y3 x4 y4]
            N = N + nbIntersection(seg1, seg2);
        end
    end
end

function nb = nbIntersection(seg1, seg2)
% inspired from http://www.faqs.org/faqs/graphics/algorithms-faq/ (1.03)
% seg1 = [x1, y1, x2, y2]
% seg2 = [x3, y3, x4, y4]
    Ax = seg1(1);
    Ay = seg1(2);
    Bx = seg1(3);
    By = seg1(4);
    Cx = seg2(1);
    Cy = seg2(2);
    Dx = seg2(3);
    Dy = seg2(4);
    
    rNom = (Ay-Cy)*(Dx-Cx) - (Ax-Cx)*(Dy-Cy);
    sNom = (Ay-Cy)*(Bx-Ax) - (Ax-Cx)*(By-Ay);
    rsDen = (Bx-Ax)*(Dy-Cy) - (By-Ay)*(Dx-Cx);
    
    % they are not parallel
    if rsDen ~= 0
        % strict intersection
        if rNom>0 && sNom>0 && rNom<rsDen && sNom<rsDen
            nb = 1;
        % one vertex is located on other edge
        elseif rNom==0 || sNom==0 || rNom==rsDen || sNom==rsDen
            nb = 2;
        else
            nb = 0;
        end
    % they are parallel
    else
        % they are colinear
        if rNom == 0
            % if not vertical
            if Ax ~= Bx
                if (Ax>min(Cx, Dx) && Ax<max(Cx, Dx)) || (Bx>min(Cx, Dx) && Bx<max(Cx, Dx))
                    nb = 2;
                else
                    nb = 0;
                end
            % if vertical
            else
                if (Ay>min(Cy, Dy) && Ay<max(Cy, Dy)) || (By>min(Cy, Dy) && By<max(Cy, Dy))
                    nb = 2;
                else
                    nb = 0;
                end                
            end
        % they are parallel but not colinear
        else
            nb = 0;
        end
    end
end