1 /* Copyright (C) 2000-2012 by George Williams */
2 /*
3 * Redistribution and use in source and binary forms, with or without
4 * modification, are permitted provided that the following conditions are met:
5
6 * Redistributions of source code must retain the above copyright notice, this
7 * list of conditions and the following disclaimer.
8
9 * Redistributions in binary form must reproduce the above copyright notice,
10 * this list of conditions and the following disclaimer in the documentation
11 * and/or other materials provided with the distribution.
12
13 * The name of the author may not be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
19 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include <fontforge-config.h>
29
30 #include "search.h"
31
32 #include "cvundoes.h"
33 #include "fontforgevw.h"
34 #include "fvfonts.h"
35 #include "splineutil.h"
36 #include "splineutil2.h"
37 #include "ustring.h"
38 #include "utype.h"
39
40 #include <math.h>
41
CoordMatches(real real_off,real search_off,SearchData * s)42 static int CoordMatches(real real_off, real search_off, SearchData *s) {
43 if ( real_off >= search_off-s->fudge && real_off <= search_off+s->fudge )
44 return( true );
45 real fudge = fabs(s->fudge_percent*search_off);
46 return real_off >= search_off-fudge && real_off <= search_off+fudge;
47 }
48
BPMatches(BasePoint * sc_p1,BasePoint * sc_p2,BasePoint * p_p1,BasePoint * p_p2,int flip,real rot,real scale,SearchData * s)49 static int BPMatches(BasePoint *sc_p1,BasePoint *sc_p2,BasePoint *p_p1,BasePoint *p_p2,
50 int flip,real rot, real scale,SearchData *s) {
51 real sxoff = sc_p1->x-sc_p2->x;
52 real syoff = sc_p1->y-sc_p2->y;
53 real pxoff = p_p1->x-p_p2->x;
54 real pyoff = p_p1->y-p_p2->y;
55 if ( flip&1 )
56 sxoff = -sxoff;
57 if ( flip&2 )
58 syoff = -syoff;
59 sxoff *= scale;
60 syoff *= scale;
61 if ( rot==0 )
62 return( CoordMatches(sxoff,pxoff,s) && CoordMatches(syoff,pyoff,s));
63
64 return( CoordMatches(sxoff*s->matched_co+syoff*s->matched_si,pxoff,s) &&
65 CoordMatches(-sxoff*s->matched_si+syoff*s->matched_co,pyoff,s) );
66 }
67
SPMatchesF(SplinePoint * sp,SearchData * s,SplineSet * path,SplinePoint * sc_path_first,int substring)68 static int SPMatchesF(SplinePoint *sp, SearchData *s, SplineSet *path,
69 SplinePoint *sc_path_first, int substring ) {
70 SplinePoint *sc_sp, *nsc_sp, *p_sp, *np_sp;
71 int flip, flipmax;
72 bigreal rot, scale;
73 int saw_sc_first = false, first_of_path;
74 BasePoint p_unit, pend_unit, sc_unit;
75 bigreal len, temp;
76
77 s->matched_sp = sp;
78 s->matched_rot = 0;
79 s->matched_scale = 1.0;
80 s->matched_flip = flip_none;
81 s->matched_co = 1; s->matched_si=0;
82
83 first_of_path = true;
84 p_sp = path->first;
85 if ( s->endpoints ) {
86 SplinePoint *p_prevsp = p_sp;
87 SplinePoint *psc_sp;
88 p_sp = p_sp->next->to;
89 p_unit.x = p_sp->me.x - p_prevsp->me.x; p_unit.y = p_sp->me.y - p_prevsp->me.y;
90 len = sqrt(p_unit.x*p_unit.x + p_unit.y*p_unit.y);
91 if ( len==0 )
92 return( false );
93 p_unit.x /= len; p_unit.y /= len;
94 if ( sp->prev==NULL )
95 return( false );
96 psc_sp = sp->prev->from;
97 if ( (sp->me.x-psc_sp->me.x)*(sp->me.x-psc_sp->me.x) +
98 (sp->me.y-psc_sp->me.y)*(sp->me.y-psc_sp->me.y) < len*len )
99 return( false );
100 }
101 if ( s->endpoints ) {
102 SplinePoint *p_nextsp = path->last;
103 SplinePoint *p_end = p_nextsp->prev->from;
104 if ( sp->next==NULL )
105 return( false );
106 for ( p_end = p_sp, p_nextsp = p_end->next->to, sc_sp = sp, nsc_sp=sp->next->to ;; ) {
107 if ( p_nextsp->next==NULL )
108 break;
109 if ( nsc_sp->next==NULL )
110 return( false );
111 p_end = p_nextsp;
112 sc_sp = nsc_sp;
113 p_nextsp = p_nextsp->next->to;
114 nsc_sp = nsc_sp->next->to;
115 }
116 pend_unit.x = p_nextsp->me.x - p_end->me.x; pend_unit.y = p_nextsp->me.y - p_end->me.y;
117 len = sqrt(pend_unit.x*pend_unit.x + pend_unit.y*pend_unit.y);
118 if ( len==0 )
119 return( false );
120 pend_unit.x /= len; pend_unit.y /= len;
121 if ( (sp->me.x-nsc_sp->me.x)*(sp->me.x-nsc_sp->me.x) +
122 (sp->me.y-nsc_sp->me.y)*(sp->me.y-nsc_sp->me.y) < len*len )
123 return( false );
124 }
125
126 /* ******************* Match with no transformations applied **************** */
127 first_of_path = true;
128 for (sc_sp=sp; ; ) {
129 if ( sc_sp->ticked ) /* Don't search within stuff we have just replaced */
130 return( false );
131
132 if ( p_sp->next==NULL ) {
133 if ( substring || sc_sp->next==NULL ) {
134 s->last_sp = saw_sc_first ? NULL : sp;
135 return( true );
136 }
137 break;
138 }
139 np_sp = p_sp->next->to;
140 if ( sc_sp->next==NULL )
141 break;
142 nsc_sp = sc_sp->next->to;
143
144 if ( first_of_path && s->endpoints ) {
145 SplinePoint *sc_prevsp;
146 if ( sc_sp->prev==NULL )
147 return( false );
148 sc_prevsp = sc_sp->prev->from;
149 if ( !p_sp->noprevcp ) {
150 if ( sc_sp->noprevcp )
151 return( false );
152 if ( !CoordMatches(sc_sp->prevcp.x-sc_sp->me.x,p_sp->prevcp.x-p_sp->me.x,s) ||
153 !CoordMatches(sc_sp->prevcp.y-sc_sp->me.y,p_sp->prevcp.y-p_sp->me.y,s) )
154 break; /* prev control points do not match, give up */
155 } else {
156 if ( !sc_sp->noprevcp )
157 return( false );
158 sc_unit.x = sc_sp->me.x - sc_prevsp->me.x; sc_unit.y = sc_sp->me.y - sc_prevsp->me.y;
159 len = sqrt(sc_unit.x*sc_unit.x + sc_unit.y*sc_unit.y );
160 if ( len==0 )
161 return( false );
162 sc_unit.x /= len; sc_unit.y /= len;
163 if ( !RealNear(sc_unit.x,p_unit.x) || !RealNear(sc_unit.y,p_unit.y))
164 break;
165 }
166 first_of_path = false;
167 }
168 if ( np_sp->next==NULL && s->endpoints ) {
169 SplinePoint *sc_nextsp;
170 if ( sc_sp->next==NULL )
171 return( false );
172 sc_nextsp = sc_sp->next->to;
173 if ( !p_sp->nonextcp ) {
174 if ( !CoordMatches(sc_sp->nextcp.x-sc_sp->me.x,p_sp->nextcp.x-p_sp->me.x,s) ||
175 !CoordMatches(sc_sp->nextcp.y-sc_sp->me.y,p_sp->nextcp.y-p_sp->me.y,s) )
176 break; /* prev control points do not match, give up */
177 } else {
178 if ( !sc_sp->nonextcp )
179 return( false );
180 sc_unit.x = sc_nextsp->me.x - sc_sp->me.x; sc_unit.y = sc_nextsp->me.y - sc_sp->me.y;
181 len = sqrt(sc_unit.x*sc_unit.x + sc_unit.y*sc_unit.y );
182 if ( len==0 )
183 return( false );
184 sc_unit.x /= len; sc_unit.y /= len;
185 if ( RealNear(sc_unit.x,pend_unit.x) && RealNear(sc_unit.y,pend_unit.y)) {
186 s->last_sp = saw_sc_first ? NULL : sp;
187 return( true );
188 } else
189 break;
190 }
191 }
192
193 if ( !CoordMatches(sc_sp->nextcp.x-sc_sp->me.x,p_sp->nextcp.x-p_sp->me.x,s) ||
194 !CoordMatches(sc_sp->nextcp.y-sc_sp->me.y,p_sp->nextcp.y-p_sp->me.y,s) ||
195 !CoordMatches(nsc_sp->me.x-sc_sp->me.x,np_sp->me.x-p_sp->me.x,s) ||
196 !CoordMatches(nsc_sp->me.y-sc_sp->me.y,np_sp->me.y-p_sp->me.y,s) ||
197 !CoordMatches(nsc_sp->prevcp.x-nsc_sp->me.x,np_sp->prevcp.x-np_sp->me.x,s) ||
198 !CoordMatches(nsc_sp->prevcp.y-nsc_sp->me.y,np_sp->prevcp.y-np_sp->me.y,s) )
199 break;
200 if ( np_sp==path->first ) {
201 if ( nsc_sp==sp ) {
202 s->last_sp = saw_sc_first ? NULL : sp;
203 return( true );
204 }
205 break;
206 }
207 sc_sp = nsc_sp;
208 if ( sc_sp == sc_path_first )
209 saw_sc_first = true;
210 p_sp = np_sp;
211 }
212
213 /* ************** Match with just flip transformations applied ************** */
214 if ( s->tryflips ) for ( flip=flip_x ; flip<=flip_xy; ++flip ) {
215 int xsign = (flip&1) ? -1 : 1, ysign = (flip&2) ? -1 : 1;
216 saw_sc_first = false;
217 p_sp = s->endpoints ? path->first->next->to : path->first;
218 first_of_path = true;
219 for (sc_sp=sp; ; ) {
220 if ( p_sp->next==NULL ) {
221 if ( substring || sc_sp->next==NULL ) {
222 s->matched_flip = flip;
223 s->last_sp = saw_sc_first ? NULL : sp;
224 return( true );
225 } else
226 break;
227 }
228 np_sp = p_sp->next->to;
229 if ( sc_sp->next==NULL )
230 break;
231 nsc_sp = sc_sp->next->to;
232
233 if ( first_of_path && s->endpoints ) {
234 SplinePoint *sc_prevsp;
235 /* if ( sc_sp->prev==NULL )*/ /* Already checked this above */
236 sc_prevsp = sc_sp->prev->from;
237 if ( !p_sp->noprevcp ) {
238 if ( !CoordMatches(sc_sp->prevcp.x-sc_sp->me.x,xsign*(p_sp->prevcp.x-p_sp->me.x),s) ||
239 !CoordMatches(sc_sp->prevcp.y-sc_sp->me.y,ysign*(p_sp->prevcp.y-p_sp->me.y),s) )
240 break; /* prev control points do not match, give up */
241 } else {
242 sc_unit.x = sc_sp->me.x - sc_prevsp->me.x; sc_unit.y = sc_sp->me.y - sc_prevsp->me.y;
243 len = sqrt(sc_unit.x*sc_unit.x + sc_unit.y*sc_unit.y );
244 sc_unit.x /= len; sc_unit.y /= len;
245 if ( !RealNear(sc_unit.x,xsign * p_unit.x) || !RealNear(sc_unit.y,ysign*p_unit.y))
246 break;
247 }
248 first_of_path = false;
249 }
250 if ( np_sp->next==NULL && s->endpoints ) {
251 SplinePoint *sc_nextsp;
252 if ( sc_sp->next==NULL )
253 return( false );
254 sc_nextsp = sc_sp->next->to;
255 if ( !p_sp->nonextcp ) {
256 if ( !CoordMatches(sc_sp->nextcp.x-sc_sp->me.x,xsign*(p_sp->nextcp.x-p_sp->me.x),s) ||
257 !CoordMatches(sc_sp->nextcp.y-sc_sp->me.y,ysign*(p_sp->nextcp.y-p_sp->me.y),s) )
258 break; /* prev control points do not match, give up */
259 } else {
260 if ( !sc_sp->nonextcp )
261 return( false );
262 sc_unit.x = sc_nextsp->me.x - sc_sp->me.x; sc_unit.y = sc_nextsp->me.y - sc_sp->me.y;
263 len = sqrt(sc_unit.x*sc_unit.x + sc_unit.y*sc_unit.y );
264 if ( len==0 )
265 return( false );
266 sc_unit.x /= len; sc_unit.y /= len;
267 if ( RealNear(sc_unit.x,xsign*pend_unit.x) && RealNear(sc_unit.y,ysign*pend_unit.y)) {
268 s->matched_flip = flip;
269 s->last_sp = saw_sc_first ? NULL : sp;
270 return( true );
271 } else
272 break;
273 }
274 }
275
276 if ( !CoordMatches(sc_sp->nextcp.x-sc_sp->me.x,xsign*(p_sp->nextcp.x-p_sp->me.x),s) ||
277 !CoordMatches(sc_sp->nextcp.y-sc_sp->me.y,ysign*(p_sp->nextcp.y-p_sp->me.y),s) ||
278 !CoordMatches(nsc_sp->me.x-sc_sp->me.x,xsign*(np_sp->me.x-p_sp->me.x),s) ||
279 !CoordMatches(nsc_sp->me.y-sc_sp->me.y,ysign*(np_sp->me.y-p_sp->me.y),s) ||
280 !CoordMatches(nsc_sp->prevcp.x-nsc_sp->me.x,xsign*(np_sp->prevcp.x-np_sp->me.x),s) ||
281 !CoordMatches(nsc_sp->prevcp.y-nsc_sp->me.y,ysign*(np_sp->prevcp.y-np_sp->me.y),s) )
282 break;
283 if ( np_sp==path->first ) {
284 if ( nsc_sp==sp ) {
285 s->matched_flip = flip;
286 s->last_sp = saw_sc_first ? NULL : sp;
287 return( true );
288 } else
289 break;
290 }
291 sc_sp = nsc_sp;
292 if ( sc_sp == sc_path_first )
293 saw_sc_first = true;
294 p_sp = np_sp;
295 }
296 }
297
298 /* ******* Match with rotate, scale and flip transformations applied ******** */
299 if ( s->tryrotate || s->tryscale ) {
300 if ( s->tryflips )
301 flipmax = flip_xy;
302 else
303 flipmax = flip_none;
304 for ( flip=flip_none ; flip<=flipmax; ++flip ) {
305 p_sp = s->endpoints ? path->first->next->to : path->first;
306 np_sp = p_sp->next->to; /* if p_sp->next were NULL, we'd have returned by now */
307 sc_sp = sp;
308 if ( sc_sp->next==NULL )
309 return( false );
310 nsc_sp = sc_sp->next->to;
311 if ( p_sp->me.x==np_sp->me.x && p_sp->me.y==np_sp->me.y )
312 return( false );
313 if ( sc_sp->me.x==nsc_sp->me.x && sc_sp->me.y==nsc_sp->me.y )
314 return( false );
315 if ( s->tryrotate && s->endpoints && np_sp->next == NULL ) {
316 int xsign = (flip&1)?-1:1, ysign=(flip&2)?-1:1;
317 if ( !p_sp->noprevcp ) {
318 rot = atan2(xsign*(sc_sp->me.y-sc_sp->prevcp.y),ysign*(sc_sp->me.x-sc_sp->prevcp.x)) -
319 atan2( p_sp->me.y- p_sp->prevcp.y, p_sp->me.x- p_sp->prevcp.x);
320 } else {
321 rot = atan2(xsign*(sc_unit.y),ysign*(sc_unit.x)) -
322 atan2( p_unit.y, p_unit.x);
323 }
324 scale = 1;
325 } else if ( s->endpoints && np_sp->next == NULL ) {
326 return( false ); /* Not enough info to make a guess */
327 } else if ( !s->tryrotate ) {
328 if ( p_sp->me.x==np_sp->me.x )
329 scale = (np_sp->me.y-p_sp->me.y) / (nsc_sp->me.y-sc_sp->me.y);
330 else if ( p_sp->me.y==np_sp->me.y )
331 scale = (np_sp->me.x-p_sp->me.x) / (nsc_sp->me.x-sc_sp->me.x);
332 else {
333 real yscale = (np_sp->me.y-p_sp->me.y) / (nsc_sp->me.y-sc_sp->me.y);
334 scale = (np_sp->me.x-p_sp->me.x) / (nsc_sp->me.x-sc_sp->me.x);
335 if ( scale<.99*yscale || scale>1.01*yscale )
336 return( false );
337 }
338 rot = 0;
339 } else {
340 int xsign = (flip&1)?-1:1, ysign=(flip&2)?-1:1;
341 rot = atan2(xsign*(nsc_sp->me.y-sc_sp->me.y),ysign*(nsc_sp->me.x-sc_sp->me.x)) -
342 atan2(np_sp->me.y-p_sp->me.y,np_sp->me.x-p_sp->me.x);
343 if ( !s->tryscale )
344 scale = 1;
345 else
346 scale = sqrt( ((np_sp->me.y-p_sp->me.y)*(np_sp->me.y-p_sp->me.y) +
347 (np_sp->me.x-p_sp->me.x)*(np_sp->me.x-p_sp->me.x))/
348 ((nsc_sp->me.y-sc_sp->me.y)*(nsc_sp->me.y-sc_sp->me.y) +
349 (nsc_sp->me.x-sc_sp->me.x)*(nsc_sp->me.x-sc_sp->me.x)) );
350 }
351 if ( scale>-.00001 && scale<.00001 )
352 return( false );
353 s->matched_rot = rot;
354 if ( rot==0 )
355 s->matched_co=1,s->matched_si=0;
356 else if ( rot>3.14159 && rot<3.141595 )
357 s->matched_co=-1,s->matched_si=0;
358 else if ( rot>1.570793 && rot<1.570799 )
359 s->matched_co=0,s->matched_si=1;
360 else if ( (rot>4.712386 && rot<4.712392 ) ||
361 (rot<-1.570793 && rot>-1.570799 ) )
362 s->matched_co=0,s->matched_si=-1;
363 else
364 s->matched_co = cos(rot), s->matched_si = sin(rot);
365 saw_sc_first = false;
366 first_of_path = true;
367 for (sc_sp=sp ; ; ) {
368 if ( p_sp->next==NULL ) {
369 if ( substring || sc_sp->next==NULL ) {
370 s->matched_flip = flip;
371 s->matched_rot = rot;
372 s->matched_scale = scale;
373 s->last_sp = saw_sc_first ? NULL : sp;
374 return( true );
375 } else
376 return( false );
377 }
378 np_sp = p_sp->next->to;
379 if ( sc_sp->next==NULL )
380 return( false );
381 nsc_sp = sc_sp->next->to;
382
383 if ( first_of_path && s->endpoints ) {
384 SplinePoint *sc_prevsp;
385 /* if ( sc_sp->prev==NULL )*/ /* Already checked this above */
386 sc_prevsp = sc_sp->prev->from;
387 if ( !p_sp->noprevcp ) {
388 if ( !BPMatches(&sc_sp->prevcp,&sc_sp->me,&p_sp->prevcp,&p_sp->me,flip,rot,scale,s) )
389 break;
390 } else {
391 sc_unit.x = sc_sp->me.x - sc_prevsp->me.x; sc_unit.y = sc_sp->me.y - sc_prevsp->me.y;
392 len = sqrt(sc_unit.x*sc_unit.x + sc_unit.y*sc_unit.y );
393 sc_unit.x /= len; sc_unit.y /= len;
394 temp = sc_unit.x * s->matched_co + sc_unit.y * s->matched_si;
395 sc_unit.y = -sc_unit.x * s->matched_si + sc_unit.y * s->matched_co;
396 sc_unit.x = temp;
397 if ( !RealNear(sc_unit.x,p_unit.x) || !RealNear(sc_unit.y,p_unit.y))
398 break;
399 }
400 first_of_path = false;
401 }
402 if ( np_sp->next==NULL && s->endpoints ) {
403 SplinePoint *sc_nextsp;
404 if ( sc_sp->next==NULL )
405 return( false );
406 sc_nextsp = sc_sp->next->to;
407 if ( !p_sp->nonextcp ) {
408 if ( !BPMatches(&sc_sp->nextcp,&sc_sp->me,&p_sp->nextcp,&p_sp->me,flip,rot,scale,s) )
409 break;
410 } else {
411 if ( !sc_sp->nonextcp )
412 return( false );
413 sc_unit.x = sc_nextsp->me.x - sc_sp->me.x; sc_unit.y = sc_nextsp->me.y - sc_sp->me.y;
414 len = sqrt(sc_unit.x*sc_unit.x + sc_unit.y*sc_unit.y );
415 if ( len==0 )
416 return( false );
417 sc_unit.x /= len; sc_unit.y /= len;
418 temp = sc_unit.x * s->matched_co + sc_unit.y * s->matched_si;
419 sc_unit.y = -sc_unit.x * s->matched_si + sc_unit.y * s->matched_co;
420 sc_unit.x = temp;
421 if ( RealNear(sc_unit.x,pend_unit.x) && RealNear(sc_unit.y,pend_unit.y)) {
422 s->matched_flip = flip;
423 s->matched_rot = rot;
424 s->matched_scale = scale;
425 s->last_sp = saw_sc_first ? NULL : sp;
426 return( true );
427 } else
428 break;
429 }
430 }
431
432 if ( !BPMatches(&sc_sp->nextcp,&sc_sp->me,&p_sp->nextcp,&p_sp->me,flip,rot,scale,s) ||
433 !BPMatches(&nsc_sp->me,&sc_sp->me,&np_sp->me,&p_sp->me,flip,rot,scale,s) ||
434 !BPMatches(&nsc_sp->prevcp,&nsc_sp->me,&np_sp->prevcp,&np_sp->me,flip,rot,scale,s) )
435 return( false );
436 if ( np_sp==path->first ) {
437 if ( nsc_sp==sp ) {
438 s->matched_flip = flip;
439 s->matched_rot = rot;
440 s->matched_scale = scale;
441 s->last_sp = saw_sc_first ? NULL : sp;
442 return( true );
443 } else
444 return( false );
445 }
446 sc_sp = nsc_sp;
447 if ( sc_sp == sc_path_first )
448 saw_sc_first = true;
449 p_sp = np_sp;
450 }
451 }
452 }
453 return( false );
454 }
455
SPMatchesO(SplinePoint * sp,SearchData * s,SplineSet * path)456 static int SPMatchesO(SplinePoint *sp, SearchData *s, SplineSet *path) {
457 SplinePoint *sc_sp, *nsc_sp, *p_sp, *np_sp;
458
459 s->matched_sp = sp;
460 if ( s->matched_rot==0 && s->matched_scale==1 && s->matched_flip==flip_none ) {
461 for (sc_sp=sp, p_sp=path->first; ; ) {
462 if ( p_sp->next==NULL )
463 return( sc_sp->next==NULL );
464 np_sp = p_sp->next->to;
465 if ( sc_sp->next==NULL )
466 return( false );
467 nsc_sp = sc_sp->next->to;
468 if ( !CoordMatches(sc_sp->nextcp.x-sc_sp->me.x,p_sp->nextcp.x-p_sp->me.x,s) ||
469 !CoordMatches(sc_sp->nextcp.y-sc_sp->me.y,p_sp->nextcp.y-p_sp->me.y,s) ||
470 !CoordMatches(nsc_sp->me.x-sc_sp->me.x,np_sp->me.x-p_sp->me.x,s) ||
471 !CoordMatches(nsc_sp->me.y-sc_sp->me.y,np_sp->me.y-p_sp->me.y,s) ||
472 !CoordMatches(nsc_sp->prevcp.x-nsc_sp->me.x,np_sp->prevcp.x-np_sp->me.x,s) ||
473 !CoordMatches(nsc_sp->prevcp.y-nsc_sp->me.y,np_sp->prevcp.y-np_sp->me.y,s) )
474 return( false );
475 if ( np_sp==path->first )
476 return( nsc_sp==sp );
477 sc_sp = nsc_sp;
478 p_sp = np_sp;
479 }
480 } else if ( s->matched_rot==0 && s->matched_scale==1 ) {
481 int xsign = (s->matched_flip&1) ? -1 : 1, ysign = (s->matched_flip&2) ? -1 : 1;
482 for (sc_sp=sp, p_sp=path->first; ; ) {
483 if ( p_sp->next==NULL )
484 return( sc_sp->next==NULL );
485 np_sp = p_sp->next->to;
486 if ( sc_sp->next==NULL )
487 return( false );
488 nsc_sp = sc_sp->next->to;
489 if ( !CoordMatches(sc_sp->nextcp.x-sc_sp->me.x,xsign*(p_sp->nextcp.x-p_sp->me.x),s) ||
490 !CoordMatches(sc_sp->nextcp.y-sc_sp->me.y,ysign*(p_sp->nextcp.y-p_sp->me.y),s) ||
491 !CoordMatches(nsc_sp->me.x-sc_sp->me.x,xsign*(np_sp->me.x-p_sp->me.x),s) ||
492 !CoordMatches(nsc_sp->me.y-sc_sp->me.y,ysign*(np_sp->me.y-p_sp->me.y),s) ||
493 !CoordMatches(nsc_sp->prevcp.x-nsc_sp->me.x,xsign*(np_sp->prevcp.x-np_sp->me.x),s) ||
494 !CoordMatches(nsc_sp->prevcp.y-nsc_sp->me.y,ysign*(np_sp->prevcp.y-np_sp->me.y),s) )
495 return( false );
496 if ( np_sp==path->first )
497 return( nsc_sp==sp );
498 sc_sp = nsc_sp;
499 p_sp = np_sp;
500 }
501 } else {
502 p_sp = path->first;
503 for (sc_sp=sp, p_sp=path->first; ; ) {
504 if ( p_sp->next==NULL )
505 return( sc_sp->next==NULL );
506 np_sp = p_sp->next->to;
507 if ( sc_sp->next==NULL )
508 return( false );
509 nsc_sp = sc_sp->next->to;
510 if ( !BPMatches(&sc_sp->nextcp,&sc_sp->me,&p_sp->nextcp,&p_sp->me,
511 s->matched_flip,s->matched_rot,s->matched_scale,s) ||
512 !BPMatches(&nsc_sp->me,&sc_sp->me,&np_sp->me,&p_sp->me,
513 s->matched_flip,s->matched_rot,s->matched_scale,s) ||
514 !BPMatches(&nsc_sp->prevcp,&nsc_sp->me,&np_sp->prevcp,&np_sp->me,
515 s->matched_flip,s->matched_rot,s->matched_scale,s) )
516 return( false );
517 if ( np_sp==path->first )
518 return( nsc_sp==sp );
519 sc_sp = nsc_sp;
520 p_sp = np_sp;
521 }
522 }
523 return( false );
524 }
525
SVBuildTrans(SearchData * s,real transform[6])526 static void SVBuildTrans(SearchData *s,real transform[6]) {
527 memset(transform,0,sizeof(real [6]));
528 transform[0] = transform[3] = 1;
529 if ( s->matched_flip&1 )
530 transform[0] = -1;
531 if ( s->matched_flip&2 )
532 transform[3] = -1;
533 transform[0] /= s->matched_scale;
534 transform[3] /= s->matched_scale;
535 transform[1] = -transform[0]*s->matched_si;
536 transform[0] *= s->matched_co;
537 transform[2] = transform[3]*s->matched_si;
538 transform[3] *= s->matched_co;
539 transform[4] = s->matched_x;
540 transform[5] = s->matched_y;
541 }
542
SVFigureTranslation(SearchData * s,BasePoint * p,SplinePoint * sp)543 static void SVFigureTranslation(SearchData *s,BasePoint *p,SplinePoint *sp) {
544 real transform[6];
545 BasePoint res;
546
547 SVBuildTrans(s,transform);
548 res.x = transform[0]*p->x + transform[2]*p->y + transform[4];
549 res.y = transform[1]*p->x + transform[3]*p->y + transform[5];
550 s->matched_x = sp->me.x - res.x;
551 s->matched_y = sp->me.y - res.y;
552 }
553
SPMatches(SplinePoint * sp,SearchData * s,SplineSet * path,SplinePoint * sc_path_first,int oriented)554 static int SPMatches(SplinePoint *sp, SearchData *s, SplineSet *path,
555 SplinePoint *sc_path_first, int oriented ) {
556 real transform[6];
557 BasePoint *p, res;
558 if ( oriented ) {
559 double fudge = s->fudge<.1 ? 10*s->fudge : s->fudge;
560 SVBuildTrans(s,transform);
561 p = &path->first->me;
562 res.x = transform[0]*p->x + transform[2]*p->y + transform[4];
563 res.y = transform[1]*p->x + transform[3]*p->y + transform[5];
564 if ( sp->me.x>res.x+fudge || sp->me.x<res.x-fudge ||
565 sp->me.y>res.y+fudge || sp->me.y<res.y-fudge )
566 return( false );
567
568 return( SPMatchesO(sp,s,path));
569 } else {
570 if ( !SPMatchesF(sp,s,path,sc_path_first,false))
571 return( false );
572 SVFigureTranslation(s,&path->first->me,sp);
573 return( true );
574 }
575 }
576
577 /* We are given a single, unclosed path to match. It is a match if it */
578 /* corresponds to any subset of a path in the character */
SCMatchesIncomplete(SplineChar * sc,SearchData * s,int startafter)579 static int SCMatchesIncomplete(SplineChar *sc,SearchData *s,int startafter) {
580 /* don't look in refs because we can't do a replace there */
581 SplineSet *spl;
582 SplinePoint *sp;
583 int layer = s->fv->active_layer;
584
585 for ( spl=startafter?s->matched_spl:sc->layers[layer].splines; spl!=NULL; spl=spl->next ) {
586 s->matched_spl = spl;
587 for ( sp=startafter?s->last_sp:spl->first; sp!=NULL; ) {
588 if ( SPMatchesF(sp,s,s->path,spl->first,true)) {
589 SVFigureTranslation(s,&s->path->first->me,sp);
590 return( true );
591 } else if ( s->tryreverse && SPMatchesF(sp,s,s->revpath,spl->first,true)) {
592 SVFigureTranslation(s,&s->revpath->first->me,sp);
593 s->wasreversed = true;
594 return( true );
595 }
596 if ( sp->next==NULL )
597 break;
598 sp = sp->next->to;
599 if ( sp==spl->first )
600 break;
601 }
602 startafter = false;
603 }
604 return( false );
605 }
606
607 /* We are given several paths/refs to match. We have a match if each path */
608 /* matches a path in the character exactly, and each ref also. A searched for*/
609 /* path can not match a subset of a path */
SCMatchesFull(SplineChar * sc,SearchData * s)610 static int SCMatchesFull(SplineChar *sc,SearchData *s) {
611 /* don't look to match paths in refs because we can't do a replace there */
612 SplineSet *spl, *s_spl, *s_r_spl;
613 SplinePoint *sp;
614 RefChar *r, *s_r;
615 int i, first, ref_first;
616 int layer = s->fv->active_layer;
617
618 s->matched_ss = s->matched_refs = s->matched_ss_start = 0;
619 first = true;
620 for ( s_r = s->sc_srch.layers[ly_fore].refs; s_r!=NULL; s_r = s_r->next ) {
621 for ( r = sc->layers[layer].refs, i=0; r!=NULL; r=r->next, ++i ) if ( !(s->matched_refs&(1<<i)) ) {
622 if ( r->sc == s_r->sc ) {
623 /* I should check the transform to see if the tryflips (etc) flags would make this not a match */
624 if ( r->transform[0]==s_r->transform[0] && r->transform[1]==s_r->transform[1] &&
625 r->transform[2]==s_r->transform[2] && r->transform[3]==s_r->transform[3] ) {
626 if ( first ) {
627 s->matched_scale = 1.0;
628 s->matched_x = r->transform[4]-s_r->transform[4];
629 s->matched_y = r->transform[5]-s_r->transform[5];
630 first = false;
631 break;
632 } else if ( r->transform[4]-s_r->transform[4]==s->matched_x &&
633 r->transform[5]-s_r->transform[5] == s->matched_y )
634 break;
635 }
636 }
637 }
638 if ( r==NULL )
639 return( false );
640 s->matched_refs |= 1<<i;
641 }
642 ref_first = first;
643
644 retry:
645 if ( ref_first )
646 s->matched_x = s->matched_y = 0;
647 s->matched_ss = s->matched_ss_start; /* Don't use any of these contours, they don't work */
648 first = ref_first;
649 for ( s_spl = s->path, s_r_spl=s->revpath; s_spl!=NULL; s_spl=s_spl->next, s_r_spl = s_r_spl->next ) {
650 for ( spl=sc->layers[layer].splines, i=0; spl!=NULL; spl=spl->next, ++i ) if ( !(s->matched_ss&(1<<i)) ) {
651 s->matched_spl = spl;
652 if ( spl->first->prev==NULL ) { /* Open */
653 if ( s_spl->first!=s_spl->last ) {
654 if ( SPMatches(spl->first,s,s_spl,spl->first,1-first))
655 break;
656 if ( s->tryreverse && SPMatches(spl->first,s,s_r_spl,spl->first,1-first)) {
657 s->wasreversed = true;
658 break;
659 }
660 }
661 } else {
662 if ( s_spl->first==s_spl->last ) {
663 int found = false;
664 for ( sp=spl->first; ; ) {
665 if ( SPMatches(sp,s,s_spl,spl->first,1-first)) {
666 found = true;
667 break;
668 }
669 if ( s->tryreverse && SPMatches(sp,s,s_r_spl,spl->first,1-first)) {
670 s->wasreversed = found = true;
671 break;
672 }
673 sp = sp->next->to;
674 if ( sp==spl->first )
675 break;
676 }
677 if ( found )
678 break;
679 }
680 }
681 }
682 if ( spl==NULL ) {
683 if ( s_spl == s->path )
684 return( false );
685 /* Ok, we could not find a match starting from the contour */
686 /* we started with. However if there are multiple contours */
687 /* in the search pattern, that might just mean that we a bad */
688 /* transform, so start from scratch and try some other contours */
689 /* but don't test anything we've already ruled out */
690 goto retry;
691 }
692 if ( s_spl == s->path ) {
693 s->matched_ss_start |= 1<<i;
694 s->matched_ss = 1<<i; /* Ok, the contours in matched_ss_start didn't work as starting points, but we still must test them with the current transform against other contours */
695 } else
696 s->matched_ss |= 1<<i;
697 first = false;
698 }
699 return( true );
700 }
701
AdjustBP(BasePoint * changeme,BasePoint * rel,BasePoint * shouldbe,BasePoint * shouldberel,BasePoint * fudge,SearchData * s)702 static int AdjustBP(BasePoint *changeme,BasePoint *rel,
703 BasePoint *shouldbe, BasePoint *shouldberel,
704 BasePoint *fudge,
705 SearchData *s) {
706 real xoff,yoff;
707
708 xoff = (shouldbe->x-shouldberel->x);
709 yoff = (shouldbe->y-shouldberel->y);
710 if ( s->matched_flip&1 )
711 xoff=-xoff;
712 if ( s->matched_flip&2 )
713 yoff =-yoff;
714 xoff *= s->matched_scale;
715 yoff *= s->matched_scale;
716 changeme->x = xoff*s->matched_co - yoff*s->matched_si + fudge->x + rel->x;
717 changeme->y = yoff*s->matched_co + xoff*s->matched_si + fudge->y + rel->y;
718 return( changeme->x==rel->x && changeme->y==rel->y );
719 }
720
AdjustAll(SplinePoint * change,BasePoint * rel,BasePoint * shouldbe,BasePoint * shouldberel,BasePoint * fudge,SearchData * s)721 static void AdjustAll(SplinePoint *change,BasePoint *rel,
722 BasePoint *shouldbe, BasePoint *shouldberel,
723 BasePoint *fudge,
724 SearchData *s) {
725 BasePoint old;
726
727 old = change->me;
728 AdjustBP(&change->me,rel,shouldbe,shouldberel,fudge,s);
729 change->nextcp.x += change->me.x-old.x; change->nextcp.y += change->me.y-old.y;
730 change->prevcp.x += change->me.x-old.x; change->prevcp.y += change->me.y-old.y;
731
732 change->nonextcp = (change->nextcp.x==change->me.x && change->nextcp.y==change->me.y);
733 change->noprevcp = (change->prevcp.x==change->me.x && change->prevcp.y==change->me.y);
734 }
735
RplInsertSP(SplinePoint * after,SplinePoint * nrpl,SplinePoint * rpl,SearchData * s,BasePoint * fudge)736 static SplinePoint *RplInsertSP(SplinePoint *after,SplinePoint *nrpl,SplinePoint *rpl,SearchData *s, BasePoint *fudge) {
737 SplinePoint *new = chunkalloc(sizeof(SplinePoint));
738 real transform[6];
739
740 SVBuildTrans(s,transform);
741 /*transform[4] += fudge->x; transform[5] += fudge->y;*/
742 new->me.x = after->me.x + transform[0]*(nrpl->me.x-rpl->me.x) + transform[1]*(nrpl->me.y-rpl->me.y) + fudge->x;
743 new->me.y = after->me.y + transform[2]*(nrpl->me.x-rpl->me.x) + transform[3]*(nrpl->me.y-rpl->me.y) + fudge->y;
744 new->nextcp.x = after->me.x + transform[0]*(nrpl->nextcp.x-rpl->me.x) + transform[1]*(nrpl->nextcp.y-rpl->me.y) + fudge->x;
745 new->nextcp.y = after->me.y + transform[2]*(nrpl->nextcp.x-rpl->me.x) + transform[3]*(nrpl->nextcp.y-rpl->me.y) + fudge->y;
746 new->prevcp.x = after->me.x + transform[0]*(nrpl->prevcp.x-rpl->me.x) + transform[1]*(nrpl->prevcp.y-rpl->me.y) + fudge->x;
747 new->prevcp.y = after->me.y + transform[2]*(nrpl->prevcp.x-rpl->me.x) + transform[3]*(nrpl->prevcp.y-rpl->me.y) + fudge->y;
748 new->nonextcp = (new->nextcp.x==new->me.x && new->nextcp.y==new->me.y);
749 new->noprevcp = (new->prevcp.x==new->me.x && new->prevcp.y==new->me.y);
750 new->pointtype = rpl->pointtype;
751 new->selected = true;
752 new->ticked = true;
753 if ( after->next==NULL ) {
754 SplineMake(after,new,after->prev->order2);
755 s->matched_spl->last = new;
756 } else {
757 SplinePoint *nsp = after->next->to;
758 after->next->to = new;
759 new->prev = after->next;
760 SplineRefigure(after->next);
761 SplineMake(new,nsp,after->next->order2);
762 }
763 return( new );
764 }
765
FudgeFigure(SearchData * s,SplineSet * path,BasePoint * fudge)766 static void FudgeFigure(SearchData *s,SplineSet *path,BasePoint *fudge) {
767 SplinePoint *search, *searchrel, *found, *foundrel;
768 real xoff, yoff;
769
770 fudge->x = fudge->y = 0;
771 if ( path->first->prev!=NULL ) /* closed path, should end where it began */
772 return; /* => no fudge */
773
774 foundrel = s->matched_sp; searchrel = path->first;
775 if ( s->endpoints ) searchrel = searchrel->next->to;
776 for ( found=foundrel, search=searchrel ; ; ) {
777 if ( found->next==NULL || search->next==NULL )
778 break;
779 if ( s->endpoints && search->next->to->next==NULL )
780 break;
781 found = found->next->to;
782 search = search->next->to;
783 }
784
785 xoff = (found->me.x-foundrel->me.x);
786 yoff = (found->me.y-foundrel->me.y);
787 if ( s->matched_flip&1 )
788 xoff=-xoff;
789 if ( s->matched_flip&2 )
790 yoff =-yoff;
791 xoff *= s->matched_scale;
792 yoff *= s->matched_scale;
793 fudge->x = xoff*s->matched_co + yoff*s->matched_si - (search->me.x-searchrel->me.x);
794 fudge->y = yoff*s->matched_co - xoff*s->matched_si - (search->me.y-searchrel->me.y);
795 }
796
DoReplaceIncomplete(SplineChar * sc,SearchData * s)797 static void DoReplaceIncomplete(SplineChar *sc,SearchData *s) {
798 SplinePoint *sc_p, *nsc_p, *p_p, *np_p, *r_p, *nr_p;
799 BasePoint fudge;
800 SplineSet *path, *rpath;
801 SplinePoint dummy; Spline dummysp;
802
803 if ( s->wasreversed ) {
804 path = s->revpath;
805 rpath = s->revreplace;
806 } else {
807 path = s->path;
808 rpath = s->replacepath;
809 }
810
811 /* Total "fudge" amount should be spread evenly over each point */
812 FudgeFigure(s,path,&fudge);
813 if ( s->pointcnt!=s->rpointcnt )
814 MinimumDistancesFree(sc->md); sc->md = NULL;
815
816 sc_p = s->matched_sp; p_p = path->first, r_p = rpath->first;
817 if ( s->endpoints ) {
818 real xoff, yoff;
819 memset(&dummy,0,sizeof(dummy));
820 memset(&dummysp,0,sizeof(dummysp));
821 dummysp.from = &dummy;
822 dummysp.to = sc_p;
823 dummysp.order2 = p_p->next->order2;
824 np_p = p_p->next->to;
825 xoff = (p_p->me.x-np_p->me.x);
826 yoff = (p_p->me.y-np_p->me.y);
827 if ( s->matched_flip&1 )
828 xoff=-xoff;
829 if ( s->matched_flip&2 )
830 yoff =-yoff;
831 xoff *= s->matched_scale;
832 yoff *= s->matched_scale;
833 dummy.me.x = sc_p->me.x + xoff*s->matched_co - yoff*s->matched_si;
834 dummy.me.y = sc_p->me.y + yoff*s->matched_co + xoff*s->matched_si;
835 dummy.nextcp = dummy.prevcp = dummy.me;
836 dummy.nonextcp = dummy.noprevcp = true;
837 dummy.next = &dummysp;
838 SplineRefigure(&dummysp);
839 sc_p = &dummy;
840 }
841 for ( ; ; ) {
842 if ( (p_p->next==NULL && r_p->next==NULL) ||
843 (s->endpoints && p_p->next->to->next==NULL && r_p->next->to->next == NULL )) {
844 s->last_sp = s->last_sp==NULL ? NULL : sc_p; /* If we crossed the contour start, move to next contour */
845 return; /* done */
846 } else if ( p_p->next==NULL || (s->endpoints && p_p->next->to->next==NULL)) {
847 /* The search pattern is shorter that the replace pattern */
848 /* Need to add some extra points */
849 nr_p = r_p->next->to;
850 sc_p = RplInsertSP(sc_p,nr_p,r_p,s,&fudge);
851 r_p = nr_p;
852 } else if ( r_p->next==NULL || (s->endpoints && r_p->next->to->next==NULL)) {
853 /* The replace pattern is shorter than the search pattern */
854 /* Need to remove some points */
855 nsc_p = sc_p->next->to;
856 if ( nsc_p->next==NULL ) {
857 SplinePointFree(nsc_p);
858 SplineFree(sc_p->next);
859 sc_p->next = NULL;
860 s->matched_spl->last = sc_p;
861 s->last_sp = s->last_sp==NULL ? NULL : sc_p;
862 return;
863 } else {
864 nsc_p = nsc_p->next->to;
865 SplinePointFree(sc_p->next->to);
866 SplineFree(sc_p->next);
867 sc_p->next = nsc_p->prev;
868 nsc_p->prev->from = sc_p;
869 SplineRefigure(nsc_p->prev);
870 }
871 p_p = p_p->next->to; sc_p = nsc_p;
872 } else {
873 if ( sc_p->next==NULL ) {
874 IError("Unexpected point mismatch in replace");
875 return;
876 }
877 np_p = p_p->next->to; nsc_p = sc_p->next->to; nr_p = r_p->next->to;
878 if ( p_p==path->first ) {
879 sc_p->nonextcp = AdjustBP(&sc_p->nextcp,&sc_p->me,&r_p->nextcp,&r_p->me,&fudge,s);
880 if ( p_p->prev!=NULL )
881 sc_p->noprevcp = AdjustBP(&sc_p->prevcp,&sc_p->me,&r_p->prevcp,&r_p->me,&fudge,s);
882 if ( sc_p->prev!=NULL )
883 SplineRefigure(sc_p->prev);
884 sc_p->ticked = true;
885 }
886 if ( np_p==path->first )
887 return;
888 if ( np_p->next!=NULL )
889 nsc_p->nonextcp = AdjustBP(&nsc_p->nextcp,&nsc_p->me,&nr_p->nextcp,&nr_p->me,&fudge,s);
890 nsc_p->noprevcp = AdjustBP(&nsc_p->prevcp,&nsc_p->me,&nr_p->prevcp,&nr_p->me,&fudge,s);
891 AdjustAll(nsc_p,&sc_p->me,&nr_p->me,&r_p->me,&fudge,s);
892 nsc_p->ticked = true;
893 nsc_p->pointtype = nr_p->pointtype;
894 if ( nsc_p->next!=NULL ) {
895 if ( nsc_p->next->order2 )
896 nsc_p->next->to->prevcp = nsc_p->nextcp;
897 SplineRefigure(nsc_p->next);
898 }
899 if ( nsc_p->prev!=NULL ) {
900 if ( nsc_p->prev->order2 )
901 nsc_p->prev->from->nextcp = nsc_p->prevcp;
902 SplineRefigure(nsc_p->prev);
903 }
904 p_p = np_p; sc_p = nsc_p; r_p = nr_p;
905 }
906 }
907 }
908
HeuristiclyBadMatch(SplineChar * sc,SearchData * s)909 static int HeuristiclyBadMatch(SplineChar *sc,SearchData *s) {
910 /* Consider the case of a closed circle and an open circle, where the */
911 /* open circle looks just like the closed except that the open circle */
912 /* has an internal counter-clockwise contour. We don't want to match here*/
913 /* we'd get a reference and a counter-clockwise contour which would make */
914 /* no sense. */
915 /* so if, after removing matched contours we are left with a single counter*/
916 /* clockwise contour, don't accept the match */
917 int contour_cnt, i;
918 SplineSet *spl;
919 int layer = s->fv->active_layer;
920
921 contour_cnt=0;
922 for ( spl=sc->layers[layer].splines, i=0; spl!=NULL; spl=spl->next, ++i ) {
923 if ( !(s->matched_ss&(1<<i))) {
924 if ( SplinePointListIsClockwise(spl)==1 )
925 return( false );
926 ++contour_cnt;
927 }
928 }
929 if ( contour_cnt==0 )
930 return( false ); /* Exact match */
931
932 /* Everything remaining is counter-clockwise */
933 return( true );
934 }
935
DoReplaceFull(SplineChar * sc,SearchData * s)936 static void DoReplaceFull(SplineChar *sc,SearchData *s) {
937 int i;
938 RefChar *r, *rnext, *new;
939 SplinePointList *spl, *snext, *sprev, *temp;
940 real transform[6], subtrans[6];
941 SplinePoint *sp;
942 int layer = s->fv->active_layer;
943
944 /* first remove those bits that matched */
945 for ( r = sc->layers[layer].refs, i=0; r!=NULL; r=rnext, ++i ) {
946 rnext = r->next;
947 if ( s->matched_refs&(1<<i))
948 SCRemoveDependent(sc,r,layer);
949 }
950 sprev = NULL;
951 for ( spl=sc->layers[layer].splines, i=0; spl!=NULL; spl=snext, ++i ) {
952 snext = spl->next;
953 if ( s->matched_ss&(1<<i)) {
954 if ( sprev==NULL )
955 sc->layers[layer].splines = snext;
956 else
957 sprev->next = snext;
958 spl->next = NULL;
959 SplinePointListMDFree(sc,spl);
960 } else
961 sprev = spl;
962 }
963
964 /* Then insert the replace stuff */
965 SVBuildTrans(s,transform);
966 for ( r = s->sc_rpl.layers[ly_fore].refs; r!=NULL; r=r->next ) {
967 subtrans[0] = transform[0]*r->transform[0] + transform[1]*r->transform[2];
968 subtrans[1] = transform[0]*r->transform[1] + transform[1]*r->transform[3];
969 subtrans[2] = transform[2]*r->transform[0] + transform[3]*r->transform[2];
970 subtrans[3] = transform[2]*r->transform[1] + transform[3]*r->transform[3];
971 subtrans[4] = transform[4]*r->transform[0] + transform[5]*r->transform[2] +
972 r->transform[4];
973 subtrans[5] = transform[4]*r->transform[1] + transform[5]*r->transform[3] +
974 r->transform[5];
975 new = RefCharCreate();
976 free(new->layers);
977 *new = *r;
978 memcpy(new->transform,subtrans,sizeof(subtrans));
979 new->layers = NULL;
980 new->layer_cnt = 0;
981 new->next = sc->layers[layer].refs;
982 new->selected = true;
983 sc->layers[layer].refs = new;
984 SCReinstanciateRefChar(sc,new,layer);
985 SCMakeDependent(sc,new->sc);
986 if ( sc->layers[layer].order2 &&
987 !sc->layers[layer].background &&
988 !sc->instructions_out_of_date &&
989 sc->ttf_instrs!=NULL ) {
990 /* The normal change check doesn't respond properly to pasting a reference */
991 SCClearInstrsOrMark(sc,layer,!s->already_complained);
992 s->already_complained = true;
993 }
994 }
995 temp = SplinePointListTransform(SplinePointListCopy(s->sc_rpl.layers[ly_fore].splines),transform,tpt_AllPoints);
996 if ( sc->layers[layer].splines==NULL )
997 sc->layers[layer].splines = temp;
998 else {
999 for ( spl=sc->layers[layer].splines; spl->next!=NULL; spl = spl->next );
1000 spl->next = temp;
1001 for ( ; temp!=NULL; temp=temp->next ) {
1002 for ( sp=temp->first; ; ) {
1003 sp->selected = true;
1004 if ( sp->next==NULL )
1005 break;
1006 sp = sp->next->to;
1007 if ( sp==temp->first )
1008 break;
1009 }
1010 }
1011 }
1012 }
1013
1014 /* ************************************************************************** */
1015
SVResetPaths(SearchData * sv)1016 void SVResetPaths(SearchData *sv) {
1017 SplineSet *spl;
1018
1019 if ( sv->sc_srch.changed_since_autosave ) {
1020 sv->path = sv->sc_srch.layers[ly_fore].splines;
1021 SplinePointListsFree(sv->revpath);
1022 sv->revpath = SplinePointListCopy(sv->path);
1023 for ( spl=sv->revpath; spl!=NULL; spl=spl->next )
1024 spl = SplineSetReverse(spl);
1025 sv->sc_srch.changed_since_autosave = false;
1026 }
1027 if ( sv->sc_rpl.changed_since_autosave ) {
1028 sv->replacepath = sv->sc_rpl.layers[ly_fore].splines;
1029 SplinePointListsFree(sv->revreplace);
1030 sv->revreplace = SplinePointListCopy(sv->replacepath);
1031 for ( spl=sv->revreplace; spl!=NULL; spl=spl->next )
1032 spl = SplineSetReverse(spl);
1033 sv->sc_rpl.changed_since_autosave = false;
1034 }
1035
1036 /* Only do a sub pattern search if we have a single path and it is open */
1037 /* and there is either no replace pattern, or it is also a single open */
1038 /* path */
1039 sv->subpatternsearch = sv->path!=NULL && sv->path->next==NULL &&
1040 sv->path->first->prev==NULL && sv->sc_srch.layers[ly_fore].refs==NULL;
1041 if ( sv->replacepath!=NULL && (sv->replacepath->next!=NULL ||
1042 sv->replacepath->first->prev!=NULL ))
1043 sv->subpatternsearch = false;
1044 else if ( sv->sc_rpl.layers[ly_fore].refs!=NULL )
1045 sv->subpatternsearch = false;
1046
1047 if ( sv->subpatternsearch ) {
1048 int i;
1049 SplinePoint *sp;
1050 for ( sp=sv->path->first, i=0; ; ) {
1051 ++i;
1052 if ( sp->next==NULL )
1053 break;
1054 sp = sp->next->to;
1055 }
1056 sv->pointcnt = i;
1057 if ( sv->replacepath!=NULL ) {
1058 for ( sp=sv->replacepath->first, i=0; ; ) {
1059 ++i;
1060 if ( sp->next==NULL )
1061 break;
1062 sp = sp->next->to;
1063 }
1064 sv->rpointcnt = i;
1065 }
1066 }
1067 }
1068
SplinePointsUntick(SplineSet * spl)1069 static void SplinePointsUntick(SplineSet *spl) {
1070 SplinePoint *sp;
1071
1072 while ( spl!=NULL ) {
1073 for ( sp = spl->first ; ; ) {
1074 sp->ticked = false;
1075 if ( sp->next==NULL )
1076 break;
1077 sp = sp->next->to;
1078 if ( sp==spl->first )
1079 break;
1080 }
1081 spl = spl->next;
1082 }
1083 }
1084
SCSplinePointsUntick(SplineChar * sc,int layer)1085 void SCSplinePointsUntick(SplineChar *sc,int layer) {
1086 SplinePointsUntick(sc->layers[layer].splines);
1087 }
1088
SearchChar(SearchData * sv,int gid,int startafter)1089 int SearchChar(SearchData *sv, int gid,int startafter) {
1090
1091 sv->curchar = sv->fv->sf->glyphs[gid];
1092
1093 sv->wasreversed = false;
1094 sv->matched_rot = 0; sv->matched_scale = 1;
1095 sv->matched_co = 1; sv->matched_si = 0;
1096 sv->matched_flip = flip_none;
1097 sv->matched_refs = sv->matched_ss = 0;
1098 sv->matched_x = sv->matched_y = 0;
1099
1100 if ( sv->subpatternsearch )
1101 return( SCMatchesIncomplete(sv->curchar,sv,startafter));
1102 else
1103 return( SCMatchesFull(sv->curchar,sv));
1104 }
1105
DoRpl(SearchData * sv)1106 int DoRpl(SearchData *sv) {
1107 RefChar *r;
1108 int layer = sv->fv->active_layer;
1109
1110 /* Make sure we don't generate any self referential characters... */
1111 for ( r = sv->sc_rpl.layers[ly_fore].refs; r!=NULL; r=r->next ) {
1112 if ( SCDependsOnSC(r->sc,sv->curchar))
1113 return(false);
1114 }
1115
1116 if ( sv->replaceall && !sv->subpatternsearch &&
1117 HeuristiclyBadMatch(sv->curchar,sv))
1118 return(false);
1119
1120 SCPreserveLayer(sv->curchar,layer,false);
1121 if ( sv->subpatternsearch )
1122 DoReplaceIncomplete(sv->curchar,sv);
1123 else
1124 DoReplaceFull(sv->curchar,sv);
1125 SCCharChangedUpdate(sv->curchar,layer);
1126 return( true );
1127 }
1128
_DoFindAll(SearchData * sv)1129 int _DoFindAll(SearchData *sv) {
1130 int i, any=0, gid;
1131 SplineChar *startcur = sv->curchar;
1132
1133 for ( i=0; i<sv->fv->map->enccount; ++i ) {
1134 if (( !sv->onlyselected || sv->fv->selected[i]) && (gid=sv->fv->map->map[i])!=-1 &&
1135 sv->fv->sf->glyphs[gid]!=NULL ) {
1136 SCSplinePointsUntick(sv->fv->sf->glyphs[gid],sv->fv->active_layer);
1137 if ( (sv->fv->selected[i] = SearchChar(sv,gid,false)) ) {
1138 any = true;
1139 if ( sv->replaceall ) {
1140 do {
1141 if ( !DoRpl(sv))
1142 break;
1143 } while ( (sv->subpatternsearch || sv->replacewithref) &&
1144 SearchChar(sv,gid,true));
1145 }
1146 }
1147 } else
1148 sv->fv->selected[i] = false;
1149 }
1150 sv->curchar = startcur;
1151 return( any );
1152 }
1153
SDDestroy(SearchData * sv)1154 void SDDestroy(SearchData *sv) {
1155 int i;
1156
1157 if ( sv==NULL )
1158 return;
1159
1160 SCClearContents(&sv->sc_srch,ly_fore);
1161 SCClearContents(&sv->sc_rpl,ly_fore);
1162 for ( i=0; i<sv->sc_srch.layer_cnt; ++i )
1163 UndoesFree(sv->sc_srch.layers[i].undoes);
1164 for ( i=0; i<sv->sc_rpl.layer_cnt; ++i )
1165 UndoesFree(sv->sc_rpl.layers[i].undoes);
1166 free(sv->sc_srch.layers);
1167 free(sv->sc_rpl.layers);
1168 SplinePointListsFree(sv->revpath);
1169 }
1170
SDFillup(SearchData * sv,FontViewBase * fv)1171 SearchData *SDFillup(SearchData *sv, FontViewBase *fv) {
1172
1173 sv->sc_srch.orig_pos = 0; sv->sc_srch.unicodeenc = -1; sv->sc_srch.name = "Search";
1174 sv->sc_rpl.orig_pos = 1; sv->sc_rpl.unicodeenc = -1; sv->sc_rpl.name = "Replace";
1175 sv->sc_srch.layer_cnt = sv->sc_rpl.layer_cnt = 2;
1176 sv->sc_srch.layers = calloc(2,sizeof(Layer));
1177 sv->sc_rpl.layers = calloc(2,sizeof(Layer));
1178 LayerDefault(&sv->sc_srch.layers[0]);
1179 LayerDefault(&sv->sc_srch.layers[1]);
1180 LayerDefault(&sv->sc_rpl.layers[0]);
1181 LayerDefault(&sv->sc_rpl.layers[1]);
1182
1183 sv->fv = fv;
1184 return( sv );
1185 }
1186
IsASingleReferenceOrEmpty(SplineChar * sc,int layer)1187 static int IsASingleReferenceOrEmpty(SplineChar *sc,int layer) {
1188 int i, empty = true, last, first;
1189
1190 if ( sc->parent->multilayer ) {
1191 first = ly_fore;
1192 last = sc->layer_cnt-1;
1193 } else
1194 first = last = layer;
1195 for ( i = first; i<=last; ++i ) {
1196 if ( sc->layers[i].splines!=NULL )
1197 return( false );
1198 if ( sc->layers[i].images!=NULL )
1199 return( false );
1200 if ( sc->layers[i].refs!=NULL ) {
1201 if ( !empty )
1202 return( false );
1203 if ( sc->layers[i].refs->next!=NULL )
1204 return( false );
1205 empty = false;
1206 }
1207 }
1208
1209 return( true );
1210 }
1211
SDCopyToSC(SplineChar * checksc,SplineChar * into,enum fvcopy_type full)1212 static void SDCopyToSC(SplineChar *checksc,SplineChar *into,enum fvcopy_type full) {
1213 int i;
1214 RefChar *ref;
1215
1216 for ( i=0; i<into->layer_cnt; ++i ) {
1217 SplinePointListsFree(into->layers[i].splines);
1218 RefCharsFree(into->layers[i].refs);
1219 into->layers[i].splines = NULL;
1220 into->layers[i].refs = NULL;
1221 }
1222 if ( full==ct_fullcopy ) {
1223 into->layers[ly_fore].splines = SplinePointListCopy(checksc->layers[ly_fore].splines);
1224 into->layers[ly_fore].refs = RefCharsCopyState(checksc,ly_fore);
1225 } else {
1226 into->layers[ly_fore].refs = ref = RefCharCreate();
1227 ref->unicode_enc = checksc->unicodeenc;
1228 ref->orig_pos = checksc->orig_pos;
1229 ref->adobe_enc = getAdobeEnc(checksc->name);
1230 ref->transform[0] = ref->transform[3] = 1.0;
1231 ref->sc = checksc;
1232 }
1233 /* This is used to fill up the search/rpl patterns, which can't have */
1234 /* instructions, so I don't bother to check for instructions out of */
1235 /* date */
1236 }
1237
FVBReplaceOutlineWithReference(FontViewBase * fv,double fudge)1238 void FVBReplaceOutlineWithReference( FontViewBase *fv, double fudge ) {
1239 SearchData *sv;
1240 uint8 *selected, *changed;
1241 SplineFont *sf = fv->sf;
1242 int i, j, selcnt = 0, gid;
1243 SplineChar *checksc;
1244
1245 sv = SDFillup( calloc(1,sizeof(SearchData)), fv);
1246 sv->fudge_percent = .001;
1247 sv->fudge = fudge;
1248 sv->replaceall = true;
1249 sv->replacewithref = true;
1250
1251 selected = malloc(fv->map->enccount);
1252 memcpy(selected,fv->selected,fv->map->enccount);
1253 changed = calloc(fv->map->enccount,1);
1254
1255 selcnt = 0;
1256 for ( i=0; i<fv->map->enccount; ++i ) if ( selected[i] && (gid=fv->map->map[i])!=-1 &&
1257 sf->glyphs[gid]!=NULL )
1258 ++selcnt;
1259 ff_progress_start_indicator(10,_("Replace with Reference"),
1260 _("Replace Outline with Reference"),0,selcnt,1);
1261
1262 for ( i=0; i<fv->map->enccount; ++i ) if ( selected[i] && (gid=fv->map->map[i])!=-1 &&
1263 (checksc=sf->glyphs[gid])!=NULL ) {
1264 if ( IsASingleReferenceOrEmpty(sf->glyphs[gid],fv->active_layer))
1265 continue; /* No point in replacing something which is itself a ref with a ref to a ref */
1266 memset(fv->selected,0,fv->map->enccount);
1267 SDCopyToSC(checksc,&sv->sc_srch,ct_fullcopy);
1268 SDCopyToSC(checksc,&sv->sc_rpl,ct_reference);
1269 sv->sc_srch.changed_since_autosave = sv->sc_rpl.changed_since_autosave = true;
1270 SVResetPaths(sv);
1271 if ( !_DoFindAll(sv) && selcnt==1 )
1272 ff_post_notice(_("Not Found"),_("The outlines of glyph %2$.30s were not found in the font %1$.60s"),
1273 sf->fontname,sf->glyphs[gid]->name);
1274 for ( j=0; j<fv->map->enccount; ++j )
1275 if ( fv->selected[j] )
1276 changed[j] = 1;
1277 if ( !ff_progress_next())
1278 break;
1279 }
1280 ff_progress_end_indicator();
1281
1282 SDDestroy(sv);
1283 free(sv);
1284
1285 free(selected);
1286 memcpy(fv->selected,changed,fv->map->enccount);
1287 free(changed);
1288 }
1289
1290 /* This will free both the find and rpl contours */
FVReplaceAll(FontViewBase * fv,SplineSet * find,SplineSet * rpl,double fudge,int flags)1291 int FVReplaceAll( FontViewBase *fv, SplineSet *find, SplineSet *rpl, double fudge, int flags ) {
1292 SearchData *sv;
1293 int ret;
1294
1295 sv = SDFillup( calloc(1,sizeof(SearchData)), fv);
1296 sv->fudge_percent = .001;
1297 sv->fudge = fudge;
1298 sv->replaceall = true;
1299
1300 sv->tryreverse = (flags&sv_reverse);
1301 sv->tryflips = (flags&sv_flips);
1302 sv->tryrotate = (flags&sv_rotate);
1303 sv->tryscale = (flags&sv_scale);
1304
1305 sv->sc_srch.layers[ly_fore].splines = find;
1306 sv->sc_rpl .layers[ly_fore].splines = rpl;
1307 sv->sc_srch.changed_since_autosave = sv->sc_rpl.changed_since_autosave = true;
1308 SVResetPaths(sv);
1309
1310 ret = _DoFindAll(sv);
1311
1312 SDDestroy(sv);
1313 free(sv);
1314 return( ret );
1315 }
1316
1317 /* This will free both the find and rpl contours */
SDFromContour(FontViewBase * fv,SplineSet * find,double fudge,int flags)1318 SearchData *SDFromContour( FontViewBase *fv, SplineSet *find, double fudge, int flags ) {
1319 SearchData *sv;
1320
1321 sv = SDFillup( calloc(1,sizeof(SearchData)), fv);
1322 sv->fudge_percent = .001;
1323 sv->fudge = fudge;
1324
1325 sv->tryreverse = (flags&sv_reverse) != 0;
1326 sv->tryflips = (flags&sv_flips) != 0;
1327 sv->tryrotate = (flags&sv_rotate) != 0;
1328 sv->tryscale = (flags&sv_scale) != 0;
1329
1330 sv->sc_srch.layers[ly_fore].splines = find;
1331 sv->sc_srch.changed_since_autosave = sv->sc_rpl.changed_since_autosave = true;
1332 SVResetPaths(sv);
1333
1334 sv->last_gid = -1;
1335 return( sv );
1336 }
1337
SDFindNext(SearchData * sd)1338 SplineChar *SDFindNext(SearchData *sd) {
1339 int gid;
1340 FontViewBase *fv;
1341
1342 if ( sd==NULL )
1343 return( NULL );
1344 fv = sd->fv;
1345
1346 for ( gid=sd->last_gid+1; gid<fv->sf->glyphcnt; ++gid ) {
1347 SCSplinePointsUntick(fv->sf->glyphs[gid],fv->active_layer);
1348 if ( SearchChar(sd,gid,false) ) {
1349 sd->last_gid = gid;
1350 return( fv->sf->glyphs[gid]);
1351 }
1352 }
1353 return( NULL );
1354 }
1355
1356 /* ************************************************************************** */
1357 /* *************************** Correct References *************************** */
1358 /* ************************************************************************** */
1359
1360 /* In TrueType a glyph can either be all contours or all references. FontForge*/
1361 /* supports mixed contours and references. This section goes through the font*/
1362 /* looking for such mixed glyphs, if it finds one it will create a new glyph */
1363 /* move the contours into it, and make a reference to the new glyph in the */
1364 /* original. This is designed to reduce the size of the TT output file */
1365
1366 /* Similar problem... The transformation matrix of a truetype reference has */
1367 /* certain restrictions placed on it (all entries must be less than 2 in abs */
1368 /* value, etc. If we have a glyph with a ref with a bad transform, then */
1369 /* go through a similar process to the above */
1370
RC_MakeNewGlyph(FontViewBase * fv,SplineChar * base,int index,const char * reason,const char * morereason)1371 static SplineChar *RC_MakeNewGlyph(FontViewBase *fv,SplineChar *base, int index,
1372 const char *reason, const char *morereason) {
1373 char *namebuf;
1374 SplineFont *sf = fv->sf;
1375 int enc;
1376 SplineChar *ret;
1377
1378 namebuf = malloc(strlen(base->name)+20);
1379 for (;;) {
1380 sprintf(namebuf, "%s.ref%d", base->name, index++ );
1381 if ( SFGetChar(sf,-1,namebuf)==NULL )
1382 break;
1383 }
1384
1385 enc = SFFindSlot(sf, fv->map, -1, namebuf );
1386 if ( enc==-1 )
1387 enc = fv->map->enccount;
1388 ret = SFMakeChar(sf,fv->map,enc);
1389 free(ret->name);
1390 ret->name = namebuf;
1391 SFHashGlyph(sf,ret);
1392
1393 ret->comment = malloc( strlen(reason)+strlen(ret->name)+strlen(morereason) + 2 );
1394 sprintf( ret->comment, reason, base->name, morereason );
1395 ret->color = 0xff8080;
1396 return( ret );
1397 }
1398
AddRef(SplineChar * sc,SplineChar * rsc,int layer)1399 static void AddRef(SplineChar *sc,SplineChar *rsc, int layer) {
1400 RefChar *r;
1401
1402 r = RefCharCreate();
1403 free(r->layers);
1404 r->layers = NULL;
1405 r->layer_cnt = 0;
1406 r->sc = rsc;
1407 r->unicode_enc = rsc->unicodeenc;
1408 r->orig_pos = rsc->orig_pos;
1409 r->adobe_enc = getAdobeEnc(rsc->name);
1410 r->transform[0] = r->transform[3] = 1.0;
1411 r->next = NULL;
1412 SCMakeDependent(sc,rsc);
1413 SCReinstanciateRefChar(sc,r,layer);
1414 r->next = sc->layers[layer].refs;
1415 sc->layers[layer].refs = r;
1416 }
1417
DListRemove(struct splinecharlist * dependents,SplineChar * this_sc)1418 static struct splinecharlist *DListRemove(struct splinecharlist *dependents,SplineChar *this_sc) {
1419 struct splinecharlist *dlist, *pd;
1420
1421 if ( dependents==NULL )
1422 return( NULL );
1423 else if ( dependents->sc==this_sc ) {
1424 dlist = dependents->next;
1425 chunkfree(dependents,sizeof(*dependents));
1426 return( dlist );
1427 } else {
1428 for ( pd=dependents, dlist = pd->next; dlist!=NULL && dlist->sc!=this_sc; pd=dlist, dlist = pd->next );
1429 if ( dlist!=NULL ) {
1430 pd->next = dlist->next;
1431 chunkfree(dlist,sizeof(*dlist));
1432 }
1433 return( dependents );
1434 }
1435 }
1436
FVCorrectReferences(FontViewBase * fv)1437 void FVCorrectReferences(FontViewBase *fv) {
1438 int enc, gid, cnt;
1439 SplineFont *sf = fv->sf;
1440 SplineChar *sc, *rsc;
1441 RefChar *ref;
1442 int layer = fv->active_layer;
1443 int index;
1444
1445 cnt = 0;
1446 for ( enc=0; enc<fv->map->enccount; ++enc ) {
1447 if ( (gid=fv->map->map[enc])!=-1 && fv->selected[enc] && (sc=sf->glyphs[gid])!=NULL )
1448 ++cnt;
1449 }
1450 ff_progress_start_indicator(10,_("Correcting References"),
1451 _("Adding new glyphs and referring to them when a glyph contains a bad truetype reference"),NULL,cnt,1);
1452 for ( enc=0; enc<fv->map->enccount; ++enc ) {
1453 if ( (gid=fv->map->map[enc])!=-1 && fv->selected[enc] && (sc=sf->glyphs[gid])!=NULL ) {
1454 index = 1;
1455 if ( sc->layers[layer].splines!=NULL && sc->layers[layer].refs!=NULL ) {
1456 SCPreserveLayer(sc,layer,false);
1457 rsc = RC_MakeNewGlyph(fv,sc,index++,
1458 _("%s had both contours and references, so the contours were moved "
1459 "into this glyph, and a reference to it was added in the original."),
1460 "");
1461 rsc->layers[layer].splines = sc->layers[layer].splines;
1462 sc->layers[layer].splines = NULL;
1463 AddRef(sc,rsc,layer);
1464 /* I don't bother to check for instructions because there */
1465 /* shouldn't be any in a mixed outline and reference glyph */
1466 }
1467 for ( ref=sc->layers[layer].refs; ref!=NULL; ref=ref->next ) {
1468 if ( ref->transform[0]>0x7fff/16384.0 ||
1469 ref->transform[1]>0x7fff/16384.0 ||
1470 ref->transform[2]>0x7fff/16384.0 ||
1471 ref->transform[3]>0x7fff/16384.0 ||
1472 ref->transform[0]<-2.0 || /* Numbers are asymetric, negative range slightly bigger */
1473 ref->transform[1]<-2.0 ||
1474 ref->transform[2]<-2.0 ||
1475 ref->transform[3]<-2.0 ) {
1476 if ( index==1 )
1477 SCPreserveLayer(sc,layer,false);
1478 rsc = RC_MakeNewGlyph(fv,sc,index++,
1479 _("%1$s had a reference, %2$s, with a bad transformation matrix (one of "
1480 "the matrix elements was bigger than 2). I moved the transformed "
1481 "contours into this glyph and made a reference to it, instead."),
1482 ref->sc->name);
1483 rsc->layers[layer].splines = ref->layers[0].splines;
1484 ref->layers[0].splines = NULL;
1485 ref->sc->dependents = DListRemove(ref->sc->dependents,sc);
1486 ref->sc = rsc;
1487 memset(ref->transform,0,sizeof(ref->transform));
1488 ref->transform[0] = ref->transform[3] = 1.0;
1489 SCReinstanciateRefChar(sc,ref,layer);
1490 }
1491 }
1492 if ( index!=1 )
1493 SCCharChangedUpdate(sc,layer);
1494 if ( !ff_progress_next())
1495 break;
1496 }
1497 }
1498 ff_progress_end_indicator();
1499 }
1500