1 /* Copyright (C) 2000-2008 by George Williams */
3 * Redistribution and use in source and binary forms, with or without
4 * modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright notice, this
7 * list of conditions and the following disclaimer.
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.
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.
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.
35 int new_em_size
= 1000;
36 int new_fonts_are_order2
= false;
37 int loaded_fonts_same_as_new
= false;
38 int default_fv_row_count
= 4;
39 int default_fv_col_count
= 16;
40 int default_fv_font_size
= 24;
41 int default_fv_antialias
=true;
42 int default_fv_bbsized
=true;
47 int RealNear(real a
,real b
) {
50 #if 0 /* def FONTFORGE_CONFIG_USE_DOUBLE*/
52 return( b
>-1e-8 && b
<1e-8 );
54 return( a
>-1e-8 && a
<1e-8 );
58 return( b
>a
-d
&& b
<a
+d
);
59 #else /* For floats */
61 return( b
>-1e-5 && b
<1e-5 );
63 return( a
>-1e-5 && a
<1e-5 );
67 return( b
>a
-d
&& b
<a
+d
);
71 int RealNearish(real a
,real b
) {
73 if ( a
-b
<.001 && a
-b
>-.001 )
78 int RealApprox(real a
,real b
) {
81 if ( b
<.0001 && b
>-.0001 )
84 if ( a
<.0001 && a
>-.0001 )
88 if ( a
>=.95 && a
<=1.05 )
94 int RealWithin(real a
,real b
,real fudge
) {
96 return( b
>=a
-fudge
&& b
<=a
+fudge
);
99 int RealRatio(real a
,real b
,real fudge
) {
102 return( RealWithin(a
,b
,fudge
));
104 return( RealWithin(a
/b
,1.0,fudge
));
107 static int MinMaxWithin(Spline
*spline
) {
112 /* We know that this "spline" is basically one dimensional. As long as its*/
113 /* extrema are between the start and end points on that line then we can */
114 /* treat it as a line. If the extrema are way outside the line segment */
115 /* then it's a line that backtracks on itself */
117 if ( (dx
= spline
->to
->me
.x
- spline
->from
->me
.x
)<0 ) dx
= -dx
;
118 if ( (dy
= spline
->to
->me
.y
- spline
->from
->me
.y
)<0 ) dy
= -dy
;
120 SplineFindExtrema(&spline
->splines
[which
],&t1
,&t2
);
123 w
= ((spline
->splines
[which
].a
*t1
+ spline
->splines
[which
].b
)*t1
124 + spline
->splines
[which
].c
)*t1
+ spline
->splines
[which
].d
;
125 if ( RealNear(w
, (&spline
->to
->me
.x
)[which
]) || RealNear(w
, (&spline
->from
->me
.x
)[which
]) )
127 else if ( (w
<(&spline
->to
->me
.x
)[which
] && w
<(&spline
->from
->me
.x
)[which
]) ||
128 (w
>(&spline
->to
->me
.x
)[which
] && w
>(&spline
->from
->me
.x
)[which
]) )
129 return( false ); /* Outside */
131 w
= ((spline
->splines
[which
].a
*t2
+ spline
->splines
[which
].b
)*t2
132 + spline
->splines
[which
].c
)*t2
+ spline
->splines
[which
].d
;
133 if ( RealNear(w
, (&spline
->to
->me
.x
)[which
]) || RealNear(w
, (&spline
->from
->me
.x
)[which
]) )
135 else if ( (w
<(&spline
->to
->me
.x
)[which
] && w
<(&spline
->from
->me
.x
)[which
]) ||
136 (w
>(&spline
->to
->me
.x
)[which
] && w
>(&spline
->from
->me
.x
)[which
]) )
137 return( false ); /* Outside */
142 int SplineIsLinear(Spline
*spline
) {
146 if ( spline
->knownlinear
)
148 if ( spline
->knowncurved
)
151 if ( spline
->splines
[0].a
==0 && spline
->splines
[0].b
==0 &&
152 spline
->splines
[1].a
==0 && spline
->splines
[1].b
==0 )
155 /* Something is linear if the control points lie on the line between the */
156 /* two base points */
159 if ( RealNear(spline
->from
->me
.x
,spline
->to
->me
.x
) ) {
160 ret
= RealNear(spline
->from
->me
.x
,spline
->from
->nextcp
.x
) &&
161 RealNear(spline
->from
->me
.x
,spline
->to
->prevcp
.x
);
162 if ( ! ((spline
->from
->nextcp
.y
>= spline
->from
->me
.y
&&
163 spline
->from
->nextcp
.y
<= spline
->to
->me
.y
&&
164 spline
->to
->prevcp
.y
>= spline
->from
->me
.y
&&
165 spline
->to
->prevcp
.y
<= spline
->to
->me
.y
) ||
166 (spline
->from
->nextcp
.y
<= spline
->from
->me
.y
&&
167 spline
->from
->nextcp
.y
>= spline
->to
->me
.y
&&
168 spline
->to
->prevcp
.y
<= spline
->from
->me
.y
&&
169 spline
->to
->prevcp
.y
>= spline
->to
->me
.y
)) )
170 ret
= MinMaxWithin(spline
);
171 /* Horizontal lines */
172 } else if ( RealNear(spline
->from
->me
.y
,spline
->to
->me
.y
) ) {
173 ret
= RealNear(spline
->from
->me
.y
,spline
->from
->nextcp
.y
) &&
174 RealNear(spline
->from
->me
.y
,spline
->to
->prevcp
.y
);
175 if ( ! ((spline
->from
->nextcp
.x
>= spline
->from
->me
.x
&&
176 spline
->from
->nextcp
.x
<= spline
->to
->me
.x
&&
177 spline
->to
->prevcp
.x
>= spline
->from
->me
.x
&&
178 spline
->to
->prevcp
.x
<= spline
->to
->me
.x
) ||
179 (spline
->from
->nextcp
.x
<= spline
->from
->me
.x
&&
180 spline
->from
->nextcp
.x
>= spline
->to
->me
.x
&&
181 spline
->to
->prevcp
.x
<= spline
->from
->me
.x
&&
182 spline
->to
->prevcp
.x
>= spline
->to
->me
.x
)) )
183 ret
= MinMaxWithin(spline
);
186 t1
= (spline
->from
->nextcp
.y
-spline
->from
->me
.y
)/(spline
->to
->me
.y
-spline
->from
->me
.y
);
187 t2
= (spline
->from
->nextcp
.x
-spline
->from
->me
.x
)/(spline
->to
->me
.x
-spline
->from
->me
.x
);
188 t3
= (spline
->to
->me
.y
-spline
->to
->prevcp
.y
)/(spline
->to
->me
.y
-spline
->from
->me
.y
);
189 t4
= (spline
->to
->me
.x
-spline
->to
->prevcp
.x
)/(spline
->to
->me
.x
-spline
->from
->me
.x
);
190 ret
= (RealApprox(t1
,t2
) || (RealApprox(t1
,0) && RealApprox(t2
,0))) &&
191 (RealApprox(t3
,t4
) || (RealApprox(t3
,0) && RealApprox(t4
,0)));
193 if ( t1
<0 || t2
<0 || t3
<0 || t4
<0 ||
194 t1
>1 || t2
>1 || t3
>1 || t4
>1 )
195 ret
= MinMaxWithin(spline
);
198 spline
->knowncurved
= !ret
;
199 spline
->knownlinear
= ret
;
201 /* A few places that if the spline is knownlinear then its splines[?] */
202 /* are linear. So give the linear version and not that suggested by */
203 /* the control points */
204 spline
->splines
[0].a
= spline
->splines
[0].b
= 0;
205 spline
->splines
[0].d
= spline
->from
->me
.x
;
206 spline
->splines
[0].c
= spline
->to
->me
.x
-spline
->from
->me
.x
;
207 spline
->splines
[1].a
= spline
->splines
[1].b
= 0;
208 spline
->splines
[1].d
= spline
->from
->me
.y
;
209 spline
->splines
[1].c
= spline
->to
->me
.y
-spline
->from
->me
.y
;
214 int SplineIsLinearMake(Spline
*spline
) {
216 if ( spline
->islinear
)
218 if ( SplineIsLinear(spline
)) {
219 spline
->islinear
= spline
->from
->nonextcp
= spline
->to
->noprevcp
= true;
220 spline
->from
->nextcp
= spline
->from
->me
;
221 if ( spline
->from
->nonextcp
&& spline
->from
->noprevcp
)
222 spline
->from
->pointtype
= pt_corner
;
223 else if ( spline
->from
->pointtype
== pt_curve
|| spline
->from
->pointtype
== pt_hvcurve
)
224 spline
->from
->pointtype
= pt_tangent
;
225 spline
->to
->prevcp
= spline
->to
->me
;
226 if ( spline
->to
->nonextcp
&& spline
->to
->noprevcp
)
227 spline
->to
->pointtype
= pt_corner
;
228 else if ( spline
->to
->pointtype
== pt_curve
|| spline
->to
->pointtype
== pt_hvcurve
)
229 spline
->to
->pointtype
= pt_tangent
;
230 SplineRefigure(spline
);
232 return( spline
->islinear
);
235 static Spline
*IsLinearApprox(SplinePoint
*from
, SplinePoint
*to
,
236 TPoint
*mid
, int cnt
, int order2
) {
237 double vx
, vy
, slope
;
240 vx
= to
->me
.x
-from
->me
.x
; vy
= to
->me
.y
-from
->me
.y
;
241 if ( vx
==0 && vy
==0 ) {
242 for ( i
=0; i
<cnt
; ++i
)
243 if ( mid
[i
].x
!= from
->me
.x
|| mid
[i
].y
!= from
->me
.y
)
245 } else if ( fabs(vx
)>fabs(vy
) ) {
247 for ( i
=0; i
<cnt
; ++i
)
248 if ( !RealWithin(mid
[i
].y
,from
->me
.y
+slope
*(mid
[i
].x
-from
->me
.x
),.7) )
252 for ( i
=0; i
<cnt
; ++i
)
253 if ( !RealWithin(mid
[i
].x
,from
->me
.x
+slope
*(mid
[i
].y
-from
->me
.y
),.7) )
256 from
->nonextcp
= to
->noprevcp
= true;
257 return( SplineMake(from
,to
,order2
) );
260 /* Least squares tells us that:
261 | S(xi*ti^3) | | S(ti^6) S(ti^5) S(ti^4) S(ti^3) | | a |
262 | S(xi*ti^2) | = | S(ti^5) S(ti^4) S(ti^3) S(ti^2) | * | b |
263 | S(xi*ti) | | S(ti^4) S(ti^3) S(ti^2) S(ti) | | c |
264 | S(xi) | | S(ti^3) S(ti^2) S(ti) n | | d |
265 and the definition of a spline tells us:
266 | x1 | = | 1 1 1 1 | * (a b c d)
267 | x0 | = | 0 0 0 1 | * (a b c d)
268 So we're a bit over specified. Let's use the last two lines of least squares
269 and the 2 from the spline defn. So d==x0. Now we've got three unknowns
270 and only three equations...
272 For order2 splines we've got
273 | S(xi*ti^2) | | S(ti^4) S(ti^3) S(ti^2) | | b |
274 | S(xi*ti) | = | S(ti^3) S(ti^2) S(ti) | * | c |
275 | S(xi) | | S(ti^2) S(ti) n | | d |
276 and the definition of a spline tells us:
277 | x1 | = | 1 1 1 | * (b c d)
278 | x0 | = | 0 0 1 | * (b c d)
282 S(ti^2)*b + S(ti)*c = S(xi)-n*x0
283 S(ti^2)*b + S(ti)*(x1-x0-b) = S(xi)-n*x0
284 [ S(ti^2)-S(ti) ]*b = S(xi)-S(ti)*(x1-x0) - n*x0
286 static int _ApproximateSplineFromPoints(SplinePoint
*from
, SplinePoint
*to
,
287 TPoint
*mid
, int cnt
, BasePoint
*nextcp
, BasePoint
*prevcp
,
291 double vx
[3], vy
[3], m
[3][3];
292 double ts
[7], xts
[4], yts
[4];
293 BasePoint nres
, pres
;
294 int nrescnt
=0, prescnt
=0;
295 double nmin
, nmax
, pmin
, pmax
, test
, ptest
;
296 double bx
, by
, cx
, cy
;
298 memset(&nres
,0,sizeof(nres
)); memset(&pres
,0,sizeof(pres
));
300 /* Add the initial and end points */
301 ts
[0] = 2; for ( i
=1; i
<7; ++i
) ts
[i
] = 1;
302 xts
[0] = from
->me
.x
+to
->me
.x
; yts
[0] = from
->me
.y
+to
->me
.y
;
303 xts
[3] = xts
[2] = xts
[1] = to
->me
.x
; yts
[3] = yts
[2] = yts
[1] = to
->me
.y
;
304 nmin
= pmin
= 0; nmax
= pmax
= (to
->me
.x
-from
->me
.x
)*(to
->me
.x
-from
->me
.x
)+(to
->me
.y
-from
->me
.y
)*(to
->me
.y
-from
->me
.y
);
305 for ( i
=0; i
<cnt
; ++i
) {
310 xts
[1] += tt
*mid
[i
].x
;
311 yts
[1] += tt
*mid
[i
].y
;
313 ts
[2] += (ttn
=tt
*tt
);
314 xts
[2] += ttn
*mid
[i
].x
;
315 yts
[2] += ttn
*mid
[i
].y
;
317 xts
[3] += ttn
*mid
[i
].x
;
318 yts
[3] += ttn
*mid
[i
].y
;
323 test
= (mid
[i
].x
-from
->me
.x
)*(to
->me
.x
-from
->me
.x
) + (mid
[i
].y
-from
->me
.y
)*(to
->me
.y
-from
->me
.y
);
324 if ( test
<nmin
) nmin
=test
;
325 if ( test
>nmax
) nmax
=test
;
326 test
= (mid
[i
].x
-to
->me
.x
)*(from
->me
.x
-to
->me
.x
) + (mid
[i
].y
-to
->me
.y
)*(from
->me
.y
-to
->me
.y
);
327 if ( test
<pmin
) pmin
=test
;
328 if ( test
>pmax
) pmax
=test
;
330 pmin
*= 1.2; pmax
*= 1.2; nmin
*= 1.2; nmax
*= 1.2;
332 for ( j
=0; j
<3; ++j
) {
334 if ( RealNear(ts
[j
+2],ts
[j
+1]) )
336 /* This produces really bad results!!!! But I don't see what I can do to improve it */
337 bx
= (xts
[j
]-ts
[j
+1]*(to
->me
.x
-from
->me
.x
) - ts
[j
]*from
->me
.x
) / (ts
[j
+2]-ts
[j
+1]);
338 by
= (yts
[j
]-ts
[j
+1]*(to
->me
.y
-from
->me
.y
) - ts
[j
]*from
->me
.y
) / (ts
[j
+2]-ts
[j
+1]);
339 cx
= to
->me
.x
-from
->me
.x
-bx
;
340 cy
= to
->me
.y
-from
->me
.y
-by
;
342 nextcp
->x
= from
->me
.x
+ cx
/2;
343 nextcp
->y
= from
->me
.y
+ cy
/2;
346 vx
[0] = xts
[j
+1]-ts
[j
+1]*from
->me
.x
;
347 vx
[1] = xts
[j
]-ts
[j
]*from
->me
.x
;
348 vx
[2] = to
->me
.x
-from
->me
.x
; /* always use the defn of spline */
350 vy
[0] = yts
[j
+1]-ts
[j
+1]*from
->me
.y
;
351 vy
[1] = yts
[j
]-ts
[j
]*from
->me
.y
;
352 vy
[2] = to
->me
.y
-from
->me
.y
;
354 m
[0][0] = ts
[j
+4]; m
[0][1] = ts
[j
+3]; m
[0][2] = ts
[j
+2];
355 m
[1][0] = ts
[j
+3]; m
[1][1] = ts
[j
+2]; m
[1][2] = ts
[j
+1];
356 m
[2][0] = 1; m
[2][1] = 1; m
[2][2] = 1;
358 /* Remove a terms from rows 0 and 1 */
359 vx
[0] -= ts
[j
+4]*vx
[2];
360 vy
[0] -= ts
[j
+4]*vy
[2];
361 m
[0][0] = 0; m
[0][1] -= ts
[j
+4]; m
[0][2] -= ts
[j
+4];
362 vx
[1] -= ts
[j
+3]*vx
[2];
363 vy
[1] -= ts
[j
+3]*vy
[2];
364 m
[1][0] = 0; m
[1][1] -= ts
[j
+3]; m
[1][2] -= ts
[j
+3];
366 if ( fabs(m
[1][1])<fabs(m
[0][1]) ) {
368 temp
= vx
[1]; vx
[1] = vx
[0]; vx
[0] = temp
;
369 temp
= vy
[1]; vy
[1] = vy
[0]; vy
[0] = temp
;
370 temp
= m
[1][1]; m
[1][1] = m
[0][1]; m
[0][1] = temp
;
371 temp
= m
[1][2]; m
[1][2] = m
[0][2]; m
[0][2] = temp
;
373 /* remove b terms from rows 0 and 2 (first normalize row 1 so m[1][1] is 1*/
378 vx
[0] -= m
[0][1]*vx
[1];
379 vy
[0] -= m
[0][1]*vy
[1];
380 m
[0][2] -= m
[0][1]*m
[1][2]; m
[0][1] = 0;
381 vx
[2] -= m
[2][1]*vx
[1];
382 vy
[2] -= m
[2][1]*vy
[1];
383 m
[2][2] -= m
[2][1]*m
[1][2]; m
[2][1] = 0;
385 vx
[0] /= m
[0][2]; /* This is cx */
386 vy
[0] /= m
[0][2]; /* This is cy */
389 vx
[1] -= m
[1][2]*vx
[0]; /* This is bx */
390 vy
[1] -= m
[1][2]*vy
[0]; /* This is by */
392 vx
[2] -= m
[2][2]*vx
[0]; /* This is ax */
393 vy
[2] -= m
[2][2]*vy
[0]; /* This is ay */
396 nextcp
->x
= from
->me
.x
+ vx
[0]/3;
397 nextcp
->y
= from
->me
.y
+ vy
[0]/3;
398 prevcp
->x
= nextcp
->x
+ (vx
[0]+vx
[1])/3;
399 prevcp
->y
= nextcp
->y
+ (vy
[0]+vy
[1])/3;
402 test
= (nextcp
->x
-from
->me
.x
)*(to
->me
.x
-from
->me
.x
) +
403 (nextcp
->y
-from
->me
.y
)*(to
->me
.y
-from
->me
.y
);
404 ptest
= (prevcp
->x
-to
->me
.x
)*(from
->me
.x
-to
->me
.x
) +
405 (prevcp
->y
-to
->me
.y
)*(from
->me
.y
-to
->me
.y
);
407 (test
<nmin
|| test
>nmax
|| ptest
<pmin
|| ptest
>pmax
))
409 if ( test
>=nmin
&& test
<=nmax
) {
410 nres
.x
+= nextcp
->x
; nres
.y
+= nextcp
->y
;
413 if ( test
>=pmin
&& test
<=pmax
) {
414 pres
.x
+= prevcp
->x
; pres
.y
+= prevcp
->y
;
417 if ( nrescnt
==1 && prescnt
==1 )
424 nextcp
->x
= nres
.x
/nrescnt
;
425 nextcp
->y
= nres
.y
/nrescnt
;
427 *nextcp
= from
->nextcp
;
430 prevcp
->x
= pres
.x
/prescnt
;
431 prevcp
->y
= pres
.y
/prescnt
;
433 *prevcp
= to
->prevcp
;
434 if ( order2
&& ret
!=3 ) {
435 nextcp
->x
= (nextcp
->x
+ prevcp
->x
)/2;
436 nextcp
->y
= (nextcp
->y
+ prevcp
->y
)/2;
443 static void TestForLinear(SplinePoint
*from
,SplinePoint
*to
) {
444 BasePoint off
, cpoff
, cpoff2
;
447 /* Did we make a line? */
448 off
.x
= to
->me
.x
-from
->me
.x
; off
.y
= to
->me
.y
-from
->me
.y
;
449 len
= sqrt(off
.x
*off
.x
+ off
.y
*off
.y
);
451 off
.x
/= len
; off
.y
/= len
;
452 cpoff
.x
= from
->nextcp
.x
-from
->me
.x
; cpoff
.y
= from
->nextcp
.y
-from
->me
.y
;
453 len
= sqrt(cpoff
.x
*cpoff
.x
+ cpoff
.y
*cpoff
.y
);
455 cpoff
.x
/= len
; cpoff
.y
/= len
;
457 cpoff2
.x
= to
->prevcp
.x
-from
->me
.x
; cpoff2
.y
= to
->prevcp
.y
-from
->me
.y
;
458 len
= sqrt(cpoff2
.x
*cpoff2
.x
+ cpoff2
.y
*cpoff2
.y
);
460 cpoff2
.x
/= len
; cpoff2
.y
/= len
;
462 co
= cpoff
.x
*off
.y
- cpoff
.y
*off
.x
; co2
= cpoff2
.x
*off
.y
- cpoff2
.y
*off
.x
;
463 if ( co
<.05 && co
>-.05 && co2
<.05 && co2
>-.05 ) {
464 from
->nextcp
= from
->me
; from
->nonextcp
= true;
465 to
->prevcp
= to
->me
; to
->noprevcp
= true;
468 memset(&temp
,0,sizeof(temp
));
469 temp
.from
= from
; temp
.to
= to
;
470 SplineRefigure(&temp
);
471 if ( SplineIsLinear(&temp
)) {
472 from
->nextcp
= from
->me
; from
->nonextcp
= true;
473 to
->prevcp
= to
->me
; to
->noprevcp
= true;
479 /* Find a spline which best approximates the list of intermediate points we */
480 /* are given. No attempt is made to fix the slopes */
481 Spline
*ApproximateSplineFromPoints(SplinePoint
*from
, SplinePoint
*to
,
482 TPoint
*mid
, int cnt
, int order2
) {
485 BasePoint nextcp
, prevcp
;
487 if ( (spline
= IsLinearApprox(from
,to
,mid
,cnt
,order2
))!=NULL
)
490 ret
= _ApproximateSplineFromPoints(from
,to
,mid
,cnt
,&nextcp
,&prevcp
,order2
);
493 from
->nextcp
= nextcp
;
494 from
->nonextcp
= false;
496 from
->nextcp
= from
->me
;
497 from
->nonextcp
= true;
501 to
->noprevcp
= false;
506 TestForLinear(from
,to
);
507 spline
= SplineMake(from
,to
,order2
);
511 static double ClosestSplineSolve(Spline1D
*sp
,double sought
,double close_to_t
) {
512 /* We want to find t so that spline(t) = sought */
513 /* find the value which is closest to close_to_t */
514 /* on error return closetot */
518 double t
, best
, test
;
522 CubicSolve(&temp
,ts
);
523 best
= 9e20
; t
= close_to_t
;
524 for ( i
=0; i
<3; ++i
) if ( ts
[i
]!=-1 ) {
525 if ( (test
=ts
[i
]-close_to_t
)<0 ) test
= -test
;
539 double min
,max
; /* If min<0 || max>len the spline extends beyond its endpoints */
542 static double SigmaDeltas(Spline
*spline
,TPoint
*mid
, int cnt
, DBounds
*b
, struct dotbounds
*db
) {
544 double xdiff
, ydiff
, sum
, temp
, t
, lastt
;
545 SplinePoint
*to
= spline
->to
, *from
= spline
->from
;
547 struct dotbounds db2
;
550 if ( (xdiff
= to
->me
.x
-from
->me
.x
)<0 ) xdiff
= -xdiff
;
551 if ( (ydiff
= to
->me
.y
-from
->me
.y
)<0 ) ydiff
= -ydiff
;
553 sum
= 0; lastt
= -1; lasti
= -1;
554 for ( i
=0; i
<cnt
; ++i
) {
555 if ( ydiff
>2*xdiff
) {
556 t
= ClosestSplineSolve(&spline
->splines
[1],mid
[i
].y
,mid
[i
].t
);
557 } else if ( xdiff
>2*ydiff
) {
558 t
= ClosestSplineSolve(&spline
->splines
[0],mid
[i
].x
,mid
[i
].t
);
560 t
= (ClosestSplineSolve(&spline
->splines
[1],mid
[i
].y
,mid
[i
].t
) +
561 ClosestSplineSolve(&spline
->splines
[0],mid
[i
].x
,mid
[i
].t
))/2;
563 if ( t
==lastt
) /* These last* values appear to be debugging */
564 t
= lastt
+ (mid
[i
].t
- mid
[lasti
].t
);
569 temp
= mid
[i
].x
- ( ((spline
->splines
[0].a
*t
+spline
->splines
[0].b
)*t
+spline
->splines
[0].c
)*t
+ spline
->splines
[0].d
);
571 temp
= mid
[i
].y
- ( ((spline
->splines
[1].a
*t
+spline
->splines
[1].b
)*t
+spline
->splines
[1].c
)*t
+ spline
->splines
[1].d
);
575 /* Ok, we've got distances from a set of points on the old spline to the */
576 /* new one. Let's do the reverse: find the extrema of the new and see how*/
577 /* close they get to the bounding box of the old */
578 /* And get really unhappy if the spline extends beyond the end-points */
579 db2
.min
= 0; db2
.max
= db
->len
;
580 SplineFindExtrema(&spline
->splines
[0],&ts
[0],&ts
[1]);
581 for ( i
=0; i
<2; ++i
) {
583 x
= ((spline
->splines
[0].a
*ts
[i
]+spline
->splines
[0].b
)*ts
[i
]+spline
->splines
[0].c
)*ts
[i
] + spline
->splines
[0].d
;
584 y
= ((spline
->splines
[1].a
*ts
[i
]+spline
->splines
[1].b
)*ts
[i
]+spline
->splines
[1].c
)*ts
[i
] + spline
->splines
[1].d
;
586 sum
+= (x
-b
->minx
)*(x
-b
->minx
);
587 else if ( x
>b
->maxx
)
588 sum
+= (x
-b
->maxx
)*(x
-b
->maxx
);
589 dot
= (x
-db
->base
.x
)*db
->unit
.x
+ (y
-db
->base
.y
)*db
->unit
.y
;
590 if ( dot
<db2
.min
) db2
.min
= dot
;
591 if ( dot
>db2
.max
) db2
.max
= dot
;
594 SplineFindExtrema(&spline
->splines
[1],&ts
[0],&ts
[1]);
595 for ( i
=0; i
<2; ++i
) {
597 x
= ((spline
->splines
[0].a
*ts
[i
]+spline
->splines
[0].b
)*ts
[i
]+spline
->splines
[0].c
)*ts
[i
] + spline
->splines
[0].d
;
598 y
= ((spline
->splines
[1].a
*ts
[i
]+spline
->splines
[1].b
)*ts
[i
]+spline
->splines
[1].c
)*ts
[i
] + spline
->splines
[1].d
;
600 sum
+= (y
-b
->miny
)*(y
-b
->miny
);
601 else if ( y
>b
->maxy
)
602 sum
+= (y
-b
->maxy
)*(y
-b
->maxy
);
603 dot
= (x
-db
->base
.x
)*db
->unit
.x
+ (y
-db
->base
.y
)*db
->unit
.y
;
604 if ( dot
<db2
.min
) db2
.min
= dot
;
605 if ( dot
>db2
.max
) db2
.max
= dot
;
609 /* Big penalty for going beyond the range of the desired spline */
610 if ( db
->min
==0 && db2
.min
<0 )
611 sum
+= 10000 + db2
.min
*db2
.min
;
612 else if ( db2
.min
<db
->min
)
613 sum
+= 100 + (db2
.min
-db
->min
)*(db2
.min
-db
->min
);
614 if ( db
->max
==db
->len
&& db2
.max
>db
->len
)
615 sum
+= 10000 + (db2
.max
-db
->max
)*(db2
.max
-db
->max
);
616 else if ( db2
.max
>db
->max
)
617 sum
+= 100 + (db2
.max
-db
->max
)*(db2
.max
-db
->max
);
622 static void ApproxBounds(DBounds
*b
,TPoint
*mid
, int cnt
, struct dotbounds
*db
) {
626 b
->minx
= b
->maxx
= mid
[0].x
;
627 b
->miny
= b
->maxy
= mid
[0].y
;
628 db
->min
= 0; db
->max
= db
->len
;
629 for ( i
=1; i
<cnt
; ++i
) {
630 if ( mid
[i
].x
>b
->maxx
) b
->maxx
= mid
[i
].x
;
631 if ( mid
[i
].x
<b
->minx
) b
->minx
= mid
[i
].x
;
632 if ( mid
[i
].y
>b
->maxy
) b
->maxy
= mid
[i
].y
;
633 if ( mid
[i
].y
<b
->miny
) b
->miny
= mid
[i
].y
;
634 dot
= (mid
[i
].x
-db
->base
.x
)*db
->unit
.x
+ (mid
[i
].y
-db
->base
.y
)*db
->unit
.y
;
635 if ( dot
<db
->min
) db
->min
= dot
;
636 if ( dot
>db
->max
) db
->max
= dot
;
640 static int GoodCurve(SplinePoint
*sp
, int check_prev
) {
641 double dx
, dy
, lenx
, leny
;
643 if ( sp
->pointtype
!=pt_curve
&& sp
->pointtype
!=pt_hvcurve
)
646 dx
= sp
->me
.x
- sp
->prevcp
.x
;
647 dy
= sp
->me
.y
- sp
->prevcp
.y
;
649 dx
= sp
->me
.x
- sp
->nextcp
.x
;
650 dy
= sp
->me
.y
- sp
->nextcp
.y
;
652 /* If the cp is very close to the base point the point might as well be a corner */
653 if ( dx
<0 ) dx
= -dx
;
654 if ( dy
<0 ) dy
= -dy
;
659 if ( sp
->prev
==NULL
)
661 lenx
= sp
->me
.x
- sp
->prev
->from
->me
.x
;
662 leny
= sp
->me
.y
- sp
->prev
->from
->me
.y
;
664 if ( sp
->next
==NULL
)
666 lenx
= sp
->me
.x
- sp
->next
->to
->me
.x
;
667 leny
= sp
->me
.y
- sp
->next
->to
->me
.y
;
669 if ( lenx
<0 ) lenx
= -lenx
;
670 if ( leny
<0 ) leny
= -leny
;
671 if ( 50*(dx
+dy
) < lenx
+leny
)
678 static int totcnt_cnt
, nocnt_cnt
, incr_cnt
, curdiff_cnt
;
681 /* I used to do a least squares aproach adding two more to the above set of equations */
682 /* which held the slopes constant. But that didn't work very well. So instead*/
683 /* Then I tried doing the approximation, and then forcing the control points */
684 /* to be in line (witht the original slopes), getting a better approximation */
685 /* to "t" for each data point and then calculating an error array, approximating*/
686 /* it, and using that to fix up the final result */
687 /* Then I tried checking various possible cp lengths in the desired directions*/
688 /* finding the best one or two, and doing a 2D binary search using that as a */
689 /* starting point. */
690 /* And sometimes a least squares approach will give us the right answer, so */
692 /* This still isn't as good as I'd like it... But I haven't been able to */
693 /* improve it further yet */
696 Spline
*ApproximateSplineFromPointsSlopes(SplinePoint
*from
, SplinePoint
*to
,
697 TPoint
*mid
, int cnt
, int order2
) {
698 BasePoint tounit
, fromunit
, ftunit
;
699 double flen
,tlen
,ftlen
;
700 Spline
*spline
, temp
;
702 int bettern
, betterp
;
703 double offn
, offp
, incrn
, incrp
, trylen
;
704 int nocnt
= 0, totcnt
;
705 double curdiff
, bestdiff
[TRY_CNT
];
706 int i
,j
,besti
[TRY_CNT
],bestj
[TRY_CNT
],k
,l
;
707 double fdiff
, tdiff
, fmax
, tmax
, fdotft
, tdotft
;
710 double offn_
, offp_
, finaldiff
;
712 /* If all the selected points are at the same spot, and one of the */
713 /* end-points is also at that spot, then just copy the control point */
714 /* But our caller seems to have done that for us */
716 /* If the two end-points are corner points then allow the slope to vary */
717 /* Or if one end-point is a tangent but the point defining the tangent's */
718 /* slope is being removed then allow the slope to vary */
719 /* Except if the slope is horizontal or vertical then keep it fixed */
720 if ( ( !from
->nonextcp
&& ( from
->nextcp
.x
==from
->me
.x
|| from
->nextcp
.y
==from
->me
.y
)) ||
721 (!to
->noprevcp
&& ( to
->prevcp
.x
==to
->me
.x
|| to
->prevcp
.y
==to
->me
.y
)) )
722 /* Preserve the slope */;
723 else if ( ((from
->pointtype
== pt_corner
&& from
->nonextcp
) ||
724 (from
->pointtype
== pt_tangent
&&
725 ((from
->nonextcp
&& from
->noprevcp
) || !from
->noprevcp
))) &&
726 ((to
->pointtype
== pt_corner
&& to
->noprevcp
) ||
727 (to
->pointtype
== pt_tangent
&&
728 ((to
->nonextcp
&& to
->noprevcp
) || !to
->nonextcp
))) ) {
729 from
->pointtype
= to
->pointtype
= pt_corner
;
730 return( ApproximateSplineFromPoints(from
,to
,mid
,cnt
,order2
) );
733 /* If we are going to honour the slopes of a quadratic spline, there is */
734 /* only one possibility */
736 if ( from
->nonextcp
)
737 from
->nextcp
= from
->next
->to
->me
;
739 to
->prevcp
= to
->prev
->from
->me
;
740 from
->nonextcp
= to
->noprevcp
= false;
741 fromunit
.x
= from
->nextcp
.x
-from
->me
.x
; fromunit
.y
= from
->nextcp
.y
-from
->me
.y
;
742 tounit
.x
= to
->prevcp
.x
-to
->me
.x
; tounit
.y
= to
->prevcp
.y
-to
->me
.y
;
744 if ( !IntersectLines(&nextcp
,&from
->nextcp
,&from
->me
,&to
->prevcp
,&to
->me
) ||
745 (nextcp
.x
-from
->me
.x
)*fromunit
.x
+ (nextcp
.y
-from
->me
.y
)*fromunit
.y
< 0 ||
746 (nextcp
.x
-to
->me
.x
)*tounit
.x
+ (nextcp
.y
-to
->me
.y
)*tounit
.y
< 0 ) {
747 /* If the slopes don't intersect then use a line */
748 /* (or if the intersection is patently absurd) */
749 from
->nonextcp
= to
->noprevcp
= true;
750 from
->nextcp
= from
->me
;
752 TestForLinear(from
,to
);
754 from
->nextcp
= to
->prevcp
= nextcp
;
755 from
->nonextcp
= to
->noprevcp
= false;
757 return( SplineMake2(from
,to
));
759 /* From here down we are only working with cubic splines */
762 /* Just use what we've got, no data to improve it */
763 /* But we do sometimes get some cps which are too big */
764 double len
= sqrt((to
->me
.x
-from
->me
.x
)*(to
->me
.x
-from
->me
.x
) + (to
->me
.y
-from
->me
.y
)*(to
->me
.y
-from
->me
.y
));
766 from
->nonextcp
= to
->noprevcp
= true;
767 from
->nextcp
= from
->me
;
770 BasePoint noff
, poff
;
772 noff
.x
= from
->nextcp
.x
-from
->me
.x
; noff
.y
= from
->nextcp
.y
-from
->me
.y
;
773 poff
.x
= to
->me
.x
-to
->prevcp
.x
; poff
.y
= to
->me
.y
-to
->prevcp
.y
;
774 nlen
= sqrt(noff
.x
*noff
.x
+ noff
.y
+noff
.y
);
775 plen
= sqrt(poff
.x
*poff
.x
+ poff
.y
+poff
.y
);
777 noff
.x
*= len
/3/nlen
; noff
.y
*= len
/3/nlen
;
778 from
->nextcp
.x
= from
->me
.x
+ noff
.x
;
779 from
->nextcp
.y
= from
->me
.y
+ noff
.y
;
782 poff
.x
*= len
/3/plen
; poff
.y
*= len
/3/plen
;
783 to
->prevcp
.x
= to
->me
.x
+ poff
.x
;
784 to
->prevcp
.y
= to
->me
.y
+ poff
.y
;
787 return( SplineMake3(from
,to
));
790 if ( to
->prev
!=NULL
&& (( to
->noprevcp
&& to
->nonextcp
) || to
->prev
->knownlinear
)) {
791 tounit
.x
= to
->prev
->from
->me
.x
-to
->me
.x
; tounit
.y
= to
->prev
->from
->me
.y
-to
->me
.y
;
792 } else if ( !to
->noprevcp
|| to
->pointtype
== pt_corner
) {
793 tounit
.x
= to
->prevcp
.x
-to
->me
.x
; tounit
.y
= to
->prevcp
.y
-to
->me
.y
;
795 tounit
.x
= to
->me
.x
-to
->nextcp
.x
; tounit
.y
= to
->me
.y
-to
->nextcp
.y
;
797 tlen
= sqrt(tounit
.x
*tounit
.x
+ tounit
.y
*tounit
.y
);
798 if ( from
->next
!=NULL
&& (( from
->noprevcp
&& from
->nonextcp
) || from
->next
->knownlinear
) ) {
799 fromunit
.x
= from
->next
->to
->me
.x
-from
->me
.x
; fromunit
.y
= from
->next
->to
->me
.y
-from
->me
.y
;
800 } else if ( !from
->nonextcp
|| from
->pointtype
== pt_corner
) {
801 fromunit
.x
= from
->nextcp
.x
-from
->me
.x
; fromunit
.y
= from
->nextcp
.y
-from
->me
.y
;
803 fromunit
.x
= from
->me
.x
-from
->prevcp
.x
; fromunit
.y
= from
->me
.y
-from
->prevcp
.y
;
805 flen
= sqrt(fromunit
.x
*fromunit
.x
+ fromunit
.y
*fromunit
.y
);
806 if ( tlen
==0 || flen
==0 ) {
807 if ( from
->next
!=NULL
)
810 memset(&temp
,0,sizeof(temp
));
811 temp
.from
= from
; temp
.to
= to
;
812 SplineRefigure(&temp
);
813 from
->next
= to
->prev
= NULL
;
817 if ( (to
->pointtype
==pt_curve
|| to
->pointtype
==pt_hvcurve
) &&
818 to
->next
&& !to
->nonextcp
) {
819 tounit
.x
= to
->me
.x
-to
->nextcp
.x
; tounit
.y
= to
->me
.y
-to
->nextcp
.y
;
821 } else if ( to->pointtype==pt_tangent && to->next ) {
822 tounit.x = to->me.x-to->next->to->me.x; tounit.y = to->me.y-to->next->to->me.y;
825 tounit
.x
= -( (3*temp
.splines
[0].a
*.9999+2*temp
.splines
[0].b
)*.9999+temp
.splines
[0].c
);
826 tounit
.y
= -( (3*temp
.splines
[1].a
*.9999+2*temp
.splines
[1].b
)*.9999+temp
.splines
[1].c
);
828 tlen
= sqrt(tounit
.x
*tounit
.x
+ tounit
.y
*tounit
.y
);
830 tounit
.x
/= tlen
; tounit
.y
/= tlen
;
833 if ( (from
->pointtype
==pt_curve
|| from
->pointtype
==pt_hvcurve
) &&
834 from
->prev
&& !from
->noprevcp
) {
835 fromunit
.x
= from
->me
.x
-from
->prevcp
.x
; fromunit
.y
= from
->me
.y
-from
->prevcp
.y
;
837 } else if ( from->pointtype==pt_tangent && from->prev ) {
838 fromunit.x = from->me.x-from->prev->from->me.x; fromunit.y = from->me.y-from->prev->from->me.y;
841 fromunit
.x
= ( (3*temp
.splines
[0].a
*.0001+2*temp
.splines
[0].b
)*.0001+temp
.splines
[0].c
);
842 fromunit
.y
= ( (3*temp
.splines
[1].a
*.0001+2*temp
.splines
[1].b
)*.0001+temp
.splines
[1].c
);
844 flen
= sqrt(fromunit
.x
*fromunit
.x
+ fromunit
.y
*fromunit
.y
);
846 fromunit
.x
/= flen
; fromunit
.y
/= flen
;
848 trylen
= (to
->me
.x
-from
->me
.x
)*fromunit
.x
+ (to
->me
.y
-from
->me
.y
)*fromunit
.y
;
849 if ( trylen
>flen
) flen
= trylen
;
851 trylen
= (from
->me
.x
-to
->me
.x
)*tounit
.x
+ (from
->me
.y
-to
->me
.y
)*tounit
.y
;
852 if ( trylen
>tlen
) tlen
= trylen
;
854 ftunit
.x
= (to
->me
.x
-from
->me
.x
); ftunit
.y
= (to
->me
.y
-from
->me
.y
);
855 ftlen
= sqrt(ftunit
.x
*ftunit
.x
+ ftunit
.y
*ftunit
.y
);
857 ftunit
.x
/= ftlen
; ftunit
.y
/= ftlen
;
859 fdotft
= fromunit
.x
*ftunit
.x
+ fromunit
.y
*ftunit
.y
;
860 fmax
= fdotft
>0 ? ftlen
/fdotft
: 1e10
;
861 tdotft
= -tounit
.x
*ftunit
.x
- tounit
.y
*ftunit
.y
;
862 tmax
= tdotft
>0 ? ftlen
/tdotft
: 1e10
;
863 /* At fmax, tmax the control points will stretch beyond the other endpoint*/
864 /* when projected along the line between the two endpoints */
867 db
.unit
.x
= (to
->me
.x
-from
->me
.x
); db
.unit
.y
= (to
->me
.y
-from
->me
.y
);
868 db
.len
= sqrt(db
.unit
.x
*db
.unit
.x
+ db
.unit
.y
*db
.unit
.y
);
873 ApproxBounds(&b
,mid
,cnt
,&db
);
875 for ( k
=0; k
<TRY_CNT
; ++k
) {
877 besti
[k
] = -1; bestj
[k
] = -1;
879 fdiff
= flen
/DECIMATION
;
880 tdiff
= tlen
/DECIMATION
;
881 from
->nextcp
= from
->me
;
882 from
->nonextcp
= false;
883 to
->noprevcp
= false;
884 memset(&temp
,0,sizeof(Spline
));
885 temp
.from
= from
; temp
.to
= to
;
886 for ( i
=1; i
<DECIMATION
; ++i
) {
887 from
->nextcp
.x
+= fdiff
*fromunit
.x
; from
->nextcp
.y
+= fdiff
*fromunit
.y
;
889 for ( j
=1; j
<DECIMATION
; ++j
) {
890 to
->prevcp
.x
+= tdiff
*tounit
.x
; to
->prevcp
.y
+= tdiff
*tounit
.y
;
891 SplineRefigure(&temp
);
892 curdiff
= SigmaDeltas(&temp
,mid
,cnt
,&b
,&db
);
893 for ( k
=0; k
<TRY_CNT
; ++k
) {
894 if ( curdiff
<bestdiff
[k
] ) {
895 for ( l
=TRY_CNT
-1; l
>k
; --l
) {
896 bestdiff
[l
] = bestdiff
[l
-1];
897 besti
[l
] = besti
[l
-1];
898 bestj
[l
] = bestj
[l
-1];
900 bestdiff
[k
] = curdiff
;
901 besti
[k
] = i
; bestj
[k
]=j
;
910 spline
= SplineMake(from
,to
,false);
911 for ( k
=-1; k
<TRY_CNT
; ++k
) {
913 BasePoint nextcp
, prevcp
;
915 int ret
= _ApproximateSplineFromPoints(from
,to
,mid
,cnt
,&nextcp
,&prevcp
,false);
916 /* sometimes least squares gives us the right answer */
917 if ( !(ret
&1) || !(ret
&2))
919 temp1
= (prevcp
.x
-to
->me
.x
)*tounit
.x
+ (prevcp
.y
-to
->me
.y
)*tounit
.y
;
920 temp2
= (nextcp
.x
-from
->me
.x
)*fromunit
.x
+ (nextcp
.y
-from
->me
.y
)*fromunit
.y
;
921 if ( temp1
<=0 || temp2
<=0 ) /* A nice solution... but the control points are diametrically opposed to what they should be */
923 tlen
= temp1
; flen
= temp2
;
925 if ( bestj
[k
]<0 || besti
[k
]<0 )
927 tlen
= bestj
[k
]*tdiff
; flen
= besti
[k
]*fdiff
;
929 to
->prevcp
.x
= to
->me
.x
+ tlen
*tounit
.x
; to
->prevcp
.y
= to
->me
.y
+ tlen
*tounit
.y
;
930 from
->nextcp
.x
= from
->me
.x
+ flen
*fromunit
.x
; from
->nextcp
.y
= from
->me
.y
+ flen
*fromunit
.y
;
931 SplineRefigure(spline
);
933 bettern
= betterp
= false;
934 incrn
= tdiff
/2.0; incrp
= fdiff
/2.0;
935 offn
= flen
; offp
= tlen
;
937 curdiff
= SigmaDeltas(spline
,mid
,cnt
,&b
,&db
);
940 double fadiff
, fsdiff
;
941 double tadiff
, tsdiff
;
943 from
->nextcp
.x
= from
->me
.x
+ (offn
+incrn
)*fromunit
.x
; from
->nextcp
.y
= from
->me
.y
+ (offn
+incrn
)*fromunit
.y
;
944 to
->prevcp
.x
= to
->me
.x
+ offp
*tounit
.x
; to
->prevcp
.y
= to
->me
.y
+ offp
*tounit
.y
;
945 SplineRefigure(spline
);
946 fadiff
= SigmaDeltas(spline
,mid
,cnt
,&b
,&db
);
947 from
->nextcp
.x
= from
->me
.x
+ (offn
-incrn
)*fromunit
.x
; from
->nextcp
.y
= from
->me
.y
+ (offn
-incrn
)*fromunit
.y
;
948 SplineRefigure(spline
);
949 fsdiff
= SigmaDeltas(spline
,mid
,cnt
,&b
,&db
);
950 from
->nextcp
.x
= from
->me
.x
+ offn
*fromunit
.x
; from
->nextcp
.y
= from
->me
.y
+ offn
*fromunit
.y
;
954 to
->prevcp
.x
= to
->me
.x
+ (offp
+incrp
)*tounit
.x
; to
->prevcp
.y
= to
->me
.y
+ (offp
+incrp
)*tounit
.y
;
955 SplineRefigure(spline
);
956 tadiff
= SigmaDeltas(spline
,mid
,cnt
,&b
,&db
);
957 to
->prevcp
.x
= to
->me
.x
+ (offp
-incrp
)*tounit
.x
; to
->prevcp
.y
= to
->me
.y
+ (offp
-incrp
)*tounit
.y
;
958 SplineRefigure(spline
);
959 tsdiff
= SigmaDeltas(spline
,mid
,cnt
,&b
,&db
);
960 to
->prevcp
.x
= to
->me
.x
+ offp
*tounit
.x
; to
->prevcp
.y
= to
->me
.y
+ offp
*tounit
.y
;
964 if ( offn
>=incrn
&& fsdiff
<curdiff
&&
965 (fsdiff
<fadiff
&& fsdiff
<tsdiff
&& fsdiff
<tadiff
)) {
972 } else if ( offn
+incrn
<fmax
&& fadiff
<curdiff
&&
973 (fadiff
<=fsdiff
&& fadiff
<tsdiff
&& fadiff
<tadiff
)) {
980 } else if ( offp
>=incrp
&& tsdiff
<curdiff
&&
981 (tsdiff
<=fsdiff
&& tsdiff
<=fadiff
&& tsdiff
<tadiff
)) {
988 } else if ( offp
+incrp
<tmax
&& tadiff
<curdiff
&&
989 (tadiff
<=fsdiff
&& tadiff
<=fadiff
&& tadiff
<=tsdiff
)) {
1004 if ( incrp
<tdiff
/1024 || incrn
<fdiff
/1024 )
1008 if ( offn
<0 || offp
<0 ) {
1009 IError("Approximation got inverse control points");
1016 else if ( curdiff
<1 )
1018 else if ( totcnt
>200 )
1023 if ( curdiff
<finaldiff
) {
1024 finaldiff
= curdiff
;
1030 to
->noprevcp
= offp_
==0;
1031 from
->nonextcp
= offn_
==0;
1032 to
->prevcp
.x
= to
->me
.x
+ offp_
*tounit
.x
; to
->prevcp
.y
= to
->me
.y
+ offp_
*tounit
.y
;
1033 from
->nextcp
.x
= from
->me
.x
+ offn_
*fromunit
.x
; from
->nextcp
.y
= from
->me
.y
+ offn_
*fromunit
.y
;
1034 /* I used to check for a spline very close to linear (and if so, make it */
1035 /* linear). But in when stroking a path with an eliptical pen we transform*/
1036 /* the coordinate system and our normal definitions of "close to linear" */
1038 /*TestForLinear(from,to);*/
1039 SplineRefigure(spline
);
1046 /* calculating the actual length of a spline is hard, this gives a very */
1047 /* rough (but quick) approximation */
1048 static double SplineLenApprox(Spline
*spline
) {
1049 double len
, slen
, temp
;
1051 if ( (temp
= spline
->to
->me
.x
-spline
->from
->me
.x
)<0 ) temp
= -temp
;
1053 if ( (temp
= spline
->to
->me
.y
-spline
->from
->me
.y
)<0 ) temp
= -temp
;
1055 if ( !spline
->to
->noprevcp
|| !spline
->from
->nonextcp
) {
1056 if ( (temp
= spline
->from
->nextcp
.x
-spline
->from
->me
.x
)<0 ) temp
= -temp
;
1058 if ( (temp
= spline
->from
->nextcp
.y
-spline
->from
->me
.y
)<0 ) temp
= -temp
;
1060 if ( (temp
= spline
->to
->prevcp
.x
-spline
->from
->nextcp
.x
)<0 ) temp
= -temp
;
1062 if ( (temp
= spline
->to
->prevcp
.y
-spline
->from
->nextcp
.y
)<0 ) temp
= -temp
;
1064 if ( (temp
= spline
->to
->me
.x
-spline
->to
->prevcp
.x
)<0 ) temp
= -temp
;
1066 if ( (temp
= spline
->to
->me
.y
-spline
->to
->prevcp
.y
)<0 ) temp
= -temp
;
1068 len
= (len
+ slen
)/2;
1073 double SplineLength(Spline
*spline
) {
1074 /* I ignore the constant term. It's just an unneeded addition */
1076 double lastx
= 0, lasty
= 0;
1080 for ( t
=1.0/128; t
<=1.0001 ; t
+=1.0/128 ) {
1081 curx
= ((spline
->splines
[0].a
*t
+spline
->splines
[0].b
)*t
+spline
->splines
[0].c
)*t
;
1082 cury
= ((spline
->splines
[1].a
*t
+spline
->splines
[1].b
)*t
+spline
->splines
[1].c
)*t
;
1083 len
+= sqrt( (curx
-lastx
)*(curx
-lastx
) + (cury
-lasty
)*(cury
-lasty
) );
1084 lastx
= curx
; lasty
= cury
;
1090 static TPoint
*SplinesFigureTPsBetween(SplinePoint
*from
, SplinePoint
*to
,
1092 int cnt
, i
, j
, pcnt
;
1093 double len
, slen
, lbase
;
1096 double _lens
[10], *lens
= _lens
;
1097 int _cnts
[10], *cnts
= _cnts
;
1098 /* I used just to give every spline 10 points. But that gave much more */
1099 /* weight to small splines than to big ones */
1102 for ( np
= from
->next
->to
; ; np
= np
->next
->to
) {
1108 lens
= galloc(cnt
*sizeof(double));
1109 cnts
= galloc(cnt
*sizeof(int));
1112 for ( np
= from
->next
->to
; ; np
= np
->next
->to
) {
1113 lens
[cnt
] = SplineLenApprox(np
->prev
);
1121 for ( i
=0; i
<cnt
; ++i
) {
1122 int pnts
= rint( (10*cnt
*lens
[i
])/len
);
1123 if ( pnts
<2 ) pnts
= 2;
1130 tp
= galloc((pcnt
+1)*sizeof(TPoint
)); i
= 0;
1132 for ( i
=0; i
<=pcnt
; ++i
) {
1134 tp
[i
].x
= from
->me
.x
;
1135 tp
[i
].y
= from
->me
.y
;
1139 for ( i
=cnt
=0, np
= from
->next
->to
; ; np
= np
->next
->to
, ++cnt
) {
1140 slen
= SplineLenApprox(np
->prev
);
1141 for ( j
=0; j
<cnts
[cnt
]; ++j
) {
1142 double t
= j
/(double) cnts
[cnt
];
1143 tp
[i
].t
= (lbase
+ t
*slen
)/len
;
1144 tp
[i
].x
= ((np
->prev
->splines
[0].a
*t
+np
->prev
->splines
[0].b
)*t
+np
->prev
->splines
[0].c
)*t
+ np
->prev
->splines
[0].d
;
1145 tp
[i
++].y
= ((np
->prev
->splines
[1].a
*t
+np
->prev
->splines
[1].b
)*t
+np
->prev
->splines
[1].c
)*t
+ np
->prev
->splines
[1].d
;
1152 if ( cnts
!=_cnts
) free(cnts
);
1153 if ( lens
!=_lens
) free(lens
);
1160 static void SplinePointReCatagorize(SplinePoint
*sp
,int oldpt
) {
1161 SplinePointCatagorize(sp
);
1162 if ( sp
->pointtype
!=oldpt
) {
1163 if ( sp
->pointtype
==pt_curve
&& oldpt
==pt_hvcurve
&&
1164 ((sp
->nextcp
.x
== sp
->me
.x
&& sp
->nextcp
.y
!= sp
->me
.y
) ||
1165 (sp
->nextcp
.y
== sp
->me
.y
&& sp
->nextcp
.x
!= sp
->me
.x
)))
1166 sp
->pointtype
= pt_hvcurve
;
1170 void SplinesRemoveBetween(SplineChar
*sc
, SplinePoint
*from
, SplinePoint
*to
,int type
) {
1173 SplinePoint
*np
, oldfrom
;
1174 int oldfpt
= from
->pointtype
, oldtpt
= to
->pointtype
;
1176 int order2
= from
->next
->order2
;
1179 tp
= SplinesFigureTPsBetween(from
,to
,&tot
);
1182 ApproximateSplineFromPointsSlopes(from
,to
,tp
,tot
-1,order2
);
1184 ApproximateSplineFromPoints(from
,to
,tp
,tot
-1,order2
);
1186 /* Have to do the frees after the approximation because the approx */
1187 /* uses the splines to determine slopes */
1188 for ( sp
= oldfrom
.next
; ; ) {
1194 SplinePointMDFree(sc
,np
);
1199 SplinePointReCatagorize(from
,oldfpt
);
1200 SplinePointReCatagorize(to
,oldtpt
);
1204 static void RemoveStupidControlPoints(SplineSet
*spl
) {
1205 double len
, normal
, dir
;
1207 BasePoint unit
, off
;
1209 /* Also remove really stupid control points: Tiny offsets pointing in */
1210 /* totally the wrong direction. Some of the TeX fonts we get have these */
1211 /* We get equally bad results with a control point that points beyond the */
1212 /* other end point */
1214 for ( s
= spl
->first
->next
; s
!=NULL
&& s
!=first
; s
=s
->to
->next
) {
1215 unit
.x
= s
->to
->me
.x
-s
->from
->me
.x
;
1216 unit
.y
= s
->to
->me
.y
-s
->from
->me
.y
;
1217 len
= sqrt(unit
.x
*unit
.x
+unit
.y
*unit
.y
);
1219 int refigure
= false;
1220 unit
.x
/= len
; unit
.y
/= len
;
1221 if ( !s
->from
->nonextcp
) {
1222 off
.x
= s
->from
->nextcp
.x
-s
->from
->me
.x
;
1223 off
.y
= s
->from
->nextcp
.y
-s
->from
->me
.y
;
1224 if ((normal
= off
.x
*unit
.y
- off
.y
*unit
.x
)<0 ) normal
= -normal
;
1225 dir
= off
.x
*unit
.x
+ off
.y
*unit
.y
;
1226 if (( normal
<dir
&& normal
<1 && dir
<0 ) || (normal
<.5 && dir
<-.5) ||
1227 (normal
<.1 && dir
>len
)) {
1228 s
->from
->nextcp
= s
->from
->me
;
1229 s
->from
->nonextcp
= true;
1233 if ( !s
->to
->noprevcp
) {
1234 off
.x
= s
->to
->me
.x
- s
->to
->prevcp
.x
;
1235 off
.y
= s
->to
->me
.y
- s
->to
->prevcp
.y
;
1236 if ((normal
= off
.x
*unit
.y
- off
.y
*unit
.x
)<0 ) normal
= -normal
;
1237 dir
= off
.x
*unit
.x
+ off
.y
*unit
.y
;
1238 if (( normal
<-dir
&& normal
<1 && dir
<0 ) || (normal
<.5 && dir
>-.5 && dir
<0) ||
1239 (normal
<.1 && dir
>len
)) {
1240 s
->to
->prevcp
= s
->to
->me
;
1241 s
->to
->noprevcp
= true;
1248 if ( first
==NULL
) first
= s
;
1252 void SSRemoveStupidControlPoints(SplineSet
*base
) {
1255 for (spl
=base
; spl
!=NULL
; spl
=spl
->next
)
1256 RemoveStupidControlPoints(spl
);
1259 static void OverlapClusterCpAngles(SplineSet
*spl
,double within
) {
1260 double len
, nlen
, plen
;
1261 double startoff
, endoff
;
1262 SplinePoint
*sp
, *nsp
, *psp
;
1263 BasePoint
*nbp
, *pbp
;
1264 BasePoint pdir
, ndir
, fpdir
, fndir
;
1267 /* If we have a junction point (right mid of 3) where the two splines */
1268 /* are almost, but not quite moving in the same direction as they go */
1269 /* away from the point, and if there is a tiny overlap because of this */
1270 /* "almost" same, then we will probably get a bit confused in remove */
1273 for ( sp
= spl
->first
; ; ) {
1274 if ( sp
->next
==NULL
)
1277 if (( !sp
->nonextcp
|| !sp
->noprevcp
) && sp
->prev
!=NULL
) {
1278 psp
= sp
->prev
->from
;
1279 nbp
= !sp
->nonextcp
? &sp
->nextcp
: !nsp
->noprevcp
? &nsp
->prevcp
: &nsp
->me
;
1280 pbp
= !sp
->noprevcp
? &sp
->prevcp
: !psp
->nonextcp
? &psp
->nextcp
: &psp
->me
;
1282 pdir
.x
= pbp
->x
-sp
->me
.x
; pdir
.y
= pbp
->y
-sp
->me
.y
;
1283 ndir
.x
= nbp
->x
-sp
->me
.x
; ndir
.y
= nbp
->y
-sp
->me
.y
;
1284 fpdir
.x
= psp
->me
.x
-sp
->me
.x
; fpdir
.y
= psp
->me
.y
-sp
->me
.y
;
1285 fndir
.x
= nsp
->me
.x
-sp
->me
.x
; fndir
.y
= nsp
->me
.y
-sp
->me
.y
;
1287 plen
= sqrt(pdir
.x
*pdir
.x
+pdir
.y
*pdir
.y
);
1289 pdir
.x
/= plen
; pdir
.y
/= plen
;
1292 nlen
= sqrt(ndir
.x
*ndir
.x
+ndir
.y
*ndir
.y
);
1294 ndir
.x
/= nlen
; ndir
.y
/= nlen
;
1297 nbad
= pbad
= false;
1298 if ( !sp
->nonextcp
&& plen
!=0 && nlen
!=0 ) {
1299 len
= sqrt(fndir
.x
*fndir
.x
+fndir
.y
*fndir
.y
);
1301 fndir
.x
/= len
; fndir
.y
/= len
;
1302 startoff
= ndir
.x
*pdir
.y
- ndir
.y
*pdir
.x
;
1303 endoff
= fndir
.x
*pdir
.y
- fndir
.y
*pdir
.x
;
1304 if (( (startoff
<0 && endoff
>0) || (startoff
>0 && endoff
<0)) &&
1305 startoff
> -within
&& startoff
< within
)
1309 if ( !sp
->noprevcp
&& plen
!=0 && nlen
!=0 ) {
1310 len
= sqrt(fpdir
.x
*fpdir
.x
+fpdir
.y
*fpdir
.y
);
1312 fpdir
.x
/= len
; fpdir
.y
/= len
;
1313 startoff
= pdir
.x
*ndir
.y
- pdir
.y
*ndir
.x
;
1314 endoff
= fpdir
.x
*ndir
.y
- fpdir
.y
*ndir
.x
;
1315 if (( (startoff
<0 && endoff
>0) || (startoff
>0 && endoff
<0)) &&
1316 startoff
> -within
&& startoff
< within
)
1320 if ( nbad
&& pbad
) {
1321 if ( ndir
.x
==0 || ndir
.y
==0 )
1323 else if ( pdir
.x
==0 || pdir
.y
==0 )
1326 if ( nbad
&& pbad
) {
1327 if ( ndir
.x
*pdir
.x
+ ndir
.y
*pdir
.y
> 0 ) {
1328 ndir
.x
= pdir
.x
= (ndir
.x
+ pdir
.x
)/2;
1329 ndir
.y
= pdir
.y
= (ndir
.x
+ pdir
.x
)/2;
1331 ndir
.x
= (ndir
.x
- pdir
.x
)/2;
1332 ndir
.y
= (ndir
.y
- pdir
.y
)/2;
1333 pdir
.x
= -ndir
.x
; pdir
.y
= -ndir
.y
;
1335 sp
->nextcp
.x
= sp
->me
.x
+ nlen
*ndir
.x
;
1336 sp
->nextcp
.y
= sp
->me
.y
+ nlen
*ndir
.y
;
1337 sp
->prevcp
.x
= sp
->me
.x
+ plen
*pdir
.x
;
1338 sp
->prevcp
.y
= sp
->me
.y
+ plen
*pdir
.y
;
1339 SplineRefigure(sp
->next
); SplineRefigure(sp
->prev
);
1340 } else if ( nbad
) {
1341 if ( ndir
.x
*pdir
.x
+ ndir
.y
*pdir
.y
< 0 ) {
1345 sp
->nextcp
.x
= sp
->me
.x
+ nlen
*pdir
.x
;
1346 sp
->nextcp
.y
= sp
->me
.y
+ nlen
*pdir
.y
;
1347 SplineRefigure(sp
->next
);
1348 } else if ( pbad
) {
1349 if ( ndir
.x
*pdir
.x
+ ndir
.y
*pdir
.y
< 0 ) {
1353 sp
->prevcp
.x
= sp
->me
.x
+ plen
*ndir
.x
;
1354 sp
->prevcp
.y
= sp
->me
.y
+ plen
*ndir
.y
;
1355 SplineRefigure(sp
->prev
);
1358 if ( nsp
==spl
->first
)
1364 void SSOverlapClusterCpAngles(SplineSet
*base
,double within
) {
1367 for (spl
=base
; spl
!=NULL
; spl
=spl
->next
)
1368 OverlapClusterCpAngles(spl
,within
);
1372 Spline
*SplineAddExtrema(Spline
*s
,int always
,real lenbound
, real offsetbound
,
1374 /* First find the extrema, if any */
1376 uint8 rmfrom
[4], rmto
[4];
1377 int p
, i
,j
, p_s
, mini
;
1379 real len
= 0; /* Init variable to silence compiler warnings */
1383 xlen
= (s
->from
->me
.x
-s
->to
->me
.x
);
1384 ylen
= (s
->from
->me
.y
-s
->to
->me
.y
);
1385 len
= xlen
*xlen
+ ylen
*ylen
;
1386 lenbound
*= lenbound
;
1387 if ( len
< lenbound
) {
1388 len
= SplineLength(s
);
1393 memset(rmfrom
,0,sizeof(rmfrom
));
1394 memset(rmto
,0,sizeof(rmto
));
1397 if ( s
->knownlinear
)
1400 if ( s
->splines
[0].a
!=0 ) {
1401 double d
= 4*s
->splines
[0].b
*s
->splines
[0].b
-4*3*s
->splines
[0].a
*s
->splines
[0].c
;
1404 t
[p
++] = CheckExtremaForSingleBitErrors(&s
->splines
[0],(-2*s
->splines
[0].b
+d
)/(2*3*s
->splines
[0].a
));
1405 t
[p
++] = CheckExtremaForSingleBitErrors(&s
->splines
[0],(-2*s
->splines
[0].b
-d
)/(2*3*s
->splines
[0].a
));
1407 } else if ( s
->splines
[0].b
!=0 )
1408 t
[p
++] = -s
->splines
[0].c
/(2*s
->splines
[0].b
);
1410 /* Generally we are only interested in extrema on long splines, or */
1411 /* extrema which are extrema for the entire contour, not just this */
1413 /* Also extrema which are very close to one of the end-points can */
1415 /* No they can't. But we need to remove the original point in this*/
1417 for ( i
=0; i
<p
; ++i
) {
1418 real x
= ((s
->splines
[0].a
*t
[i
]+s
->splines
[0].b
)*t
[i
]+s
->splines
[0].c
)*t
[i
]+s
->splines
[0].d
;
1419 real y
= ((s
->splines
[1].a
*t
[i
]+s
->splines
[1].b
)*t
[i
]+s
->splines
[1].c
)*t
[i
]+s
->splines
[1].d
;
1420 int close_from
= ( x
-s
->from
->me
.x
<offsetbound
&& x
-s
->from
->me
.x
>-offsetbound
) &&
1421 ( y
-s
->from
->me
.y
<10*offsetbound
&& y
-s
->from
->me
.y
>-10*offsetbound
);
1422 int close_to
= ( x
-s
->to
->me
.x
<offsetbound
&& x
-s
->to
->me
.x
>-offsetbound
) &&
1423 ( y
-s
->to
->me
.y
<10*offsetbound
&& y
-s
->to
->me
.y
>-10*offsetbound
);
1424 int remove_from
= close_from
&& GoodCurve(s
->from
,true);
1425 int remove_to
= close_to
&& GoodCurve(s
->to
,false);
1426 if (( x
>b
->minx
&& x
<b
->maxx
&& len
<lenbound
) ||
1427 (close_from
&& !remove_from
) || (close_to
&& !remove_to
) ) {
1429 for ( j
=i
; j
<p
; ++j
)
1433 rmfrom
[i
] = remove_from
;
1434 rmto
[i
] = remove_to
;
1440 if ( s
->splines
[1].a
!=0 ) {
1441 double d
= 4*s
->splines
[1].b
*s
->splines
[1].b
-4*3*s
->splines
[1].a
*s
->splines
[1].c
;
1444 t
[p
++] = CheckExtremaForSingleBitErrors(&s
->splines
[1],(-2*s
->splines
[1].b
+d
)/(2*3*s
->splines
[1].a
));
1445 t
[p
++] = CheckExtremaForSingleBitErrors(&s
->splines
[1],(-2*s
->splines
[1].b
-d
)/(2*3*s
->splines
[1].a
));
1447 } else if ( s
->splines
[1].b
!=0 )
1448 t
[p
++] = -s
->splines
[1].c
/(2*s
->splines
[1].b
);
1450 for ( i
=p_s
; i
<p
; ++i
) {
1451 real x
= ((s
->splines
[0].a
*t
[i
]+s
->splines
[0].b
)*t
[i
]+s
->splines
[0].c
)*t
[i
]+s
->splines
[0].d
;
1452 real y
= ((s
->splines
[1].a
*t
[i
]+s
->splines
[1].b
)*t
[i
]+s
->splines
[1].c
)*t
[i
]+s
->splines
[1].d
;
1453 int close_from
=( y
-s
->from
->me
.y
<offsetbound
&& y
-s
->from
->me
.y
>-offsetbound
) &&
1454 ( x
-s
->from
->me
.x
<offsetbound
&& x
-s
->from
->me
.x
>-offsetbound
);
1455 int close_to
= ( y
-s
->to
->me
.y
<offsetbound
&& y
-s
->to
->me
.y
>-offsetbound
) &&
1456 ( x
-s
->to
->me
.x
<offsetbound
&& x
-s
->to
->me
.x
>-offsetbound
);
1457 int remove_from
= close_from
&& GoodCurve(s
->from
,true);
1458 int remove_to
= close_to
&& GoodCurve(s
->to
,false);
1459 if (( y
>b
->miny
&& y
<b
->maxy
&& len
<lenbound
) ||
1460 (close_from
&& !remove_from
) || (close_to
&& !remove_to
) ) {
1462 for ( j
=i
; j
<p
; ++j
)
1466 rmfrom
[i
] = remove_from
;
1467 rmto
[i
] = remove_to
;
1472 /* Throw out any t values which are not between 0 and 1 */
1473 /* (we do a little fudging near the endpoints so we don't get confused */
1474 /* by rounding errors) */
1475 for ( i
=0; i
<p
; ++i
) {
1476 if ( t
[i
]>0 && t
[i
]<.05 ) {
1478 /* Expand strong gets very confused on zero-length splines so */
1479 /* don't let that happen */
1480 test
.x
= ((s
->splines
[0].a
*t
[i
]+s
->splines
[0].b
)*t
[i
]+s
->splines
[0].c
)*t
[i
]+s
->splines
[0].d
;
1481 test
.y
= ((s
->splines
[1].a
*t
[i
]+s
->splines
[1].b
)*t
[i
]+s
->splines
[1].c
)*t
[i
]+s
->splines
[1].d
;
1482 if ( test
.x
== s
->from
->me
.x
&& test
.y
==s
->from
->me
.y
)
1483 t
[i
] = 0; /* Throw it out */
1485 if ( t
[i
]<1 && t
[i
]>.95 ) {
1487 test
.x
= ((s
->splines
[0].a
*t
[i
]+s
->splines
[0].b
)*t
[i
]+s
->splines
[0].c
)*t
[i
]+s
->splines
[0].d
;
1488 test
.y
= ((s
->splines
[1].a
*t
[i
]+s
->splines
[1].b
)*t
[i
]+s
->splines
[1].c
)*t
[i
]+s
->splines
[1].d
;
1489 if ( test
.x
== s
->to
->me
.x
&& test
.y
==s
->to
->me
.y
)
1490 t
[i
] = 1.0; /* Throw it out */
1493 if ( t
[i
]<.0001 || t
[i
]>.9999 ) {
1495 for ( j
=i
; j
<p
; ++j
) {
1497 rmfrom
[j
] = rmfrom
[j
+1];
1498 rmto
[j
] = rmto
[j
+1];
1507 /* Find the smallest of all the interesting points */
1508 min
= t
[0]; mini
= 0;
1509 for ( i
=1; i
<p
; ++i
) {
1515 sp
= SplineBisect(s
,min
);
1516 /* On the mac we get rounding errors in the bisect routine */
1518 if ( (dx
= sp
->me
.x
- sp
->prevcp
.x
)<0 ) dx
=-dx
;
1519 if ( (dy
= sp
->me
.y
- sp
->prevcp
.y
)<0 ) dy
=-dy
;
1520 if ( dx
!=0 && dy
!=0 ) {
1522 sp
->prevcp
.x
= sp
->me
.x
;
1524 sp
->prevcp
.y
= sp
->me
.y
;
1526 if ( (dx
= sp
->me
.x
- sp
->nextcp
.x
)<0 ) dx
=-dx
;
1527 if ( (dy
= sp
->me
.y
- sp
->nextcp
.y
)<0 ) dy
=-dy
;
1528 if ( dx
!=0 && dy
!=0 ) {
1530 sp
->nextcp
.x
= sp
->me
.x
;
1532 sp
->nextcp
.y
= sp
->me
.y
;
1536 if ( rmfrom
[mini
] ) sp
->prev
->from
->ticked
= true;
1537 if ( rmto
[mini
] ) sp
->next
->to
->ticked
= true;
1541 /* Don't try to use any other computed t values, it is easier to */
1542 /* recompute them than to try and figure out what they map to on the */
1547 void SplineSetAddExtrema(SplineChar
*sc
, SplineSet
*ss
,enum ae_type between_selected
, int emsize
) {
1553 SplinePoint
*sp
, *nextp
;
1555 if ( between_selected
==ae_only_good
) {
1556 SplineSetQuickBounds(ss
,&b
);
1557 lenbound
= (emsize
)/32.0;
1560 between_selected
= ae_only_good_rm_later
;
1561 for ( sp
= ss
->first
; ; ) {
1563 if ( sp
->next
==NULL
)
1566 if ( sp
==ss
->first
)
1572 for ( s
= ss
->first
->next
; s
!=NULL
&& s
!=first
; s
= s
->to
->next
) {
1573 if ( between_selected
!=ae_between_selected
||
1574 (s
->from
->selected
&& s
->to
->selected
))
1575 s
= SplineAddExtrema(s
,always
,lenbound
,offsetbound
,&b
);
1576 if ( first
==NULL
) first
= s
;
1578 if ( between_selected
== ae_only_good_rm_later
) {
1579 for ( sp
= ss
->first
; ; ) {
1580 if ( sp
->next
==NULL
)
1582 nextp
= sp
->next
->to
;
1584 if ( sp
==ss
->first
)
1585 ss
->first
= ss
->last
= nextp
;
1586 SplinesRemoveBetween(sc
,sp
->prev
->from
,nextp
,1);
1589 if ( sp
==ss
->first
)
1596 char *GetNextUntitledName(void) {
1597 static int untitled_cnt
=1;
1600 sprintf( buffer
, "Untitled%d", untitled_cnt
++ );
1601 return( copy(buffer
));
1604 SplineFont
*SplineFontEmpty(void) {
1605 extern int default_fv_row_count
, default_fv_col_count
;
1609 sf
= gcalloc(1,sizeof(SplineFont
));
1610 sf
->pfminfo
.fstype
= -1;
1613 sf
->desired_row_cnt
= default_fv_row_count
; sf
->desired_col_cnt
= default_fv_col_count
;
1614 sf
->display_antialias
= default_fv_antialias
;
1615 sf
->display_bbsized
= default_fv_bbsized
;
1616 sf
->display_size
= -default_fv_font_size
;
1617 sf
->display_layer
= ly_fore
;
1618 sf
->pfminfo
.winascent_add
= sf
->pfminfo
.windescent_add
= true;
1619 sf
->pfminfo
.hheadascent_add
= sf
->pfminfo
.hheaddescent_add
= true;
1620 sf
->pfminfo
.typoascent_add
= sf
->pfminfo
.typodescent_add
= true;
1621 if ( TTFFoundry
!=NULL
)
1622 strncpy(sf
->pfminfo
.os2_vendor
,TTFFoundry
,4);
1624 memcpy(sf
->pfminfo
.os2_vendor
,"PfEd",4);
1625 sf
->for_new_glyphs
= DefaultNameListForNewFonts();
1627 sf
->creationtime
= sf
->modificationtime
= now
;
1630 sf
->layers
= gcalloc(2,sizeof(LayerInfo
));
1631 sf
->layers
[0].name
= copy(_("Back"));
1632 sf
->layers
[0].background
= true;
1633 sf
->layers
[1].name
= copy(_("Fore"));
1634 sf
->layers
[1].background
= false;
1635 sf
->grid
.background
= true;
1641 static void SFChangeXUID(SplineFont
*sf
, int random
) {
1642 char *pt
, *new, *npt
;
1645 if ( sf
->xuid
==NULL
)
1647 pt
= strrchr(sf
->xuid
,' ');
1649 pt
= strchr(sf
->xuid
,'[');
1655 val
= rand()&0xffffff;
1657 val
= strtol(pt
,NULL
,10);
1658 val
= (val
+1)&0xffffff;
1661 new = galloc(pt
-sf
->xuid
+12);
1662 strncpy(new,sf
->xuid
,pt
-sf
->xuid
);
1663 npt
= new + (pt
-sf
->xuid
);
1664 if ( npt
==new ) *npt
++ = '[';
1665 sprintf(npt
, "%d]", val
);
1666 free(sf
->xuid
); sf
->xuid
= new;
1668 sf
->changed_since_xuidchanged
= false;
1671 void SFIncrementXUID(SplineFont
*sf
) {
1672 SFChangeXUID(sf
,false);
1675 void SFRandomChangeXUID(SplineFont
*sf
) {
1676 SFChangeXUID(sf
,true);
1679 void SPWeightedAverageCps(SplinePoint
*sp
) {
1680 double pangle
, nangle
, angle
, plen
, nlen
, c
, s
;
1681 if ( sp
->noprevcp
|| sp
->nonextcp
)
1682 /*SPAverageCps(sp)*/; /* Expand Stroke wants this case to hold still */
1683 else if (( sp
->pointtype
==pt_curve
|| sp
->pointtype
==pt_hvcurve
) &&
1684 sp
->prev
&& sp
->next
) {
1685 pangle
= atan2(sp
->me
.y
-sp
->prevcp
.y
,sp
->me
.x
-sp
->prevcp
.x
);
1686 nangle
= atan2(sp
->nextcp
.y
-sp
->me
.y
,sp
->nextcp
.x
-sp
->me
.x
);
1687 if ( pangle
<0 && nangle
>0 && nangle
-pangle
>=3.1415926 )
1688 pangle
+= 2*3.1415926535897932;
1689 else if ( pangle
>0 && nangle
<0 && pangle
-nangle
>=3.1415926 )
1690 nangle
+= 2*3.1415926535897932;
1691 plen
= sqrt((sp
->me
.y
-sp
->prevcp
.y
)*(sp
->me
.y
-sp
->prevcp
.y
) +
1692 (sp
->me
.x
-sp
->prevcp
.x
)*(sp
->me
.x
-sp
->prevcp
.x
));
1693 nlen
= sqrt((sp
->nextcp
.y
-sp
->me
.y
)*(sp
->nextcp
.y
-sp
->me
.y
) +
1694 (sp
->nextcp
.x
-sp
->me
.x
)*(sp
->nextcp
.x
-sp
->me
.x
));
1696 angle
= (nangle
+pangle
)/2;
1698 angle
= (plen
*pangle
+ nlen
*nangle
)/(plen
+nlen
);
1700 c
= cos(angle
); s
=sin(angle
);
1701 sp
->nextcp
.x
= c
*nlen
+ sp
->me
.x
;
1702 sp
->nextcp
.y
= s
*nlen
+ sp
->me
.y
;
1703 sp
->prevcp
.x
= c
*plen
+ sp
->me
.x
;
1704 sp
->prevcp
.y
= s
*plen
+ sp
->me
.y
;
1705 SplineRefigure(sp
->prev
);
1706 SplineRefigure(sp
->next
);
1711 void SPAverageCps(SplinePoint
*sp
) {
1712 double pangle
, nangle
, angle
, plen
, nlen
, c
, s
;
1713 if (( sp
->pointtype
==pt_curve
|| sp
->pointtype
==pt_hvcurve
) &&
1714 sp
->prev
&& sp
->next
) {
1716 pangle
= atan2(sp
->me
.y
-sp
->prev
->from
->me
.y
,sp
->me
.x
-sp
->prev
->from
->me
.x
);
1718 pangle
= atan2(sp
->me
.y
-sp
->prevcp
.y
,sp
->me
.x
-sp
->prevcp
.x
);
1720 nangle
= atan2(sp
->next
->to
->me
.y
-sp
->me
.y
,sp
->next
->to
->me
.x
-sp
->me
.x
);
1722 nangle
= atan2(sp
->nextcp
.y
-sp
->me
.y
,sp
->nextcp
.x
-sp
->me
.x
);
1723 if ( pangle
<0 && nangle
>0 && nangle
-pangle
>=3.1415926 )
1724 pangle
+= 2*3.1415926535897932;
1725 else if ( pangle
>0 && nangle
<0 && pangle
-nangle
>=3.1415926 )
1726 nangle
+= 2*3.1415926535897932;
1727 angle
= (nangle
+pangle
)/2;
1728 plen
= -sqrt((sp
->me
.y
-sp
->prevcp
.y
)*(sp
->me
.y
-sp
->prevcp
.y
) +
1729 (sp
->me
.x
-sp
->prevcp
.x
)*(sp
->me
.x
-sp
->prevcp
.x
));
1730 nlen
= sqrt((sp
->nextcp
.y
-sp
->me
.y
)*(sp
->nextcp
.y
-sp
->me
.y
) +
1731 (sp
->nextcp
.x
-sp
->me
.x
)*(sp
->nextcp
.x
-sp
->me
.x
));
1732 c
= cos(angle
); s
=sin(angle
);
1733 sp
->nextcp
.x
= c
*nlen
+ sp
->me
.x
;
1734 sp
->nextcp
.y
= s
*nlen
+ sp
->me
.y
;
1735 sp
->prevcp
.x
= c
*plen
+ sp
->me
.x
;
1736 sp
->prevcp
.y
= s
*plen
+ sp
->me
.y
;
1737 SplineRefigure(sp
->prev
);
1738 SplineRefigure(sp
->next
);
1739 } else if ( sp
->pointtype
==pt_tangent
&& sp
->prev
&& sp
->next
) {
1740 if ( !sp
->noprevcp
) {
1741 nangle
= atan2(sp
->next
->to
->me
.y
-sp
->me
.y
,sp
->next
->to
->me
.x
-sp
->me
.x
);
1742 plen
= -sqrt((sp
->me
.y
-sp
->prevcp
.y
)*(sp
->me
.y
-sp
->prevcp
.y
) +
1743 (sp
->me
.x
-sp
->prevcp
.x
)*(sp
->me
.x
-sp
->prevcp
.x
));
1744 c
= cos(nangle
); s
=sin(nangle
);
1745 sp
->prevcp
.x
= c
*plen
+ sp
->me
.x
;
1746 sp
->prevcp
.y
= s
*plen
+ sp
->me
.y
;
1747 SplineRefigure(sp
->prev
);
1749 if ( !sp
->nonextcp
) {
1750 pangle
= atan2(sp
->me
.y
-sp
->prev
->from
->me
.y
,sp
->me
.x
-sp
->prev
->from
->me
.x
);
1751 nlen
= sqrt((sp
->nextcp
.y
-sp
->me
.y
)*(sp
->nextcp
.y
-sp
->me
.y
) +
1752 (sp
->nextcp
.x
-sp
->me
.x
)*(sp
->nextcp
.x
-sp
->me
.x
));
1753 c
= cos(pangle
); s
=sin(pangle
);
1754 sp
->nextcp
.x
= c
*nlen
+ sp
->me
.x
;
1755 sp
->nextcp
.y
= s
*nlen
+ sp
->me
.y
;
1756 SplineRefigure(sp
->next
);
1762 void SplineCharTangentNextCP(SplinePoint
*sp
) {
1764 BasePoint
*bp
, unit
;
1765 extern int snaptoint
;
1767 if ( sp
->prev
==NULL
)
1769 bp
= &sp
->prev
->from
->me
;
1771 unit
.y
= sp
->me
.y
-bp
->y
; unit
.x
= sp
->me
.x
-bp
->x
;
1772 len
= sqrt( unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1777 len
= sqrt((sp
->nextcp
.y
-sp
->me
.y
)*(sp
->nextcp
.y
-sp
->me
.y
) + (sp
->nextcp
.x
-sp
->me
.x
)*(sp
->nextcp
.x
-sp
->me
.x
));
1778 sp
->nextcp
.x
= sp
->me
.x
+ len
*unit
.x
;
1779 sp
->nextcp
.y
= sp
->me
.y
+ len
*unit
.y
;
1781 sp
->nextcp
.x
= rint(sp
->nextcp
.x
);
1782 sp
->nextcp
.y
= rint(sp
->nextcp
.y
);
1784 sp
->nextcp
.x
= rint(sp
->nextcp
.x
*1024)/1024;
1785 sp
->nextcp
.y
= rint(sp
->nextcp
.y
*1024)/1024;
1787 if ( sp
->next
!=NULL
&& sp
->next
->order2
)
1788 sp
->next
->to
->prevcp
= sp
->nextcp
;
1791 void SplineCharTangentPrevCP(SplinePoint
*sp
) {
1793 BasePoint
*bp
, unit
;
1794 extern int snaptoint
;
1796 if ( sp
->next
==NULL
)
1798 bp
= &sp
->next
->to
->me
;
1800 unit
.y
= sp
->me
.y
-bp
->y
; unit
.x
= sp
->me
.x
-bp
->x
;
1801 len
= sqrt( unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1806 len
= sqrt((sp
->prevcp
.y
-sp
->me
.y
)*(sp
->prevcp
.y
-sp
->me
.y
) + (sp
->prevcp
.x
-sp
->me
.x
)*(sp
->prevcp
.x
-sp
->me
.x
));
1807 sp
->prevcp
.x
= sp
->me
.x
+ len
*unit
.x
;
1808 sp
->prevcp
.y
= sp
->me
.y
+ len
*unit
.y
;
1810 sp
->prevcp
.x
= rint(sp
->prevcp
.x
);
1811 sp
->prevcp
.y
= rint(sp
->prevcp
.y
);
1813 sp
->prevcp
.x
= rint(sp
->prevcp
.x
*1024)/1024;
1814 sp
->prevcp
.y
= rint(sp
->prevcp
.y
*1024)/1024;
1816 if ( sp
->prev
!=NULL
&& sp
->prev
->order2
)
1817 sp
->prev
->from
->nextcp
= sp
->prevcp
;
1820 static void BP_HVForce(BasePoint
*vector
) {
1821 /* Force vector to be horizontal/vertical */
1824 if ( (dx
= vector
->x
)<0 ) dx
= -dx
;
1825 if ( (dy
= vector
->y
)<0 ) dy
= -dy
;
1826 if ( dx
==0 || dy
==0 )
1828 len
= sqrt(dx
*dx
+ dy
*dy
);
1830 vector
->x
= vector
->x
<0 ? -len
: len
;
1833 vector
->y
= vector
->y
<0 ? -len
: len
;
1838 #define NICE_PROPORTION .39
1839 void SplineCharDefaultNextCP(SplinePoint
*base
) {
1840 SplinePoint
*prev
=NULL
, *next
;
1841 double len
, plen
, ulen
;
1843 extern int snaptoint
;
1845 if ( base
->next
==NULL
)
1847 if ( base
->next
->order2
) {
1848 SplineRefigureFixup(base
->next
);
1851 if ( !base
->nextcpdef
) {
1852 if ( base
->pointtype
==pt_tangent
)
1853 SplineCharTangentNextCP(base
);
1856 next
= base
->next
->to
;
1857 if ( base
->prev
!=NULL
)
1858 prev
= base
->prev
->from
;
1860 len
= NICE_PROPORTION
* sqrt((base
->me
.x
-next
->me
.x
)*(base
->me
.x
-next
->me
.x
) +
1861 (base
->me
.y
-next
->me
.y
)*(base
->me
.y
-next
->me
.y
));
1862 unit
.x
= next
->me
.x
- base
->me
.x
;
1863 unit
.y
= next
->me
.y
- base
->me
.y
;
1864 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1866 unit
.x
/= ulen
, unit
.y
/= ulen
;
1867 base
->nonextcp
= false;
1869 if ( base
->pointtype
== pt_curve
|| base
->pointtype
== pt_hvcurve
) {
1870 if ( prev
!=NULL
&& (base
->prevcpdef
|| base
->noprevcp
)) {
1871 unit
.x
= next
->me
.x
- prev
->me
.x
;
1872 unit
.y
= next
->me
.y
- prev
->me
.y
;
1873 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1875 unit
.x
/= ulen
, unit
.y
/= ulen
;
1876 if ( base
->pointtype
== pt_hvcurve
)
1878 plen
= sqrt((base
->prevcp
.x
-base
->me
.x
)*(base
->prevcp
.x
-base
->me
.x
) +
1879 (base
->prevcp
.y
-base
->me
.y
)*(base
->prevcp
.y
-base
->me
.y
));
1880 base
->prevcp
.x
= base
->me
.x
- plen
*unit
.x
;
1881 base
->prevcp
.y
= base
->me
.y
- plen
*unit
.y
;
1883 base
->prevcp
.x
= rint(base
->prevcp
.x
);
1884 base
->prevcp
.y
= rint(base
->prevcp
.y
);
1886 SplineRefigureFixup(base
->prev
);
1887 } else if ( prev
!=NULL
) {
1888 /* The prev control point is fixed. So we've got to use the same */
1890 unit
.x
= base
->me
.x
-base
->prevcp
.x
;
1891 unit
.y
= base
->me
.y
-base
->prevcp
.y
;
1892 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1894 unit
.x
/= ulen
, unit
.y
/= ulen
;
1896 base
->prevcp
= base
->me
;
1897 base
->noprevcp
= true;
1898 base
->prevcpdef
= true;
1900 if ( base
->pointtype
== pt_hvcurve
)
1902 } else if ( base
->pointtype
== pt_corner
) {
1903 if ( next
->pointtype
!= pt_curve
&& next
->pointtype
!= pt_hvcurve
) {
1904 base
->nonextcp
= true;
1906 } else /* tangent */ {
1907 if ( next
->pointtype
!= pt_curve
) {
1908 base
->nonextcp
= true;
1911 if ( !base
->noprevcp
) {
1912 plen
= sqrt((base
->prevcp
.x
-base
->me
.x
)*(base
->prevcp
.x
-base
->me
.x
) +
1913 (base
->prevcp
.y
-base
->me
.y
)*(base
->prevcp
.y
-base
->me
.y
));
1914 base
->prevcp
.x
= base
->me
.x
- plen
*unit
.x
;
1915 base
->prevcp
.y
= base
->me
.y
- plen
*unit
.y
;
1916 SplineRefigureFixup(base
->prev
);
1918 unit
.x
= base
->me
.x
-prev
->me
.x
;
1919 unit
.y
= base
->me
.y
-prev
->me
.y
;
1920 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1922 unit
.x
/= ulen
, unit
.y
/= ulen
;
1926 if ( base
->nonextcp
)
1927 base
->nextcp
= base
->me
;
1929 base
->nextcp
.x
= base
->me
.x
+ len
*unit
.x
;
1930 base
->nextcp
.y
= base
->me
.y
+ len
*unit
.y
;
1932 base
->nextcp
.x
= rint(base
->nextcp
.x
);
1933 base
->nextcp
.y
= rint(base
->nextcp
.y
);
1935 base
->nextcp
.x
= rint(base
->nextcp
.x
*1024)/1024;
1936 base
->nextcp
.y
= rint(base
->nextcp
.y
*1024)/1024;
1938 if ( base
->next
!= NULL
)
1939 SplineRefigureFixup(base
->next
);
1943 void SplineCharDefaultPrevCP(SplinePoint
*base
) {
1944 SplinePoint
*next
=NULL
, *prev
;
1945 double len
, nlen
, ulen
;
1947 extern int snaptoint
;
1949 if ( base
->prev
==NULL
)
1951 if ( base
->prev
->order2
) {
1952 SplineRefigureFixup(base
->prev
);
1955 if ( !base
->prevcpdef
) {
1956 if ( base
->pointtype
==pt_tangent
)
1957 SplineCharTangentPrevCP(base
);
1960 prev
= base
->prev
->from
;
1961 if ( base
->next
!=NULL
)
1962 next
= base
->next
->to
;
1964 len
= NICE_PROPORTION
* sqrt((base
->me
.x
-prev
->me
.x
)*(base
->me
.x
-prev
->me
.x
) +
1965 (base
->me
.y
-prev
->me
.y
)*(base
->me
.y
-prev
->me
.y
));
1966 unit
.x
= prev
->me
.x
- base
->me
.x
;
1967 unit
.y
= prev
->me
.y
- base
->me
.y
;
1968 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1970 unit
.x
/= ulen
, unit
.y
/= ulen
;
1971 base
->noprevcp
= false;
1973 if ( base
->pointtype
== pt_curve
|| base
->pointtype
== pt_hvcurve
) {
1974 if ( next
!=NULL
&& (base
->nextcpdef
|| base
->nonextcp
)) {
1975 unit
.x
= prev
->me
.x
- next
->me
.x
;
1976 unit
.y
= prev
->me
.y
- next
->me
.y
;
1977 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1979 unit
.x
/= ulen
, unit
.y
/= ulen
;
1980 if ( base
->pointtype
== pt_hvcurve
)
1982 nlen
= sqrt((base
->nextcp
.x
-base
->me
.x
)*(base
->nextcp
.x
-base
->me
.x
) +
1983 (base
->nextcp
.y
-base
->me
.y
)*(base
->nextcp
.y
-base
->me
.y
));
1984 base
->nextcp
.x
= base
->me
.x
- nlen
*unit
.x
;
1985 base
->nextcp
.y
= base
->me
.y
- nlen
*unit
.y
;
1987 base
->nextcp
.x
= rint(base
->nextcp
.x
);
1988 base
->nextcp
.y
= rint(base
->nextcp
.y
);
1990 SplineRefigureFixup(base
->next
);
1991 } else if ( next
!=NULL
) {
1992 /* The next control point is fixed. So we got to use the same */
1994 unit
.x
= base
->me
.x
-base
->nextcp
.x
;
1995 unit
.y
= base
->me
.y
-base
->nextcp
.y
;
1996 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1998 unit
.x
/= ulen
, unit
.y
/= ulen
;
2000 base
->nextcp
= base
->me
;
2001 base
->nonextcp
= true;
2002 base
->nextcpdef
= true;
2004 if ( base
->pointtype
== pt_hvcurve
)
2006 } else if ( base
->pointtype
== pt_corner
) {
2007 if ( prev
->pointtype
!= pt_curve
&& prev
->pointtype
!= pt_hvcurve
) {
2008 base
->noprevcp
= true;
2010 } else /* tangent */ {
2011 if ( prev
->pointtype
!= pt_curve
) {
2012 base
->noprevcp
= true;
2015 if ( !base
->nonextcp
) {
2016 nlen
= sqrt((base
->nextcp
.x
-base
->me
.x
)*(base
->nextcp
.x
-base
->me
.x
) +
2017 (base
->nextcp
.y
-base
->me
.y
)*(base
->nextcp
.y
-base
->me
.y
));
2018 base
->nextcp
.x
= base
->me
.x
- nlen
*unit
.x
;
2019 base
->nextcp
.y
= base
->me
.y
- nlen
*unit
.y
;
2020 SplineRefigureFixup(base
->next
);
2022 unit
.x
= base
->me
.x
-next
->me
.x
;
2023 unit
.y
= base
->me
.y
-next
->me
.y
;
2024 ulen
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
2026 unit
.x
/= ulen
, unit
.y
/= ulen
;
2030 if ( base
->noprevcp
)
2031 base
->prevcp
= base
->me
;
2033 base
->prevcp
.x
= base
->me
.x
+ len
*unit
.x
;
2034 base
->prevcp
.y
= base
->me
.y
+ len
*unit
.y
;
2036 base
->prevcp
.x
= rint(base
->prevcp
.x
);
2037 base
->prevcp
.y
= rint(base
->prevcp
.y
);
2039 base
->prevcp
.x
= rint(base
->prevcp
.x
*1024)/1024;
2040 base
->prevcp
.y
= rint(base
->prevcp
.y
*1024)/1024;
2042 if ( base
->prev
!=NULL
)
2043 SplineRefigureFixup(base
->prev
);
2048 SplineSet
*SplineSetReverse(SplineSet
*spl
) {
2049 Spline
*spline
, *first
, *next
;
2053 /* reverse the splineset so that what was the start point becomes the end */
2054 /* and vice versa. This entails reversing every individual spline, and */
2058 spline
= spl
->first
->next
;
2060 return( spl
); /* Only one point, reversal is meaningless */
2062 tp
= spline
->from
->nextcp
;
2063 spline
->from
->nextcp
= spline
->from
->prevcp
;
2064 spline
->from
->prevcp
= tp
;
2065 bool = spline
->from
->nonextcp
;
2066 spline
->from
->nonextcp
= spline
->from
->noprevcp
;
2067 spline
->from
->noprevcp
= bool;
2068 bool = spline
->from
->nextcpdef
;
2069 spline
->from
->nextcpdef
= spline
->from
->prevcpdef
;
2070 spline
->from
->prevcpdef
= bool;
2072 for ( ; spline
!=NULL
&& spline
!=first
; spline
=next
) {
2073 next
= spline
->to
->next
;
2075 if ( spline
->to
!=spl
->first
) { /* On a closed spline don't want to reverse the first point twice */
2076 tp
= spline
->to
->nextcp
;
2077 spline
->to
->nextcp
= spline
->to
->prevcp
;
2078 spline
->to
->prevcp
= tp
;
2079 bool = spline
->to
->nonextcp
;
2080 spline
->to
->nonextcp
= spline
->to
->noprevcp
;
2081 spline
->to
->noprevcp
= bool;
2082 bool = spline
->to
->nextcpdef
;
2083 spline
->to
->nextcpdef
= spline
->to
->prevcpdef
;
2084 spline
->to
->prevcpdef
= bool;
2088 spline
->to
= spline
->from
;
2089 spline
->from
= temp
;
2090 spline
->from
->next
= spline
;
2091 spline
->to
->prev
= spline
;
2092 SplineRefigure(spline
);
2093 if ( first
==NULL
) first
= spline
;
2096 if ( spl
->first
!=spl
->last
) {
2098 spl
->first
= spl
->last
;
2100 spl
->first
->prev
= NULL
;
2101 spl
->last
->next
= NULL
;
2107 static void SplineSetsUntick(SplineSet
*spl
) {
2108 Spline
*spline
, *first
;
2110 while ( spl
!=NULL
) {
2112 spl
->first
->isintersection
= false;
2113 for ( spline
=spl
->first
->next
; spline
!=first
&& spline
!=NULL
; spline
= spline
->to
->next
) {
2114 spline
->isticked
= false;
2115 spline
->isneeded
= false;
2116 spline
->isunneeded
= false;
2117 spline
->ishorvert
= false;
2118 spline
->to
->isintersection
= false;
2119 if ( first
==NULL
) first
= spline
;
2125 static void SplineSetTick(SplineSet
*spl
) {
2126 Spline
*spline
, *first
;
2129 for ( spline
=spl
->first
->next
; spline
!=first
&& spline
!=NULL
; spline
= spline
->to
->next
) {
2130 spline
->isticked
= true;
2131 if ( first
==NULL
) first
= spline
;
2135 static SplineSet
*SplineSetOfSpline(SplineSet
*spl
,Spline
*search
) {
2136 Spline
*spline
, *first
;
2138 while ( spl
!=NULL
) {
2140 for ( spline
=spl
->first
->next
; spline
!=first
&& spline
!=NULL
; spline
= spline
->to
->next
) {
2141 if ( spline
==search
)
2143 if ( first
==NULL
) first
= spline
;
2150 static int SplineInSplineSet(Spline
*spline
, SplineSet
*spl
) {
2154 for ( s
= spl
->first
->next
; s
!=NULL
&& s
!=first
; s
= s
->to
->next
) {
2157 if ( first
==NULL
) first
= s
;
2162 #include "edgelist.h"
2164 static void EdgeListReverse(EdgeList
*es
, SplineSet
*spl
) {
2167 if ( es
->edges
!=NULL
) {
2168 for ( i
=0; i
<es
->cnt
; ++i
) {
2170 for ( e
= es
->edges
[i
]; e
!=NULL
; e
= e
->esnext
) {
2171 if ( SplineInSplineSet(e
->spline
,spl
)) {
2173 e
->t_mmin
= 1-e
->t_mmin
;
2174 e
->t_mmax
= 1-e
->t_mmax
;
2175 e
->t_cur
= 1-e
->t_cur
;
2182 static int SSCheck(SplineSet
*base
,Edge
*active
, int up
, EdgeList
*es
,int *changed
) {
2184 if ( active
->spline
->isticked
)
2186 spl
= SplineSetOfSpline(base
,active
->spline
);
2187 if ( active
->up
!=up
) {
2188 SplineSetReverse(spl
);
2190 EdgeListReverse(es
,spl
);
2197 /* The idea behind SplineSetsCorrect is simple. However there are many splinesets */
2198 /* where it is impossible, so bear in mind that this only works for nice */
2199 /* splines. Figure 8's, interesecting splines all cause problems */
2200 /* The outermost spline should be clockwise (up), the next splineset we find */
2201 /* should be down, if it isn't reverse it (if it's already been dealt with */
2202 /* then ignore it) */
2203 SplineSet
*SplineSetsCorrect(SplineSet
*base
,int *changed
) {
2205 int sscnt
, check_cnt
;
2208 Edge
*active
=NULL
, *apt
, *pr
, *e
;
2213 SplineSetsUntick(base
);
2214 for (sscnt
=0,spl
=base
; spl
!=NULL
; spl
=spl
->next
, ++sscnt
);
2216 SplineSetFindBounds(base
,&b
);
2217 memset(&es
,'\0',sizeof(es
));
2219 es
.mmin
= floor(b
.miny
*es
.scale
);
2220 es
.mmax
= ceil(b
.maxy
*es
.scale
);
2221 es
.omin
= b
.minx
*es
.scale
;
2222 es
.omax
= b
.maxx
*es
.scale
;
2223 es
.layer
= ly_fore
; /* Not meaningful */
2225 /* Give up if we are given unreasonable values (ie. if rounding errors might screw us up) */
2226 if ( es
.mmin
<1e5
&& es
.mmax
>-1e5
&& es
.omin
<1e5
&& es
.omax
>-1e5
) {
2227 es
.cnt
= (int) (es
.mmax
-es
.mmin
) + 1;
2228 es
.edges
= gcalloc(es
.cnt
,sizeof(Edge
*));
2229 es
.interesting
= gcalloc(es
.cnt
,sizeof(char));
2231 es
.major
= 1; es
.other
= 0;
2232 FindEdgesSplineSet(base
,&es
,false);
2235 for ( i
=0; i
<es
.cnt
&& check_cnt
<sscnt
; ++i
) {
2236 active
= ActiveEdgesRefigure(&es
,active
,i
);
2237 if ( es
.edges
[i
]!=NULL
)
2238 continue; /* Just too hard to get the edges sorted when we are at a start vertex */
2239 if ( /*es.edges[i]==NULL &&*/ !es
.interesting
[i
] &&
2240 !(i
>0 && es
.interesting
[i
-1]) && !(i
>0 && es
.edges
[i
-1]!=NULL
) &&
2241 !(i
<es
.cnt
-1 && es
.edges
[i
+1]!=NULL
) &&
2242 !(i
<es
.cnt
-1 && es
.interesting
[i
+1])) /* interesting things happen when we add (or remove) entries */
2243 continue; /* and where we have extrema */
2244 for ( apt
=active
; apt
!=NULL
; apt
= e
) {
2245 check_cnt
+= SSCheck(base
,apt
,true,&es
,changed
);
2246 winding
= apt
->up
?1:-1;
2247 for ( pr
=apt
, e
=apt
->aenext
; e
!=NULL
&& winding
!=0; pr
=e
, e
=e
->aenext
) {
2248 if ( !e
->spline
->isticked
)
2249 check_cnt
+= SSCheck(base
,e
,winding
<0,&es
,changed
);
2250 if ( pr
->up
!=e
->up
)
2251 winding
+= (e
->up
?1:-1);
2252 else if ( (pr
->before
==e
|| pr
->after
==e
) &&
2253 (( pr
->mmax
==i
&& e
->mmin
==i
) ||
2254 ( pr
->mmin
==i
&& e
->mmax
==i
)) )
2255 /* This just continues the line and doesn't change count */;
2257 winding
+= (e
->up
?1:-1);
2259 /* color a horizontal line that comes out of the last vertex */
2260 if ( e
!=NULL
&& (e
->before
==pr
|| e
->after
==pr
) &&
2261 (( pr
->mmax
==i
&& e
->mmin
==i
) ||
2262 ( pr
->mmin
==i
&& e
->mmax
==i
)) ) {
2274 int SplinePointListIsClockwise(const SplineSet
*spl
) {
2276 EI
*active
=NULL
, *apt
, *e
;
2277 int i
, change
,waschange
;
2280 int ret
= -1, maybe
=-1;
2283 if ( spl
->first
!=spl
->last
|| spl
->first
->next
== NULL
)
2284 return( -1 ); /* Open paths, (open paths with only one point are a special case) */
2286 memset(&el
,'\0',sizeof(el
));
2287 memset(&dummy
,'\0',sizeof(dummy
));
2288 memset(layers
,0,sizeof(layers
));
2290 dummy
.layers
= layers
;
2291 dummy
.layer_cnt
= 2;
2292 dummy
.layers
[ly_fore
].splines
= (SplineSet
*) spl
;
2293 next
= spl
->next
; ((SplineSet
*) spl
)->next
= NULL
;
2294 ELFindEdges(&dummy
,&el
);
2295 if ( el
.coordmax
[1]-el
.coordmin
[1] > 1.e6
) {
2296 LogError( _("Warning: Unreasonably big splines. They will be ignored.\n") );
2300 ELOrder(&el
,el
.major
);
2303 for ( i
=0; i
<el
.cnt
&& ret
==-1; ++i
) {
2304 active
= EIActiveEdgesRefigure(&el
,active
,i
,1,&change
);
2305 if ( el
.ordered
[i
]!=NULL
|| el
.ends
[i
] || waschange
|| change
) {
2309 continue; /* Just too hard to get the edges sorted when we are at a start vertex */
2312 for ( apt
=active
; apt
!=NULL
&& ret
==-1; apt
= e
) {
2313 if ( EISkipExtremum(apt
,i
+el
.low
,1)) {
2314 e
= apt
->aenext
->aenext
;
2324 ((SplineSet
*) spl
)->next
= next
;