function xyOut = solver2(a, xyIn, wts)
at = triu(a);
N = length(wts);
linkCount = sum(at,2);
[maxNLinks,maxind] = max(linkCount);
%{
depth = 10;
an = zeros(N,N,depth);
an(:,:,1) = a;
for i =2:depth
for j = 1:N
for k = j:N
an(j,k,i) = any(an(:,j,i-1) & an(:,k,1));
%an(k,j,i) = an{i}(j,k);
end
end
an(:,:,i) = an(:,:,i)' | an(:,:,i);
end
%}
%% Define direction offsets
dir8 = [0,1;
1,1;
1,0;
1,-1;
0,-1;
-1,-1;
-1,0;
-1,1;
0,1;];
dir16 = [0,2; % north, direction 1
1,2;
2,2; % NE, 3
2,1;
2,0; % east, 5
2,-1;
2,-2; % SE, 7
1,-2;
0,-2; % south, direction 9
-1,-2;
-2,-2; % SW, 11
-2,-1;
-2,0; % west, 13
-2,1;
-2,2; % NW, 15
-1,2;]; % NNW, 16
dir24 = [0,3;
1,3;
2,3;
3,3;
3,2;
3,1;
3,0;
3,-1;
3,-2;
3,-3;
2,-3;
1,-3;
0,-3;
-1,-3;
-2,-3;
-3,-3;
-3,-2;
-3,-1;
-3,0;
-3,1;
-3,2;
-3,3;
-2,3;
-1,3;];
%% Initialize key vectors
placed = false(1,N);
linksToPlaced = zeros(1,N);
xyOut = xyIn;
%% Start at a link with the highest order
selectedInd = maxind;
%% move it to the center and mark it placed
[meanxy] = mean(xyIn,1);
xyOut(selectedInd,:) = round(meanxy);
placed(selectedInd) = true;
%% Update linksToPlaced
linksToPlaced = linksToPlaced + a(selectedInd,:);
linksToPlaced(placed) = 0; % ignore if already placed
%% Loop until all nodes placed
while any(~placed)
%% Select the next node
[maxLinksToPlaced] = max(linksToPlaced);
candidates = linksToPlaced==maxLinksToPlaced;
num_candidates = sum(candidates);
if num_candidates>1
% Choose among candidiates based on order
links = linkCount(candidates);
maxLinks = max(links);
%Continuting candidates have maximal order
candidates = candidates & (linkCount==maxLinks)';
num_candidates = sum(candidates);
if num_candidates>1
% Just pick one
selectedInd = find(candidates,1,'first');
else
selectedInd = find(candidates,1,'first');
end
else
selectedInd = find(candidates,1,'first');
end
%% Place the selected node
% If 1/2 or more links are yet to be placed, we want to be towards the
% outside of the cloud.
fracLeft = maxLinksToPlaced/linkCount(selectedInd);
if fracLeft>=0.5
% prefer away from center of cloud to allow room for new links
away = true;
else
away = false;
end
% Find centroid of placed, linked points
placedLinked = placed & a(selectedInd,:);
cent_linked = mean(xyOut(placedLinked',:),1);
% Find centroid of all placed points
cent_placed = mean(xyOut(placed',:),1);
if away
% Prefer to move away from centroid of all points, because the majority
% of linkages are going to come from new points, and we want to have
% room for those
% pick one placed neigbor to be near, for now let's choose the lowest
% order one
[minLinks] = min(linkCount(placedLinked));
bestNeighbor = find(linkCount==minLinks & placedLinked',1,'first');
preferred_dir = xyOut(bestNeighbor,:)-cent_placed;
loc = xyOut(bestNeighbor,:);
else % not away
% Prefer to be placed near centroid of linked points because most
% linkages are already placed
loc = round(cent_linked);
preferred_dir = [];
end
loc_final = placeme(loc,preferred_dir,placed);
% Update
xyOut(selectedInd,:) = loc_final;
placed(selectedInd) = true;
linksToPlaced = linksToPlaced + a(selectedInd,:);
linksToPlaced(placed) = 0; % ignore if already placed
end % end of while
function loc_final = placeme(loc,preferred_dir,placed)
% Choose a good final location near loc. if there is a preferred
% direction, then the desired point is some distance in that direction
% from the input loc. The desired distance depends on the remaining
% linkage order of the currently selected point.
if ~isempty(preferred_dir) && norm(preferred_dir)>0
%Determine desired distance based on remaining node order
desired_dist = linkCount(selectedInd)-linksToPlaced(selectedInd)+1;
% Deterimine desired location
loc = loc+preferred_dir/norm(preferred_dir)*desired_dist;
end
rounded_loc = round(loc);
% Is something there?
dirlevel = 8;
dircount = 0;
startdir = get_start_dir(preferred_dir,dirlevel);
curdir = startdir;
base_loc = rounded_loc;
cur_loc = base_loc;
while ~isempty(intersect(xyOut(placed,:),cur_loc,'rows'))
%keep looking if there is already a point there
% Start in a direction, then move clockwise
% Increment dirlevel if necessary
if dircount==dirlevel-1
dirlevel = dirlevel+8;
dircount = 0;
startdir = get_start_dir(preferred_dir,dirlevel);
end
cur_loc = new_loc(base_loc,dirlevel,dircount,startdir);
if isnan(cur_loc)
% error signal from new_loc, just put the point outside the
% range of current points
cur_loc =[max(xyOut(placed,1))+1,base_loc(2)];
break
end
dircount = dircount+1;
end
loc_final = cur_loc;
function cur_loc = new_loc(base_loc,dirlevel,dircount,startdir)
% rotate from the starting direction by dircount units,
% increment, and generate the new current location
dirnow = startdir+dircount;
if dirnow>dirlevel
dirnow = dirnow-dirlevel;
elseif dirnow==0
dirnow=dirlevel;
end
if dirlevel==8
cur_loc = base_loc+dir8(dirnow,:);
elseif dirlevel==16
cur_loc = base_loc+dir16(dirnow,:);
elseif dirlevel == 24
cur_loc = base_loc+dir24(dirnow,:);
else
% Give up and put it right on the spot, even though it will
% be overlapping another point.
cur_loc = NaN;
%make_an_error
end
end
function startdir = get_start_dir(preferred_direction,dirlevel)
% get a starting direction at the preferred dirlevel
if isempty(preferred_direction) || norm(preferred_direction)==0
% choose randomly
startdir = ceil(rand*dirlevel);
else
startdir = ceil(rand*dirlevel);
end
end
end % eof for placeme
end
|
