-
Notifications
You must be signed in to change notification settings - Fork 0
/
linearizeHamPath3D.m
91 lines (85 loc) · 3.04 KB
/
linearizeHamPath3D.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
%Traversing the image I with a Hamilton path with given entry point and
%exit point without a precomputed min spanning tree
function [LT, visitOrder, exitPix] = linearizeHamPath3D(V, entryPix, exitFace)
% simple graph test cases work up to 3*3
% I = [1 1 1 1; 0 0 0 0; 0 0 0 0; 0 0 0 0];
% entryPix = [3,1];
% exitPix = [1,3];
% [Status, visitOrder, LT] = hamPathGrid(I, entryPix, exitPix);
% return;
% Use nearest neighbor strategy
LT = [];
visitOrder = [];
exitPix = [];
global w;
global h;
global d;
w = size(V,1);
h = size(V,3);
d = size(V,2);
visitOrder = [];
LT = [];
exitPix = [];
if w * h * d > 64
disp('Cannot handle this case yet.');
return;
end
needPartition = false;
exitPixs = findCompatibleExitPixs3D(size(V), entryPix, exitFace);
if ~isempty(exitPixs)
%% convert the volume connectivity to adjacency matrix
Madj = createAdjMatrixVol(V, size(V));
entryId = ((entryPix(3)-1)*h + entryPix(2)-1)*w + entryPix(1)-1+1;
minCost = realmax;
minpath_id = -1;
hamPath = [];
for i = size(exitPixs,1):-1:1
if exitPixs(i,1) == entryPix(1) && exitPixs(i,2) == entryPix(2) && exitPixs(i,3) == entryPix(3)
continue;
end
%%Generate Hampath!!!
exitId = ((exitPixs(i,3)-1)*h + exitPixs(i,2)-1)*w + exitPixs(i,1)-1+1;
hamPath = hamiltonian(Madj, entryId, exitId);
if isempty(hamPath) % hampath may be invalid!
continue;
end
[visitOrder, LT] = reconstrPath(hamPath, V, size(V));
LTG = gradient(LT);
gradMag = sum(abs(LTG));
% disp(gradMag)
if gradMag < minCost
exitPix = exitPixs(i,:);
minCost = gradMag;
minpath_id = i;
% shall we quit to save time???
break;
end
end
% compute visitOrder
disp('chosen path number:');
disp(minpath_id);
if minpath_id == -1
disp('HamPath configuration error!');
disp('Cannot generate exitPixs!');
needPartition = true;
end
% if isempty(hamPath)% Status == 0
% disp('HamPath Status Error!');
% end
else
disp('Cannot generate exitPixs!');
needPartition = true;
visitOrder = [];
LT = [];
exitPix = [];
end
% in case we cannot find a path in vol of 4*4*4, we have to do
% partitioning.
if needPartition && w == 4 && h == 4 && d == 4
[Status, LT, visitOrder, exitPix] = hamPathPartitionGrid3D(V, entryPix, exitFace);
if Status == 0
disp('HamPath Status Error!');
end
return;
end
end