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
|
#include "cp_types.h"
#include "cp_proto.h"
/* "Blending" refers to the attachment of one packing to another,
generally with some overlap where a smooth transition in radii
and centers from one pack to the other can be made. (Eg., packing
'islands' generated with PlugPack or "mending" a flaw.) */
int match(struct p_data *p,struct p_data *q,int v1,int v2,
int w1,int w2,double *err,int *err_flag,Mobius *M)
/* Find mobius M putting pack p in register with q. Both packs
hyp or eucl. Apply 'best' automorphism to line up centers
of designated vertices: v1 <--> w1, v2 <--> w2. In hyp case,
all centers on unit circle or interior to disc. Return 0 on error.
Send back err and increment err_flag if there's a mobius error.
(Eventually may want 'best' automorphism for lining up 3 pairs.) */
{
int err_hit=0;
double cut;
complex a1,a2,b1,b2;
*err=0.0;
if (!p->status || !q->status || p->hes>0
|| v1 < 1 || v2 < 1 || v1 > p->nodecount || v2 > p->nodecount
|| w1 < 1 || w2 < 1 || w1 > q->nodecount || w2 > q->nodecount)
return 0;
if (p->hes<0) /* hyperbolic automorphism */
{
if (q->hes>=0) return 0;
a1=p->packR_ptr[v1].center;
a2=p->packR_ptr[v2].center;
b1=q->packR_ptr[w1].center;
b2=q->packR_ptr[w2].center;
cut=1-m_toler;
if (cAbs(a1)>cut && cAbs(a2)>cut && cAbs(b1)>cut && cAbs(b2)>cut)
/* all on unit circle */
*M=trans_abAB(a1,a2,b1,b2,&err_hit);
else if
(cAbs(a1)<=cut && cAbs(a2)<=cut && cAbs(b1)<=cut && cAbs(b2)<=cut)
/* all interior */
*M=auto_abAB(a1,a2,b1,b2,err,&err_hit);
else
{
sprintf(msgbuf,"match: data not suitable.");
emsg();
return 0;
}
if (err_hit)
{
(*err_flag)++;
return 0;
}
return 1;
}
if (p->hes>=0) /* eucl automorphism */
{
if (q->hes<0) return 0;
a1=p->packR_ptr[v1].center;
a2=p->packR_ptr[v2].center;
b1=q->packR_ptr[w1].center;
b2=q->packR_ptr[w2].center;
*M=affine_mob(a1,a2,b1,b2,&err_hit);
if (err_hit)
{
(*err_flag)++;
return 0;
}
return 1;
}
return 1;
} /* match */
int comb_bdry_antip(struct p_data *p,int *v,int *w)
/* Given bdry vert v, find bdry vert w in same bdry component
which is combinatorially 'opposite' v. Return 0 on error, eg. bdry
component length < 4; else return distance of v to w along bdry. */
{
int i,n,vv,count=0;
struct K_data *pK_ptr;
pK_ptr=p->packK_ptr;
vv=*v;
if (vv<1 || vv>p->nodecount || !pK_ptr[vv].bdry_flag)
/* improper vert? use first bdry vert encountered */
{
vv=0;
for (i=1;i<=p->nodecount;i++)
if (pK_ptr[i].bdry_flag) {vv=i;i=p->nodecount+1;}
if (!vv) return 0;
*v=vv;
}
if (!(count=bdry_comp_count(p,(*v))) || count<4 )
return 0;
n=(int)(count/2);
*w=*v;
for (i=1;i<=n;i++) (*w)=pK_ptr[(*w)].flower[0];
return n;
} /* comb_bdry_antip */
int blend(struct p_data *p,struct p_data *q,int bdry_vert,int depth)
/* Blend pack q centers/radii with pack p centers/radii, putting
result in pack p. (Assume both p, q have been packed.) The vertex_map
of q will be used to identify circles of q with the corresponding
circles of p.
bdry_vert is a bdry_vert of q; it and its bdry antipital will be used
for registration purposes, and the resulting mobius is applied to pack
q. Presumably the packing combinatorics are such that they overlap in
a certain combinatorial annulus; 'depth' indicates how many generations
(counting done in q) are used to smoothly blend the centers of p with
those of q -- the closer to bdry q, the more heavily the centers of p
are weighted. Depth 1 means just line up bdry_vert and its antipital;
depth < 0 means allow largest possible depth.
Return number of generations blended (may be less than depth). Return
0 on error. */
{
int i,hits,v,w,V,W,err_flag=0,*genlist=NULL;
int *maplist,max_depth,tv,vert_count;
double err,factor=0.0,ofactor=1.0;
char *endptr,buf[32];
Mobius M;
struct Vertlist *vertlist=NULL,*trace,*bdrylist=NULL,*vtrace;
struct Edgelist *etrace;
struct K_data *pK_ptr,*qK_ptr;
struct R_data *pR_ptr,*qR_ptr;
pK_ptr=p->packK_ptr;pR_ptr=p->packR_ptr;
qK_ptr=q->packK_ptr;qR_ptr=q->packR_ptr;
if (!p->status || !q->status || !q->vertex_map) return 0;
v=bdry_vert;
/* find bdry verts to match for registering packings */
if (!comb_bdry_antip(q,&v,&w)
|| (V=vertex_translation(q->vertex_map,v))<=0
|| (W=vertex_translation(q->vertex_map,w))<=0)
return 0; /* if v was not adequate, it was changed in this call */
/* find and apply Mobius to get q in register with p. */
if (!match(q,p,v,w,V,W,&err,&err_flag,&M) || err_flag
|| !(bdrylist=Node_link_parse(q,"b",&endptr,&hits,
&Vlist,&Elist,&Flist,®ion,pathlist,pathlength)) )
return 0;
apply_Mobius(q,"a",1,M);
/* get list with generation labels */
for (i=1;i<=p->nodecount;i++) pK_ptr[i].util_flag=0;
vtrace=bdrylist;
while (vtrace)
{
pK_ptr[vtrace->v].util_flag=1;
vtrace=vtrace->next;
}
vert_free(&bdrylist);
if (!(genlist=label_generations(q,depth,&hits,&vert_count)))
return 0;
/* for efficiency, put vertex_map in vector. */
maplist=(int *)calloc((size_t)(q->nodecount+1),sizeof(int));
etrace=q->vertex_map;
while (etrace)
{
maplist[etrace->v]=etrace->w;
etrace=etrace->next;
}
/* what is actual number of generations overlap? (up to 'depth'). */
max_depth=q->nodecount;
for (i=1;i<=q->nodecount;i++)
{
qK_ptr[i].mark=0;
if (genlist[i]>0 && genlist[i]<=max_depth && maplist[i]==0)
/* vert of q in this generation does have corresp. vert in p */
max_depth=genlist[i]-1;
else qK_ptr[i].mark=genlist[i]; /* record gen in mark in case
we need it later. */
}
if (max_depth<1) {free(genlist);return 0;} /* bdry doesn't overlap? */
if (depth<0) depth=max_depth;
if (max_depth<depth) depth=max_depth;
free(genlist);
/* now set centers of p circles in overlap by going successively
through generations in q and weighting their centers with
centers already in p. */
for (i=1;i<=depth;i++)
{
sprintf(buf,"{c:m=%d}",i);
if (!(vertlist=Node_link_parse(q,buf,&endptr,&hits,
&Vlist,&Elist,&Flist,®ion,pathlist,pathlength)))
/* should have verts in every generation up to depth */
{free(maplist);return 0;}
trace=vertlist;
if (depth>1) factor=(double)(i-1)/(double)(depth-1);
ofactor=1.0-factor;
while (trace)
{
if (!(tv=maplist[trace->v]) || tv>p->nodecount)
{
vert_free(&vertlist);
free(maplist);
return 0; /* failed translation */
}
pR_ptr[tv].center.re=
ofactor*pR_ptr[tv].center.re+
factor*qR_ptr[trace->v].center.re;
pR_ptr[tv].center.im=
ofactor*pR_ptr[tv].center.im+
factor*qR_ptr[trace->v].center.im;
pR_ptr[tv].rad=ofactor*pR_ptr[tv].rad+
factor*qR_ptr[trace->v].rad;
trace=trace->next;
}
vert_free(&vertlist);
}
/* finally, for all the rest of the vertices of q, map their
centers/radii over to p without change */
for (i=1;i<=q->nodecount;i++)
{
if ((qK_ptr[i].mark>depth || !qK_ptr[i].mark)
&& (tv=maplist[i]) && tv<=p->nodecount)
{
pR_ptr[tv].center=qR_ptr[i].center;
pR_ptr[tv].rad=qR_ptr[i].rad;
}
}
free(maplist);
return 1;
} /* blend */
|