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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
|
#include "cp_types.h"
#include "cp_proto.h"
/* layer_decompose.c
Idea is to take given complex and break it into sub-complexes.
Central granule starts at alpha. Then take circles in generations
i to i+n as interior; for next grain, start with i=i+n-m, giving
an overlap of m generations. Use mx to try to keep size from getting
too out of bounds; stop once pack has gone over mx interior
vertices (after at least n/2 generations).
I build the generations here in order to load them into the
pl structure in order -- approximately the same order they will
be laid out in a fix operation.
Return 0 on error, otherwise, grain_count and pass back pointer
to array of p_light structures built.
Caution: these light packings may fail to be simply connected,
or even connected, may have poor properties (bdry length
to area), etc. We might refine the process later.
*/
int layer_decompose(struct p_data *p,struct p_light **grains,
int spread,int overlp,int mx,int max_grains)
{
int i,j,k,m,w,v,stop,done=0,grain_count=0;
int hold_gen=1,start_gen=1,gen_num=2;
int vert_count,old_vert_count,local_gen_count,vcount,tick;
int *utility=NULL;
struct p_light *pl;
struct Vertlist *holdlist=NULL,*new_pack_verts=NULL,*genlist=NULL,
*vertlist=NULL;
struct Vertlist *vtrace,*ntrace,*htrace,*gtrace;
struct K_data *pK_ptr;
if (!p->status || spread<3) return 0;
overlp=(overlp>((spread-1)/2)) ? (spread-1)/2 : overlp;
pK_ptr=p->packK_ptr;
for (i=1;i<=p->nodecount;i++) pK_ptr[i].util_flag=0;
/* do central granule starting at alpha
we use various dynamic linked lists:
- new_pack_verts: new light packing interiors, picked off in order
- holdlist: the list to get started on next grain
- genlist: things in previous generation
- vertlist: things added to new generation
*/
genlist=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
genlist->v=p->alpha;
pK_ptr[p->alpha].util_flag=1;
/* =================== main outer loop, new grains ======= */
while (!done && grain_count<max_grains)
{
start_gen=hold_gen+1;
local_gen_count=1;
vert_count=0;
new_pack_verts=ntrace=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
if (grain_count==0)
{
ntrace=ntrace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
ntrace->v=p->alpha;
vert_count=1;
}
stop=0;
while (!stop) /* keep adding next generation */
{
old_vert_count=vert_count;
vertlist=genlist; /* process old list */
genlist=gtrace=(struct Vertlist *) /* create new list */
calloc((size_t)1,sizeof(struct Vertlist));
do
{
v=vertlist->v;
for (i=0;i<=pK_ptr[v].num;i++)
if (!pK_ptr[(j=pK_ptr[v].flower[i])].util_flag)
{
gtrace=gtrace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
gtrace->v=j;
pK_ptr[j].util_flag=gen_num;
if (!pK_ptr[j].bdry_flag)
{
ntrace=ntrace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
ntrace->v=j;
vert_count++;
}
}
vtrace=vertlist; /* throw old away as used */
vertlist=vertlist->next;
free(vtrace);
}
while (vertlist);
gtrace=genlist;
genlist=genlist->next; /* first position was empty */
free(gtrace);
local_gen_count++;
gen_num++;
/* have to save latest genlist for starting next grain */
if (local_gen_count==(spread-overlp))
{
hold_gen=gen_num-1;
if (overlp==0) /* use last genlist */
{
holdlist=genlist;
genlist=NULL;
}
else /* have to store new copy of genlist */
{
holdlist=htrace=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
gtrace=genlist;
while(gtrace)
{
htrace=htrace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
htrace->v=gtrace->v;
gtrace=gtrace->next;
}
htrace=holdlist; /* first spot not used */
holdlist=holdlist->next;
free(htrace);
}
}
/* done with this grain? */
if (local_gen_count==spread
|| !genlist
|| (vert_count==old_vert_count)
|| (vert_count>mx && local_gen_count>(spread/2)))
{
stop=1;
if (!holdlist && genlist) /* should be able to continue
next grain */
{
holdlist=genlist;
hold_gen=gen_num-1;
}
if (vert_count==old_vert_count) done=1; /* no more grains
to build */
}
} /* end of while, adding to current grain */
ntrace=new_pack_verts; /* first wasn't used */
new_pack_verts=new_pack_verts->next;
free(ntrace);
/* record the light packing */
if ((vcount=vert_count))
{
utility=(int *)calloc((size_t)(p->nodecount+1),sizeof(int));
grains[grain_count]=pl=(struct p_light *)
calloc((size_t)1,sizeof(struct p_light));
pl->counts=(int *)calloc((size_t)5,sizeof(int));
pl->counts[1]=p->hes;
pl->counts[2]=vert_count;
pl->counts[4]=p->nodecount;
for (i=1;i<=p->nodecount;i++)
utility[i]=0;
/* label interior, count var_indices size */
ntrace=new_pack_verts;
tick=1;
while (ntrace)
{
v=ntrace->v;
utility[v]=tick++;
pl->counts[3] += pK_ptr[v].num+1;
ntrace=ntrace->next;
}
if (tick!=(vert_count+1))
goto SCREWUP;
/* label/count bdry */
ntrace=new_pack_verts;
while (ntrace)
{
v=ntrace->v;
for (j=0;j<=pK_ptr[v].num;j++)
if (!utility[(k=pK_ptr[v].flower[j])])
{
vcount++;
utility[k]=-vcount;
}
ntrace=ntrace->next;
}
vert_free(&new_pack_verts); /* don't need this any longer */
new_pack_verts=NULL;
pl->counts[0]=vcount;
pl->radii=(double *)
calloc((size_t)(pl->counts[0]+1),sizeof(double));
pl->orig_indices=(int *)
calloc((size_t)(pl->counts[0]+1),sizeof(int));
/* fill various data vectors */
pl->var_indices=(int *)
calloc((size_t)(pl->counts[3]+1),sizeof(int));
tick=1;
for (i=1;i<=p->nodecount;i++)
{
k=utility[i];
if (k>0) /* interior */
{
pl->var_indices[tick++]=pK_ptr[i].num;
/* create flower list. Note: every flower should be
interior, so don't record the redundant last
petal index. */
for (j=0;j<pK_ptr[i].num;j++)
{
w=pK_ptr[i].flower[j];
if (!(m=utility[w]))
goto SCREWUP; /* every petal should be an
interior or bdry, hence >0
or <0 util_flag, resp. */
m = (m<0) ? -m : m;
pl->var_indices[tick++] = m;
}
pl->radii[k]=p->packR_ptr[i].rad;
pl->orig_indices[k]=i;
}
else if (k<0) /* bdry */
{
pl->radii[-k]=p->packR_ptr[i].rad;
pl->orig_indices[-k]=i;
}
}
free(utility);utility=NULL;
/* debug */
printf("Grain %d: area %d, interiors %d; "
"generations %d-%d\n",
grain_count,(grains[grain_count])->counts[0],
(grains[grain_count])->counts[2],start_gen-1,gen_num-1);
} /* finished storing grain */
grain_count++;
/* get ready for next grain; reset util_flag, gen_num */
for (i=1;i<=p->nodecount;i++)
if (pK_ptr[i].util_flag>hold_gen)
pK_ptr[i].util_flag=0;
gen_num=hold_gen+1;
genlist=holdlist;
holdlist=NULL;
} /* end of while, creating new grains */
if (utility) free(utility);
return grain_count;
SCREWUP:
for (i=1;i<=grain_count;i++)
{
free_p_light(&(grains[i]));
grains[i]=NULL;
}
if (utility) free(utility);
printf("layer_decompose failed for some reason.\n");
return 0;
} /* layer_decompose */
|