diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineoverlap.c')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineoverlap.c | 2396 |
1 files changed, 2396 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineoverlap.c b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineoverlap.c new file mode 100644 index 00000000000..1b459508f2a --- /dev/null +++ b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineoverlap.c @@ -0,0 +1,2396 @@ +/* Copyright (C) 2000-2008 by George Williams */ +/* + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + + * The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO + * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "pfaedit.h" +#include "splinefont.h" +#include "edgelist2.h" +#include <math.h> +#ifdef HAVE_IEEEFP_H +# include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */ +#endif +#include <stdarg.h> + +#include <gwidget.h> /* For PostNotice */ + +/* First thing we do is divide each spline into a set of sub-splines each of */ +/* which is monotonic in both x and y (always increasing or decreasing) */ +/* Then we compare each monotonic spline with every other one and see if they*/ +/* intersect. If they do, split each up into sub-sub-segments and create an*/ +/* intersection point (note we need to be a little careful if an intersec- */ +/* tion happens at an end point. We don't need to create a intersection for */ +/* two adjacent splines, there isn't a real intersection... but if a third */ +/* spline crosses that point (or ends there) then all three (four) splines */ +/* need to be joined into an intersection point) */ +/* Nasty things happen if splines are coincident. They will almost never be */ +/* perfectly coincident and will keep crossing and recrossing as rounding */ +/* errors suggest one is before the other. Look for coincident splines and */ +/* treat the places they start and stop being coincident as intersections */ +/* then when we find needed splines below look for these guys and ignore */ +/* recrossings of splines which are close together */ +/* Figure out if each monotonic sub-spline is needed or not */ +/* (Note: It was tempting to split the bits up into real splines rather */ +/* than keeping them as sub-sections of the original. Unfortunately this */ +/* splitting introduced rounding errors which meant that we got more */ +/* intersections, which meant that splines could be both needed and un. */ +/* so I don't do that until later) */ +/* if the spline hasn't been tagged yet: */ +/* does the spline change greater in x or y? */ +/* draw a line parallel to the OTHER axis which hits our spline and doesn't*/ +/* hit any endpoints (or intersections, which are end points too now) */ +/* count the winding number (as we do this we can mark other splines as */ +/* needed or not) and figure out if our spline is needed */ +/* So run through the list of intersections */ +/* At an intersection there should be an even number of needed monos. */ +/* Use this as the basis of a new splineset, trace it around until */ +/* we get back to the start intersection (should happen) */ +/* (Note: We may need to reverse a monotonic sub-spline or two) */ +/* As we go, mark each monotonic as having been used */ +/* Keep doing this until all needed exits from all intersections have been */ +/* used. */ +/* The free up our temporary data structures, merge in any open splinesets */ +/* free the old closed splinesets */ + +typedef struct mlist { + Spline *s; + Monotonic *m; /* May get slightly munched but will */ + /* always have right spline. we fix when we need it */ + extended t; + int isend; + BasePoint unit; + struct mlist *next; +} MList; + +typedef struct intersection { + MList *monos; + BasePoint inter; + struct intersection *next; +} Intersection; + +static char *glyphname=NULL; + +static void SOError(char *format,...) { + va_list ap; + va_start(ap,format); + if ( glyphname==NULL ) + fprintf(stderr, "Internal Error: " ); + else + fprintf(stderr, "Internal Error in %s: ", glyphname ); + vfprintf(stderr,format,ap); +} + +static Monotonic *SplineToMonotonic(Spline *s,extended startt,extended endt, + Monotonic *last,int exclude) { + Monotonic *m; + BasePoint start, end; + + start.x = ((s->splines[0].a*startt+s->splines[0].b)*startt+s->splines[0].c)*startt + + s->splines[0].d; + start.y = ((s->splines[1].a*startt+s->splines[1].b)*startt+s->splines[1].c)*startt + + s->splines[1].d; + end.x = ((s->splines[0].a*endt+s->splines[0].b)*endt+s->splines[0].c)*endt + + s->splines[0].d; + end.y = ((s->splines[1].a*endt+s->splines[1].b)*endt+s->splines[1].c)*endt + + s->splines[1].d; + if ( (real) (((start.x+end.x)/2)==start.x || (real) ((start.x+end.x)/2)==end.x) && + (real) (((start.y+end.y)/2)==start.y || (real) ((start.y+end.y)/2)==end.y) ) { + /* The distance between the two extrema is so small */ + /* as to be unobservable. In other words we'd end up with a zero*/ + /* length spline */ + if ( endt==1.0 && last!=NULL && last->s==s ) + last->tend = endt; +return( last ); + } + + m = chunkalloc(sizeof(Monotonic)); + m->s = s; + m->tstart = startt; + m->tend = endt; + m->exclude = exclude; + + if ( end.x>start.x ) { + m->xup = true; + m->b.minx = start.x; + m->b.maxx = end.x; + } else { + m->b.minx = end.x; + m->b.maxx = start.x; + } + if ( end.y>start.y ) { + m->yup = true; + m->b.miny = start.y; + m->b.maxy = end.y; + } else { + m->b.miny = end.y; + m->b.maxy = start.y; + } + + if ( last!=NULL ) { + last->next = m; + last->linked = m; + m->prev = last; + } +return( m ); +} + +static int SSIsSelected(SplineSet *spl) { + SplinePoint *sp; + + for ( sp=spl->first; ; ) { + if ( sp->selected ) +return( true ); + if ( sp->next==NULL ) +return( false ); + sp = sp->next->to; + if ( sp==spl->first ) +return( false ); + } +} + +static int BpSame(BasePoint *bp1, BasePoint *bp2) { + BasePoint mid; + + mid.x = (bp1->x+bp2->x)/2; mid.y = (bp1->y+bp2->y)/2; + if ( (bp1->x==mid.x || bp2->x==mid.x) && + (bp1->y==mid.y || bp2->y==mid.y)) +return( true ); + +return( false ); +} + +static int SSRmNullSplines(SplineSet *spl) { + Spline *s, *first, *next; + + first = NULL; + for ( s=spl->first->next ; s!=first; s=next ) { + next = s->to->next; + if ( ((s->splines[0].a>-.01 && s->splines[0].a<.01 && + s->splines[0].b>-.01 && s->splines[0].b<.01 && + s->splines[1].a>-.01 && s->splines[1].a<.01 && + s->splines[1].b>-.01 && s->splines[1].b<.01) || + /* That describes a null spline (a line between the same end-point) */ + RealNear((s->from->nextcp.x-s->from->me.x)*(s->to->me.y-s->to->prevcp.y)- + (s->from->nextcp.y-s->from->me.y)*(s->to->me.x-s->to->prevcp.x),0)) && + /* And the above describes a point with a spline between it */ + /* and itself where the spline covers no area (the two cps */ + /* point in the same direction) */ + BpSame(&s->from->me,&s->to->me)) { + if ( next==s ) +return( true ); + if ( next->from->selected ) s->from->selected = true; + s->from->next = next; + s->from->nextcp = next->from->nextcp; + s->from->nonextcp = next->from->nonextcp; + s->from->nextcpdef = next->from->nextcpdef; + SplinePointFree(next->from); + if ( spl->first==next->from ) + spl->last = spl->first = s->from; + next->from = s->from; + SplineFree(s); + } else { + if ( first==NULL ) + first = s; + } + } +return( false ); +} + +static Monotonic *SSToMContour(SplineSet *spl, Monotonic *start, + Monotonic **end, enum overlap_type ot) { + extended ts[4]; + Spline *first, *s; + Monotonic *head=NULL, *last=NULL; + int cnt, i, selected = false; + extended lastt; + + if ( spl->first->prev==NULL ) +return( start ); /* Open contours have no interior, ignore 'em */ + if ( spl->first->prev->from==spl->first && + spl->first->noprevcp && spl->first->nonextcp ) +return( start ); /* Let's just remove single points */ + + if ( ot==over_rmselected || ot==over_intersel || ot==over_fisel || ot==over_exclude ) { + selected = SSIsSelected(spl); + if ( ot==over_rmselected || ot==over_intersel || ot==over_fisel ) { + if ( !selected ) +return( start ); + selected = false; + } + } + + /* We blow up on zero length splines. And a zero length contour is nasty */ + if ( SSRmNullSplines(spl)) +return( start ); + + first = NULL; + for ( s=spl->first->next; s!=first; s=s->to->next ) { + if ( first==NULL ) first = s; + cnt = Spline2DFindExtrema(s,ts); + lastt = 0; + for ( i=0; i<cnt; ++i ) { + last = SplineToMonotonic(s,lastt,ts[i],last,selected); + if ( head==NULL ) head = last; + lastt=ts[i]; + } + if ( lastt!=1.0 ) { + last = SplineToMonotonic(s,lastt,1.0,last,selected); + if ( head==NULL ) head = last; + } + } + head->prev = last; + last->next = head; + if ( start==NULL ) + start = head; + else + (*end)->linked = head; + *end = last; +return( start ); +} + +static Monotonic *SSsToMContours(SplineSet *spl, enum overlap_type ot) { + Monotonic *head=NULL, *last = NULL; + + while ( spl!=NULL ) { + if ( spl->first->prev!=NULL ) + head = SSToMContour(spl,head,&last,ot); + spl = spl->next; + } +return( head ); +} + +static void _AddSpline(Intersection *il,Monotonic *m,extended t,int isend) { + MList *ml; + + for ( ml=il->monos; ml!=NULL; ml=ml->next ) { + if ( ml->s==m->s && RealNear( ml->t,t ) && ml->isend==isend ) +return; + } + + ml = chunkalloc(sizeof(MList)); + ml->next = il->monos; + il->monos = ml; + ml->s = m->s; + ml->m = m; /* This may change. We'll fix it up later */ + ml->t = t; + ml->isend = isend; + if ( isend ) { + if ( m->end!=NULL && m->end!=il ) + SOError("Resetting end.\n"); + m->end = il; + } else { + if ( m->start!=NULL && m->start!=il ) + SOError("Resetting start.\n"); + m->start = il; + } +return; +} + +static void AddSpline(Intersection *il,Monotonic *m,extended t) { + MList *ml; + + if ( m->start==il || m->end==il ) +return; + + for ( ml=il->monos; ml!=NULL; ml=ml->next ) { + if ( ml->s==m->s && RealWithin( ml->t,t,.0001 )) +return; + } + + ml = chunkalloc(sizeof(MList)); + ml->next = il->monos; + il->monos = ml; + ml->s = m->s; + ml->m = m; /* This may change. We'll fix it up later */ + ml->t = t; + ml->isend = true; + if ( t-m->tstart < m->tend-t && RealNear(m->tstart,t) ) { + if ( m->start!=NULL && m->start!=il ) + SOError("Resetting start.\n"); + m->start = il; + ml->t = m->tstart; + ml->isend = false; + _AddSpline(il,m->prev,m->prev->tend,true); + } else if ( RealNear(m->tend,t)) { + if ( m->end!=NULL && m->end!=il ) + SOError("Resetting end.\n"); + m->end = il; + ml->t = m->tend; + _AddSpline(il,m->next,m->next->tstart,false); + } else { + /* Ok, if we've got a new intersection on this spline then break up */ + /* the monotonic into two bits which end and start at this inter */ + if ( t<m->tstart || t>m->tend ) + SOError( "Attempt to subset monotonic rejoin inappropriately: %g should be [%g,%g]\n", + t, m->tstart, m->tend ); + else { + /* It is monotonic, so a subset of it must also be */ + Monotonic *m2 = chunkalloc(sizeof(Monotonic)); + BasePoint pt; + *m2 = *m; + m->next = m2; + m2->prev = m; + m2->next->prev = m2; + m->linked = m2; + m->tend = t; + m->end = il; + m2->start = il; + m2->tstart = t; + pt.x = ((m->s->splines[0].a*m->tstart+m->s->splines[0].b)*m->tstart+ + m->s->splines[0].c)*m->tstart+m->s->splines[0].d; + pt.y = ((m->s->splines[1].a*m->tstart+m->s->splines[1].b)*m->tstart+ + m->s->splines[1].c)*m->tstart+m->s->splines[1].d; + if ( pt.x>il->inter.x ) { + m->b.minx = il->inter.x; + m->b.maxx = pt.x; + } else { + m->b.minx = pt.x; + m->b.maxx = il->inter.x; + } + if ( pt.y>il->inter.y ) { + m->b.miny = il->inter.y; + m->b.maxy = pt.y; + } else { + m->b.miny = pt.y; + m->b.maxy = il->inter.y; + } + pt.x = ((m2->s->splines[0].a*m2->tend+m2->s->splines[0].b)*m2->tend+ + m2->s->splines[0].c)*m2->tend+m2->s->splines[0].d; + pt.y = ((m2->s->splines[1].a*m2->tend+m2->s->splines[1].b)*m2->tend+ + m2->s->splines[1].c)*m2->tend+m2->s->splines[1].d; + if ( pt.x>il->inter.x ) { + m2->b.minx = il->inter.x; + m2->b.maxx = pt.x; + } else { + m2->b.minx = pt.x; + m2->b.maxx = il->inter.x; + } + if ( pt.y>il->inter.y ) { + m2->b.miny = il->inter.y; + m2->b.maxy = pt.y; + } else { + m2->b.miny = pt.y; + m2->b.maxy = il->inter.y; + } + _AddSpline(il,m2,t,false); + } + } +} + +static void SetStartPoint(BasePoint *pt,Monotonic *m) { + if ( m->tstart==0 ) + *pt = m->s->from->me; + else if ( m->start!=NULL ) + *pt = m->start->inter; + else { + pt->x = ((m->s->splines[0].a*m->tstart+m->s->splines[0].b)*m->tstart + + m->s->splines[0].c)*m->tstart + m->s->splines[0].d; + pt->y = ((m->s->splines[1].a*m->tstart+m->s->splines[1].b)*m->tstart + + m->s->splines[1].c)*m->tstart + m->s->splines[1].d; + } +} + +static void SetEndPoint(BasePoint *pt,Monotonic *m) { + if ( m->tend==1.0 ) + *pt = m->s->to->me; + else if ( m->end!=NULL ) + *pt = m->end->inter; + else { + pt->x = ((m->s->splines[0].a*m->tend+m->s->splines[0].b)*m->tend + + m->s->splines[0].c)*m->tend + m->s->splines[0].d; + pt->y = ((m->s->splines[1].a*m->tend+m->s->splines[1].b)*m->tend + + m->s->splines[1].c)*m->tend + m->s->splines[1].d; + } +} + +static extended RoundToEndpoints(Monotonic *m,extended t,BasePoint *inter) { + BasePoint end; + extended bound; + + if ( t==0 || t==1 ) { + if ( t==0 ) + *inter = m->s->from->me; + else + *inter = m->s->to->me; +return( t ); + } + + if ( t-m->tstart < m->tend-t ) { + bound = m->tstart; + SetStartPoint(&end,m); + } else { + bound = m->tend; + SetEndPoint(&end,m); + } + if ( BpSame(&end,inter) || RealWithin(t,bound,.00001)) { + *inter = end; +return( bound ); + } + +return( t ); +} + +static extended Grad1(Spline1D *s1, Spline1D *s2, + extended t1,extended t2 ) { + /* d/dt[12] (m1(t1).x-m2(t2).x)^2 + (m1(t1).y-m2(t2).y)^2 */ + /* d/dt[12] (m1(t1).x^2 -2m1(t1).x*m2(t2).x + m2(t2).x^2) + (m1(t1).y^2 -2m1(t1).y*m2(t2).y + m2(t2).y^2) */ + extended val2 = ((s2->a*t2+s2->b)*t2+s2->c)*t2+s2->d; + +return( ((((6*(extended)s1->a*s1->a*t1 + + 5*2*(extended)s1->a*s1->b)*t1 + + 4*(s1->b*(extended)s1->b+2*s1->a*(extended)s1->c))*t1 + + 3*2*(s1->a*(extended)s1->d+s1->b*(extended)s1->c))*t1 + + 2*(s1->c*(extended)s1->c+2*s1->b*(extended)s1->d))*t1 + + 2*s1->c*(extended)s1->d - + 2*val2 * ((3*s1->a*t1 + 2*s1->b)*t1 + s1->c) ); +} + +static void GradImproveInter(Monotonic *m1, Monotonic *m2, + extended *_t1,extended *_t2,BasePoint *inter) { + Spline *s1 = m1->s, *s2 = m2->s; + extended x1, x2, y1, y2; + extended gt1=0, gt2=0, glen=1; + extended error, olderr=1e10; + extended factor = 4096; + extended t1=*_t1, t2=*_t2; + extended off, off2, yoff; + int cnt=0; + /* We want to find (t1,t2) so that (m1(t1)-m2(t2))^2==0 */ + /* Find the gradiant and move in the reverse direction */ + /* We know that the current values of (t1,t2) are close to an intersection*/ + /* so the grad should point correctly */ + /* d/dt[12] (m1(t1).x-m2(t2).x)^2 + (m1(t1).y-m2(t2).y)^2 */ + /* d/dt[12] (m1(t1).x^2 -2m1(t1).x*m2(t2).x + m2(t2).x^2) + (m1(t1).y^2 -2m1(t1).y*m2(t2).y + m2(t2).y^2) */ + + forever { + x1 = ((s1->splines[0].a*t1 + s1->splines[0].b)*t1 + s1->splines[0].c)*t1 + s1->splines[0].d; + x2 = ((s2->splines[0].a*t2 + s2->splines[0].b)*t2 + s2->splines[0].c)*t2 + s2->splines[0].d; + y1 = ((s1->splines[1].a*t1 + s1->splines[1].b)*t1 + s1->splines[1].c)*t1 + s1->splines[1].d; + y2 = ((s2->splines[1].a*t2 + s2->splines[1].b)*t2 + s2->splines[1].c)*t2 + s2->splines[1].d; + error = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2); + if ( error>olderr ) { + if ( olderr==1e10 ) + break; + factor *= 2; + if ( factor>4096*4096 ) + break; + glen *= 2; + t1 += gt1/glen; + t2 += gt2/glen; + continue; + } else + factor /= 1.4; + if ( error<1e-11 ) /* Error is actually the square of the error */ + break; /* So this isn't as constraining as it looks */ + + gt1 = Grad1(&s1->splines[0],&s2->splines[0],t1,t2) + Grad1(&s1->splines[1],&s2->splines[1],t1,t2); + gt2 = Grad1(&s2->splines[0],&s1->splines[0],t2,t1) + Grad1(&s2->splines[1],&s1->splines[1],t2,t1); + glen = esqrt(gt1*gt1 + gt2*gt2) * factor; + if ( glen==0 ) + break; + *_t1 = t1; *_t2 = t2; + t1 -= gt1/glen; + t2 -= gt2/glen; + if ( isnan(t1) || isnan(t2)) { + IError( "Nan in grad" ); + break; + } + olderr = error; + ++cnt; + if ( cnt>1000 ) + break; + } +#if 0 + if ( cnt<=1 && error>=1e-11 ) + fprintf(stderr,"No Improvement\n" ); + else if ( cnt>1 ) + fprintf(stderr,"Improvement\n" ); +#endif + t1 = *_t1; t2 = *_t2; + if ( t1<0 && t1>-.00001 ) *_t1 = t1 = 0; + else if ( t1>1 && t1<1.00001 ) *_t1 = t1 = 1.0; + if ( t2<0 && t2>-.00001 ) *_t2 = t2 = 0; + else if ( t2>1 && t2<1.00001 ) *_t2 = t2 = 1.0; + x1 = ((s1->splines[0].a*t1 + s1->splines[0].b)*t1 + s1->splines[0].c)*t1 + s1->splines[0].d; + x2 = ((s2->splines[0].a*t2 + s2->splines[0].b)*t2 + s2->splines[0].c)*t2 + s2->splines[0].d; + y1 = ((s1->splines[1].a*t1 + s1->splines[1].b)*t1 + s1->splines[1].c)*t1 + s1->splines[1].d; + y2 = ((s2->splines[1].a*t2 + s2->splines[1].b)*t2 + s2->splines[1].c)*t2 + s2->splines[1].d; + inter->x = (x1+x2)/2; inter->y = (y1+y2)/2; + + if ( (off=x1-x2)<0 ) off = -off; + if ( (yoff=y1-y2)<0 ) yoff = -yoff; + off += yoff; + + if ( t1<.0001 ) { + t1 = 0; + x1 = s1->splines[0].d; + y1 = s1->splines[1].d; + } else if ( t1>.9999 ) { + t1 = 1.0; + x1 = s1->splines[0].a+s1->splines[0].b+s1->splines[0].c+s1->splines[0].d; + y1 = s1->splines[1].a+s1->splines[1].b+s1->splines[1].c+s1->splines[1].d; + } + if ( t2<.0001 ) { + t2=0; + x2 = s2->splines[0].d; + y2 = s2->splines[1].d; + } else if ( t2>.9999 ) { + t2=1.0; + x2 = s2->splines[0].a+s2->splines[0].b+s2->splines[0].c+s2->splines[0].d; + y2 = s2->splines[1].a+s2->splines[1].b+s2->splines[1].c+s2->splines[1].d; + } + if ( (off2=x1-x2)<0 ) off2 = -off2; + if ( (yoff=y1-y2)<0 ) yoff = -yoff; + off2 += yoff; + if ( off2<=off ) { + *_t1 = t1; *_t2 = t2; + inter->x = (x1+x2)/2; inter->y = (y1+y2)/2; + } +} + +static Intersection *AddIntersection(Intersection *ilist,Monotonic *m1, + Monotonic *m2,extended t1,extended t2,BasePoint *inter) { + Intersection *il; + extended ot1 = t1, ot2 = t2; + + /* Fixup some rounding errors */ + GradImproveInter(m1,m2,&t1,&t2,inter); + if ( t1<m1->tstart || t1>m1->tend || t2<m2->tstart || t2>m2->tend ) +return( ilist ); + + t1 = RoundToEndpoints(m1,t1,inter); + t2 = RoundToEndpoints(m2,t2,inter); + t1 = RoundToEndpoints(m1,t1,inter); /* Do it twice. rounding t2 can mean we now need to round t1 */ + + if (( m1->s->to == m2->s->from && RealWithin(t1,1.0,.01) && RealWithin(t2,0,.01)) || + ( m1->s->from == m2->s->to && RealWithin(t1,0,.01) && RealWithin(t2,1.0,.01))) +return( ilist ); + + if (( t1==m1->tstart && m1->start!=NULL && + (inter->x!=m1->start->inter.x || inter->y!=m1->start->inter.y)) || + ( t1==m1->tend && m1->end!=NULL && + (inter->x!=m1->end->inter.x || inter->y!=m1->end->inter.y))) + t1 = ot1; + if (( t2==m2->tstart && m2->start!=NULL && + (inter->x!=m2->start->inter.x || inter->y!=m2->start->inter.y)) || + ( t2==m2->tend && m2->end!=NULL && + (inter->x!=m2->end->inter.x || inter->y!=m2->end->inter.y))) + t2 = ot2; + + /* The ordinary join of one spline to the next doesn't really count */ + /* Or one monotonic sub-spline to the next either */ + if (( m1->next==m2 && RealNear(t1,m1->tend) && RealNear(t2,m2->tstart)) || + (m2->next==m1 && RealNear(t1,m1->tstart) && RealNear(t2,m2->tend)) ) +return( ilist ); + + if ( RealWithin(m1->tstart,t1,.01) ) + il = m1->start; + else if ( RealWithin(m1->tend,t1,.01) ) + il = m1->end; + else + il = NULL; + if ( il!=NULL && + ((RealWithin(m2->tstart,t2,.01) && m2->start==il) || + (RealWithin(m2->tend,t2,.01) && m2->end==il)) ) +return( ilist ); + + for ( il = ilist; il!=NULL; il=il->next ) { + if ( RealWithin(il->inter.x,inter->x,.01) && RealWithin(il->inter.y,inter->y,.01)) { + AddSpline(il,m1,t1); + AddSpline(il,m2,t2); +return( ilist ); + } + } + + il = chunkalloc(sizeof(Intersection)); + il->inter = *inter; + il->next = ilist; + AddSpline(il,m1,t1); + AddSpline(il,m2,t2); +return( il ); +} + +static extended BoundIterateSplineSolve(Spline1D *sp, extended tmin, extended tmax, + extended sought,double err) { + extended t = IterateSplineSolve(sp,tmin,tmax,sought,err); + if ( t<tmin || t>tmax ) +return( -1 ); + +return( t ); +} + +static Intersection *FindMonotonicIntersection(Intersection *ilist,Monotonic *m1,Monotonic *m2) { + /* I believe that two monotonic cubics can still intersect in two points */ + /* so we can't just check if the splines are on oposite sides of each */ + /* other at top and bottom */ + DBounds b; + const double error = .0001; + BasePoint pt; + extended t1,t2; + + b.minx = m1->b.minx>m2->b.minx ? m1->b.minx : m2->b.minx; + b.maxx = m1->b.maxx<m2->b.maxx ? m1->b.maxx : m2->b.maxx; + b.miny = m1->b.miny>m2->b.miny ? m1->b.miny : m2->b.miny; + b.maxy = m1->b.maxy<m2->b.maxy ? m1->b.maxy : m2->b.maxy; + + if ( b.maxy==b.miny && b.minx==b.maxx ) { + extended x1,y1, x2,y2; + if ( m1->next==m2 || m2->next==m1 ) +return( ilist ); /* Not interesting. Only intersection is at an endpoint */ + if ( ((m1->start==m2->start || m1->end==m2->start) && m2->start!=NULL) || + ((m1->start==m2->end || m1->end==m2->end ) && m2->end!=NULL )) +return( ilist ); + pt.x = b.minx; pt.y = b.miny; + if ( m1->b.maxx-m1->b.minx > m1->b.maxy-m1->b.miny ) + t1 = BoundIterateSplineSolve(&m1->s->splines[0],m1->tstart,m1->tend,b.minx,error); + else + t1 = BoundIterateSplineSolve(&m1->s->splines[1],m1->tstart,m1->tend,b.miny,error); + if ( m2->b.maxx-m2->b.minx > m2->b.maxy-m2->b.miny ) + t2 = BoundIterateSplineSolve(&m2->s->splines[0],m2->tstart,m2->tend,b.minx,error); + else + t2 = BoundIterateSplineSolve(&m2->s->splines[1],m2->tstart,m2->tend,b.miny,error); + if ( t1!=-1 && t2!=-1 ) { + x1 = ((m1->s->splines[0].a*t1+m1->s->splines[0].b)*t1+m1->s->splines[0].c)*t1+m1->s->splines[0].d; + y1 = ((m1->s->splines[1].a*t1+m1->s->splines[1].b)*t1+m1->s->splines[1].c)*t1+m1->s->splines[1].d; + x2 = ((m2->s->splines[0].a*t2+m2->s->splines[0].b)*t2+m2->s->splines[0].c)*t2+m2->s->splines[0].d; + y2 = ((m2->s->splines[1].a*t2+m2->s->splines[1].b)*t2+m2->s->splines[1].c)*t2+m2->s->splines[1].d; + if ( x1-x2>-.01 && x1-x2<.01 && y1-y2>-.01 && y1-y2<.01 ) + ilist = AddIntersection(ilist,m1,m2,t1,t2,&pt); + } + } else if ( b.maxy==b.miny ) { + extended x1,x2; + if ( m1->next==m2 || m2->next==m1 ) +return( ilist ); /* Not interesting. Only intersection is at an endpoint */ + t1 = BoundIterateSplineSolve(&m1->s->splines[1],m1->tstart,m1->tend,b.miny,error); + t2 = BoundIterateSplineSolve(&m2->s->splines[1],m2->tstart,m2->tend,b.miny,error); + if ( t1!=-1 && t2!=-1 ) { + x1 = ((m1->s->splines[0].a*t1+m1->s->splines[0].b)*t1+m1->s->splines[0].c)*t1+m1->s->splines[0].d; + x2 = ((m2->s->splines[0].a*t2+m2->s->splines[0].b)*t2+m2->s->splines[0].c)*t2+m2->s->splines[0].d; + if ( x1-x2>-.01 && x1-x2<.01 ) { + pt.x = (x1+x2)/2; pt.y = b.miny; + ilist = AddIntersection(ilist,m1,m2,t1,t2,&pt); + } + } + } else if ( b.maxx==b.minx ) { + extended y1,y2; + if ( m1->next==m2 || m2->next==m1 ) +return( ilist ); /* Not interesting. Only intersection is at an endpoint */ + t1 = BoundIterateSplineSolve(&m1->s->splines[0],m1->tstart,m1->tend,b.minx,error); + t2 = BoundIterateSplineSolve(&m2->s->splines[0],m2->tstart,m2->tend,b.minx,error); + if ( t1!=-1 && t2!=-1 ) { + y1 = ((m1->s->splines[1].a*t1+m1->s->splines[1].b)*t1+m1->s->splines[1].c)*t1+m1->s->splines[1].d; + y2 = ((m2->s->splines[1].a*t2+m2->s->splines[1].b)*t2+m2->s->splines[1].c)*t2+m2->s->splines[1].d; + if ( y1-y2>-.01 && y1-y2<.01 ) { + pt.x = b.minx; pt.y = (y1+y2)/2; + ilist = AddIntersection(ilist,m1,m2,t1,t2,&pt); + } + } + } else if ( b.maxy-b.miny > b.maxx-b.minx ) { + extended diff, y, x1,x2, x1o,x2o; + extended t1,t2, t1o,t2o ; + + diff = (b.maxy-b.miny)/32; + y = b.miny; + x1o = x2o = 0; + while ( y<b.maxy ) { + while ( y<b.maxy ) { + t1o = BoundIterateSplineSolve(&m1->s->splines[1],m1->tstart,m1->tend,b.miny,error); + t2o = BoundIterateSplineSolve(&m2->s->splines[1],m2->tstart,m2->tend,b.miny,error); + if ( t1o!=-1 && t2o!=-1 ) + break; + y += diff; + } + x1o = ((m1->s->splines[0].a*t1o+m1->s->splines[0].b)*t1o+m1->s->splines[0].c)*t1o+m1->s->splines[0].d; + x2o = ((m2->s->splines[0].a*t2o+m2->s->splines[0].b)*t2o+m2->s->splines[0].c)*t2o+m2->s->splines[0].d; + if ( x1o!=x2o ) + break; + y += diff; + } + for ( y+=diff; ; y += diff ) { + /* I used to say y<=b.maxy in the above for statement. */ + /* that seemed to get rounding errors on the mac, so we do it */ + /* like this now: */ + if ( y>b.maxy ) { + if ( y<b.maxy+diff/4 ) y = b.maxy; + else + break; + } + t1 = BoundIterateSplineSolve(&m1->s->splines[1],m1->tstart,m1->tend,y,error); + t2 = BoundIterateSplineSolve(&m2->s->splines[1],m2->tstart,m2->tend,y,error); + if ( t1==-1 || t2==-1 ) + continue; + x1 = ((m1->s->splines[0].a*t1+m1->s->splines[0].b)*t1+m1->s->splines[0].c)*t1+m1->s->splines[0].d; + x2 = ((m2->s->splines[0].a*t2+m2->s->splines[0].b)*t2+m2->s->splines[0].c)*t2+m2->s->splines[0].d; + if ( x1o!=x2o && (x1o>x2o) != ( x1>x2 ) ) { + /* A cross over has occured. (assume we have a small enough */ + /* region that three cross-overs can't have occurred) */ + /* Use a binary search to track it down */ + extended ytop, ybot; + ytop = y; + ybot = y-diff; + while ( ytop!=ybot ) { + extended ytest = (ytop+ybot)/2; + extended t1t, t2t; + t1t = BoundIterateSplineSolve(&m1->s->splines[1],m1->tstart,m1->tend,ytest,error); + t2t = BoundIterateSplineSolve(&m2->s->splines[1],m2->tstart,m2->tend,ytest,error); + x1 = ((m1->s->splines[0].a*t1t+m1->s->splines[0].b)*t1t+m1->s->splines[0].c)*t1t+m1->s->splines[0].d; + x2 = ((m2->s->splines[0].a*t2t+m2->s->splines[0].b)*t2t+m2->s->splines[0].c)*t2t+m2->s->splines[0].d; + if ( t1t==-1 || t2t==-1 ) { + SOError( "Can't find something in range.\n" ); + break; + } else if (( x1-x2<error && x1-x2>-error ) || ytop==ytest || ybot==ytest ) { + pt.y = ytest; pt.x = (x1+x2)/2; + ilist = AddIntersection(ilist,m1,m2,t1t,t2t,&pt); + b.maxy = m1->b.maxy<m2->b.maxy ? m1->b.maxy : m2->b.maxy; + break; + } else if ( (x1o>x2o) != ( x1>x2 ) ) { + ytop = ytest; + } else { + ybot = ytest; + } + } + x1 = x1o; x1o = x2o; x2o = x1; + } else { + x1o = x1; x2o = x2; + } + } + } else { + extended diff, x, y1,y2, y1o,y2o; + extended t1,t2, t1o,t2o ; + + diff = (b.maxx-b.minx)/32; + x = b.minx; + y1o = y2o = 0; + while ( x<b.maxx ) { + while ( x<b.maxx ) { + t1o = BoundIterateSplineSolve(&m1->s->splines[0],m1->tstart,m1->tend,b.minx,error); + t2o = BoundIterateSplineSolve(&m2->s->splines[0],m2->tstart,m2->tend,b.minx,error); + if ( t1o!=-1 && t2o!=-1 ) + break; + x += diff; + } + y1o = ((m1->s->splines[1].a*t1o+m1->s->splines[1].b)*t1o+m1->s->splines[1].c)*t1o+m1->s->splines[1].d; + y2o = ((m2->s->splines[1].a*t2o+m2->s->splines[1].b)*t2o+m2->s->splines[1].c)*t2o+m2->s->splines[1].d; + if ( y1o!=y2o ) + break; + x += diff; + } + y1 = y2 = 0; + for ( x+=diff; ; x += diff ) { + if ( x>b.maxx ) { + if ( x<b.maxx+diff/4 ) x = b.maxx; + else + break; + } + t1 = BoundIterateSplineSolve(&m1->s->splines[0],m1->tstart,m1->tend,x,error); + t2 = BoundIterateSplineSolve(&m2->s->splines[0],m2->tstart,m2->tend,x,error); + if ( t1==-1 || t2==-1 ) + continue; + y1 = ((m1->s->splines[1].a*t1+m1->s->splines[1].b)*t1+m1->s->splines[1].c)*t1+m1->s->splines[1].d; + y2 = ((m2->s->splines[1].a*t2+m2->s->splines[1].b)*t2+m2->s->splines[1].c)*t2+m2->s->splines[1].d; + if ( (y1o>y2o) != ( y1>y2 ) ) { + /* A cross over has occured. (assume we have a small enough */ + /* region that three cross-overs can't have occurred) */ + /* Use a binary search to track it down */ + extended xtop, xbot; + xtop = x; + xbot = x-diff; + while ( xtop!=xbot ) { + extended xtest = (xtop+xbot)/2; + extended t1t, t2t; + t1t = BoundIterateSplineSolve(&m1->s->splines[0],m1->tstart,m1->tend,xtest,error); + t2t = BoundIterateSplineSolve(&m2->s->splines[0],m2->tstart,m2->tend,xtest,error); + y1 = ((m1->s->splines[1].a*t1t+m1->s->splines[1].b)*t1t+m1->s->splines[1].c)*t1t+m1->s->splines[1].d; + y2 = ((m2->s->splines[1].a*t2t+m2->s->splines[1].b)*t2t+m2->s->splines[1].c)*t2t+m2->s->splines[1].d; + if ( t1t==-1 || t2t==-1 ) { + SOError( "Can't find something in range.\n" ); + break; + } else if (( y1-y2<error && y1-y2>-error ) || xtop==xtest || xbot==xtest ) { + pt.x = xtest; pt.y = (y1+y2)/2; + ilist = AddIntersection(ilist,m1,m2,t1t,t2t,&pt); + b.maxx = m1->b.maxx<m2->b.maxx ? m1->b.maxx : m2->b.maxx; + break; + } else if ( (y1o>y2o) != ( y1>y2 ) ) { + xtop = xtest; + } else { + xbot = xtest; + } + } + y1 = y1o; y1o = y2o; y2o = y1; + } else { + y1o = y1; y2o = y2; + } + } + } +return( ilist ); +} + + +static extended SplineContainsPoint(Monotonic *m,BasePoint *pt) { + int which, nw; + extended t; + BasePoint slope; + const double error = .0001; + + which = ( m->b.maxx-m->b.minx > m->b.maxy-m->b.miny )? 0 : 1; + nw = !which; + t = BoundIterateSplineSolve(&m->s->splines[which],m->tstart,m->tend,(&pt->x)[which],error); + if ( (slope.x = (3*m->s->splines[0].a*t+2*m->s->splines[0].b)*t+m->s->splines[0].c)<0 ) + slope.x = -slope.x; + if ( (slope.y = (3*m->s->splines[1].a*t+2*m->s->splines[1].b)*t+m->s->splines[1].c)<0 ) + slope.y = -slope.y; + if ( t==-1 || (slope.y>slope.x)!=which ) { + nw = which; + which = 1-which; + t = BoundIterateSplineSolve(&m->s->splines[which],m->tstart,m->tend,(&pt->x)[which],error); + } + if ( t!=-1 && RealWithin((&pt->x)[nw], + ((m->s->splines[nw].a*t+m->s->splines[nw].b)*t + + m->s->splines[nw].c)*t + m->s->splines[nw].d,.1 )) +return( t ); + +return( -1 ); +} + +/* If two splines are coincident, then pretend they intersect at both */ +/* end-points and nowhere else */ +static int CoincidentIntersect(Monotonic *m1,Monotonic *m2,BasePoint *pts, + extended *t1s,extended *t2s) { + const double error = .0001; + int cnt=0; + extended t, t2, diff; + + if ( m1==m2 || m1->next==m2 || m1->prev==m2 ) +return( false ); /* Can't be coincident. Adjacent */ + /* Actually adjacent splines can double back on themselves */ + + if ( (m1->xup==m2->xup && m1->yup==m2->yup) || + ((m1->xup!=m2->xup || (m1->b.minx==m1->b.maxx && m2->b.minx==m2->b.maxx)) || + (m1->yup!=m2->yup || (m1->b.miny==m1->b.maxy && m2->b.miny==m2->b.maxy)))) + /* A match is possible */; + else +return( false ); + + SetStartPoint(&pts[cnt],m1); + t1s[cnt] = m1->tstart; + if ( (t2s[cnt] = SplineContainsPoint(m2,&pts[cnt]))!=-1 ) + ++cnt; + + SetEndPoint(&pts[cnt],m1); + t1s[cnt] = m1->tend; + if ( (t2s[cnt] = SplineContainsPoint(m2,&pts[cnt]))!=-1 ) + ++cnt; + + if ( cnt!=2 ) { + SetStartPoint(&pts[cnt],m2); + t2s[cnt] = m2->tstart; + if ( (t1s[cnt] = SplineContainsPoint(m1,&pts[cnt]))!=-1 ) + ++cnt; + } + + if ( cnt!=2 ) { + SetEndPoint(&pts[cnt],m2); + t2s[cnt] = m2->tend; + if ( (t1s[cnt] = SplineContainsPoint(m1,&pts[cnt]))!=-1 ) + ++cnt; + } + + if ( cnt!=2 ) +return( false ); + + if ( RealWithin(t1s[0],t1s[1],.01) ) +return( false ); + + /* Ok, if we've gotten this far we know that two of the end points are */ + /* on both splines. */ + t1s[2] = t2s[2] = -1; + if ( !m1->s->knownlinear || !m1->s->knownlinear ) { + if ( t1s[1]<t1s[0] ) { + extended temp = t1s[1]; t1s[1] = t1s[0]; t1s[0] = temp; + temp = t2s[1]; t2s[1] = t2s[0]; t2s[0] = temp; + } + diff = (t1s[1]-t1s[0])/16; + for ( t=t1s[0]+diff; t<t1s[1]-diff/4; t += diff ) { + BasePoint here, slope; + here.x = ((m1->s->splines[0].a*t+m1->s->splines[0].b)*t+m1->s->splines[0].c)*t+m1->s->splines[0].d; + here.y = ((m1->s->splines[1].a*t+m1->s->splines[1].b)*t+m1->s->splines[1].c)*t+m1->s->splines[1].d; + if ( (slope.x = (3*m1->s->splines[0].a*t+2*m1->s->splines[0].b)*t+m1->s->splines[0].c)<0 ) + slope.x = -slope.x; + if ( (slope.y = (3*m1->s->splines[1].a*t+2*m1->s->splines[1].b)*t+m1->s->splines[1].c)<0 ) + slope.y = -slope.y; + if ( slope.y>slope.x ) { + t2 = BoundIterateSplineSolve(&m2->s->splines[1],t2s[0],t2s[1],here.y,error); + if ( t2==-1 || !RealWithin(here.x,((m2->s->splines[0].a*t2+m2->s->splines[0].b)*t2+m2->s->splines[0].c)*t2+m2->s->splines[0].d,.1)) +return( false ); + } else { + t2 = BoundIterateSplineSolve(&m2->s->splines[0],t2s[0],t2s[1],here.x,error); + if ( t2==-1 || !RealWithin(here.y,((m2->s->splines[1].a*t2+m2->s->splines[1].b)*t2+m2->s->splines[1].c)*t2+m2->s->splines[1].d,.1)) +return( false ); + } + } + } + +return( true ); +} + +static void FigureProperMonotonicsAtIntersections(Intersection *ilist) { + MList *ml, *ml2, *mlnext, *prev, *p2; + + while ( ilist!=NULL ) { + for ( ml=ilist->monos; ml!=NULL; ml=ml->next ) { + if ( (ml->t==ml->m->tstart && !ml->isend) || + (ml->t==ml->m->tend && ml->isend)) + /* It's right */; + else if ( ml->t>ml->m->tstart ) { + while ( ml->t>ml->m->tend ) { + ml->m = ml->m->next; + if ( ml->m->s!=ml->s ) { + SOError("we could not find a matching monotonic\n" ); + break; + } + } + } else { + while ( ml->t<ml->m->tstart ) { + ml->m = ml->m->prev; + if ( ml->m->s!=ml->s ) { + SOError( "we could not find a matching monotonic\n" ); + break; + } + } + } + if ( ml->t==ml->m->tstart && ml->isend ) + ml->m = ml->m->prev; + else if ( ml->t==ml->m->tend && !ml->isend ) + ml->m = ml->m->next; + if ( ml->t!=ml->m->tstart && ml->t!=ml->m->tend ) + SOError( "we could not find a matching monotonic time\n" ); + } + for ( prev=NULL, ml=ilist->monos; ml!=NULL; ml = mlnext ) { + mlnext = ml->next; + if ( ml->m->start==ml->m->end ) { + for ( p2 = ml, ml2=ml->next; ml2!=NULL; p2=ml2, ml2 = ml2->next ) { + if ( ml2->m==ml->m ) + break; + } + if ( ml2!=NULL ) { + if ( ml2==mlnext ) mlnext = ml2->next; + p2->next = ml2->next; + chunkfree(ml2,sizeof(*ml2)); + } + if ( prev==NULL ) + ilist->monos = mlnext; + else + prev->next = mlnext; + chunkfree(ml,sizeof(*ml)); + } + } +#if 0 + for ( ml=ilist->monos; ml!=NULL; ml=ml->next ) { + Monotonic *search; + MList *ml2; + extended t; + if ( ml->m->start == ilist ) { + search = ml->m->prev; + t = ( ml->m->tstart==0 ) ? 1.0 : ml->m->tstart; + } else { + search = ml->m->next; + t = ( ml->m->tend==1.0 ) ? 0.0 : ml->m->tend; + } + for ( ml2=ilist->monos; ml2!=NULL && ml2->m!=search; ml2=ml2->next ); + if ( ml2==NULL ) { + ml2 = chunkalloc(sizeof(MList)); + ml2->m = search; + ml2->s = search->s; + ml2->t = t; + ml2->next = ml->next; + ml->next = ml2; + ml = ml2; + } + } +#endif + ilist = ilist->next; + } +} + +static void Validate(Monotonic *ms, Intersection *ilist) { + MList *ml; + int mcnt; + + while ( ilist!=NULL ) { + for ( mcnt=0, ml=ilist->monos; ml!=NULL; ml=ml->next ) { + if ( ml->m->isneeded ) ++mcnt; + if ( ml->m->start!=ilist && ml->m->end!=ilist ) + SOError( "Intersection (%g,%g) not on a monotonic which should contain it.\n", + ilist->inter.x, ilist->inter.y ); + } + if ( mcnt&1 ) + SOError( "Odd number of needed monotonic sections at intersection. (%g,%g)\n", + ilist->inter.x,ilist->inter.y ); + ilist = ilist->next; + } + + while ( ms!=NULL ) { + if ( ms->prev->end!=ms->start ) + SOError( "Mismatched intersection.\n"); + ms = ms->linked; + } +} + +static Intersection *FindIntersections(Monotonic *ms, enum overlap_type ot) { + Monotonic *m1, *m2; + BasePoint pts[9]; + extended t1s[10], t2s[10]; + Intersection *ilist=NULL; + int i; + int wasc; + + for ( m1=ms; m1!=NULL; m1=m1->linked ) { + for ( m2=m1->linked; m2!=NULL; m2=m2->linked ) { + if ( m2->b.minx > m1->b.maxx || + m2->b.maxx < m1->b.minx || + m2->b.miny > m1->b.maxy || + m2->b.maxy < m1->b.miny ) + continue; /* Can't intersect */; + wasc = CoincidentIntersect(m1,m2,pts,t1s,t2s); + if ( wasc || m1->s->knownlinear || m2->s->knownlinear || + (m1->s->splines[0].a==0 && m1->s->splines[1].a==0 && + m2->s->splines[0].a==0 && m2->s->splines[1].a==0 )) { + if ( !wasc && SplinesIntersect(m1->s,m2->s,pts,t1s,t2s)<=0 ) + continue; + for ( i=0; i<4 && t1s[i]!=-1; ++i ) { + if ( t1s[i]>=m1->tstart && t1s[i]<=m1->tend && + t2s[i]>=m2->tstart && t2s[i]<=m2->tend ) { + ilist = AddIntersection(ilist,m1,m2,t1s[i],t2s[i],&pts[i]); + } + } + continue; + } + ilist = FindMonotonicIntersection(ilist,m1,m2); + } + } + + FigureProperMonotonicsAtIntersections(ilist); + + /* Now suppose we have a contour which intersects nothing? */ + /* with no intersections we lose track of it and it will vanish */ + /* That's not a good idea. Make sure each contour has at least one inter */ + if ( ot!=over_findinter && ot!=over_fisel ) { + for ( m1=ms; m1!=NULL; m1=m2->linked ) { + if ( m1->start==NULL && m1->end==NULL ) { + Intersection *il; + il = chunkalloc(sizeof(Intersection)); + il->inter = m1->s->from->me; + il->next = ilist; + AddSpline(il,m1,0); + AddSpline(il,m1->prev,1.0); + ilist = il; + } + for ( m2=m1; m2->linked==m2->next; m2=m2->linked ); + } + } + +return( ilist ); +} + +static int dcmp(const void *_p1, const void *_p2) { + const extended *dpt1 = _p1, *dpt2 = _p2; + if ( *dpt1>*dpt2 ) +return( 1 ); + else if ( *dpt1<*dpt2 ) +return( -1 ); + +return( 0 ); +} + +static extended *FindOrderedEndpoints(Monotonic *ms,int which) { + int cnt; + Monotonic *m; + extended *ends; + int i,j,k; + + for ( m=ms, cnt=0; m!=NULL; m=m->linked, ++cnt ); + ends = galloc((2*cnt+1)*sizeof(extended)); + for ( m=ms, cnt=0; m!=NULL; m=m->linked, cnt+=2 ) { + if ( m->start!=NULL ) + ends[cnt] = (&m->start->inter.x)[which]; + else if ( m->tstart==0 ) + ends[cnt] = (&m->s->from->me.x)[which]; + else + ends[cnt] = ((m->s->splines[which].a*m->tstart+m->s->splines[which].b)*m->tstart+ + m->s->splines[which].c)*m->tstart+m->s->splines[which].d; + if ( m->end!=NULL ) + ends[cnt+1] = (&m->end->inter.x)[which]; + else if ( m->tend==1.0 ) + ends[cnt+1] = (&m->s->to->me.x)[which]; + else + ends[cnt+1] = ((m->s->splines[which].a*m->tend+m->s->splines[which].b)*m->tend+ + m->s->splines[which].c)*m->tend+m->s->splines[which].d; + } + + qsort(ends,cnt,sizeof(extended),dcmp); + for ( i=0; i<cnt; ++i ) { + for ( j=i; j<cnt && ends[i]==ends[j]; ++j ); + if ( j>i+1 ) { + for ( k=i+1; j<cnt; ends[k++] = ends[j++]); + cnt-= j-k; + } + } + ends[cnt] = 1e10; +return( ends ); +} + +static int mcmp(const void *_p1, const void *_p2) { + const Monotonic * const *mpt1 = _p1, * const *mpt2 = _p2; + if ( (*mpt1)->other>(*mpt2)->other ) +return( 1 ); + else if ( (*mpt1)->other<(*mpt2)->other ) +return( -1 ); + +return( 0 ); +} + +static int MonotonicFindAt(Monotonic *ms,int which, extended test, Monotonic **space ) { + /* Find all monotonic sections which intersect the line (x,y)[which] == test */ + /* find the value of the other coord on that line */ + /* Order them (by the other coord) */ + /* then run along that line figuring out which monotonics are needed */ + extended t; + Monotonic *m, *mm; + int i, j, k, cnt; + const double error = .0001; + int nw = !which; + + for ( m=ms, i=0; m!=NULL; m=m->linked ) { + if (( which==0 && test >= m->b.minx && test <= m->b.maxx ) || + ( which==1 && test >= m->b.miny && test <= m->b.maxy )) { + /* Lines parallel to the direction we are testing just get in the */ + /* way and don't add any useful info */ + if ( m->s->knownlinear && + (( which==1 && m->s->from->me.y==m->s->to->me.y ) || + (which==0 && m->s->from->me.x==m->s->to->me.x))) + continue; + t = BoundIterateSplineSolve(&m->s->splines[which],m->tstart,m->tend,test,error); + if ( t==-1 ) + continue; + m->t = t; + if ( t==m->tend ) t -= (m->tend-m->tstart)/100; + else if ( t==m->tstart ) t += (m->tend-m->tstart)/100; + m->other = ((m->s->splines[nw].a*t+m->s->splines[nw].b)*t+ + m->s->splines[nw].c)*t+m->s->splines[nw].d; + space[i++] = m; + } + } + cnt = i; + + /* Things get a little tricky at end-points */ + for ( i=0; i<cnt; ++i ) { + m = space[i]; + if ( m->t==m->tend ) { + /* Ignore horizontal/vertical lines (as appropriate) */ + for ( mm=m->next; mm!=m; mm=mm->next ) { + if ( !mm->s->knownlinear ) + break; + if (( which==1 && mm->s->from->me.y!=m->s->to->me.y ) || + (which==0 && mm->s->from->me.x!=m->s->to->me.x)) + break; + } + } else if ( m->t==m->tstart ) { + for ( mm=m->prev; mm!=m; mm=mm->prev ) { + if ( !mm->s->knownlinear ) + break; + if (( which==1 && mm->s->from->me.y!=m->s->to->me.y ) || + (which==0 && mm->s->from->me.x!=m->s->to->me.x)) + break; + } + } else + break; + /* If the next monotonic continues in the same direction, and we found*/ + /* it too, then don't count both. They represent the same intersect */ + /* If they are in oposite directions then they cancel each other out */ + /* and that is correct */ + if ( mm!=m && /* Should always be true */ + (&mm->xup)[which]==(&m->xup)[which] ) { + for ( j=cnt-1; j>=0; --j ) + if ( space[j]==mm ) + break; + if ( j!=-1 ) { + /* remove mm */ + for ( k=j+1; k<cnt; ++k ) + space[k-1] = space[k]; + --cnt; + if ( i>j ) --i; + } + } + } + + space[cnt] = NULL; space[cnt+1] = NULL; + qsort(space,cnt,sizeof(Monotonic *),mcmp); +return(cnt); +} + +static void FigureNeeds(Monotonic *ms,int which, extended test, Monotonic **space, + enum overlap_type ot, int ignore_close) { + /* Find all monotonic sections which intersect the line (x,y)[which] == test */ + /* find the value of the other coord on that line */ + /* Order them (by the other coord) */ + /* then run along that line figuring out which monotonics are needed */ + int i, j, winding, ew, was_close, close; + + MonotonicFindAt(ms,which,test,space); + + winding = 0; ew = 0; was_close = false; + for ( i=0; space[i]!=NULL; ++i ) { + int needed, unneeded, inverted=false; + Monotonic *m; + int new; + int nwinding; + retry: + needed = false, unneeded = false; + nwinding=winding; + new=ew; + m = space[i]; + if ( m->exclude ) + new += ( (&m->xup)[which] ? 1 : -1 ); + else + nwinding += ( (&m->xup)[which] ? 1 : -1 ); + if ( ot==over_remove || ot==over_rmselected ) { + if ( winding==0 || nwinding==0 ) + needed = true; + else + unneeded = true; + } else if ( ot==over_intersect || ot==over_intersel ) { + if ( (winding>-2 && winding<2 && nwinding>-2 && nwinding<2) || + ((winding<=-2 || winding>=2) && (nwinding<=-2 && nwinding>=2))) + unneeded = true; + else + needed = true; + } else if ( ot == over_exclude ) { + if ( (( winding==0 || nwinding==0 ) && ew==0 && new==0 ) || + (winding!=0 && (( ew!=0 && new==0 ) || ( ew==0 && new!=0))) ) + needed = true; + else + unneeded = true; + } + if ( space[i+1]!=NULL ) + close = space[i+1]->other-space[i]->other < 1; + else + close = false; + if (( !close && !was_close ) || ignore_close ) { + if (( m->isneeded || m->isunneeded ) && m->isneeded!=needed ) { + for ( j=i+1; space[j]!=NULL && space[j]->other-m->other<.5; ++j ) { + if ( space[j]->start==m->start && space[j]->end==m->end && + (space[j]->isneeded == needed || + (!space[j]->isneeded && !space[j]->isunneeded))) { + space[i] = space[j]; + space[j] = m; + m = space[i]; + break; + } else if ( !inverted && space[j]->other-m->other<.001 && + (((&space[j]->xup)[which] == (&m->xup)[which] && + (space[j]->isneeded == needed || + (!space[j]->isneeded && !space[j]->isunneeded))) || + ((&space[j]->xup)[which] != (&m->xup)[which] && + (space[j]->isneeded != needed || + (!space[j]->isneeded && !space[j]->isunneeded)))) ) { + space[i] = space[j]; + space[j] = m; + inverted = true; + goto retry; + } + } + } + if ( !m->isneeded && !m->isunneeded ) { + m->isneeded = needed; m->isunneeded = unneeded; + m->when_set = test; /* Debugging */ + } else if ( m->isneeded!=needed || m->isunneeded!=unneeded ) + SOError( "monotonic is both needed and unneeded.\n" ); + } + winding = nwinding; + ew = new; + was_close = close; + } + if ( winding!=0 ) + SOError( "Winding number did not return to 0 when %s=%g\n", + which ? "y" : "x", test ); +} + +struct gaps { extended test, len; int which; }; + +static int gcmp(const void *_p1, const void *_p2) { + const struct gaps *gpt1 = _p1, *gpt2 = _p2; + if ( gpt1->len > gpt2->len ) +return( 1 ); + else if ( gpt1->len < gpt2->len ) +return( -1 ); + +return( 0 ); +} + +static void FindNeeded(Monotonic *ms,enum overlap_type ot) { + extended *ends[2]; + Monotonic *m, **space; + extended top, bottom, test; + int t,b,i,j,k,cnt,which; + struct gaps *gaps; + extended min_gap; + + if ( ms==NULL ) +return; + + ends[0] = FindOrderedEndpoints(ms,0); + ends[1] = FindOrderedEndpoints(ms,1); + + for ( m=ms, cnt=0; m!=NULL; m=m->linked, ++cnt ); + space = galloc((cnt+2)*sizeof(Monotonic*)); + gaps = galloc(2*cnt*sizeof(struct gaps)); + + /* Look for the longest splines without interruptions first. These are */ + /* least likely to cause problems and will give us a good basis from which*/ + /* to make guesses should rounding errors occur later */ + for ( j=k=0; j<2; ++j ) + for ( i=0; ends[j][i+1]!=1e10; ++i ) { + gaps[k].which = j; + gaps[k].len = (ends[j][i+1]-ends[j][i]); + gaps[k++].test = (ends[j][i+1]+ends[j][i])/2; + } + qsort(gaps,k,sizeof(struct gaps),gcmp); + min_gap = 1e10; + for ( m=ms; m!=NULL; m=m->linked ) { + if ( m->b.maxx-m->b.minx > m->b.maxy-m->b.miny ) { + if ( min_gap > m->b.maxx-m->b.minx ) min_gap = m->b.maxx-m->b.minx; + } else { + if ( m->b.maxy-m->b.miny==0 ) + fprintf( stderr, "Foo\n"); + if ( min_gap > m->b.maxy-m->b.miny ) min_gap = m->b.maxy-m->b.miny; + } + } + if ( min_gap<.5 ) min_gap = .5; + for ( i=0; i<k && gaps[i].len>=min_gap; ++i ) + FigureNeeds(ms,gaps[i].which,gaps[i].test,space,ot,0); + + for ( m=ms; m!=NULL; m=m->linked ) if ( !m->isneeded && !m->isunneeded ) { + if ( m->b.maxx-m->b.minx > m->b.maxy-m->b.miny ) { + top = m->b.maxx; + bottom = m->b.minx; + which = 0; + } else { + top = m->b.maxy; + bottom = m->b.miny; + which = 1; + } + for ( b=0; ends[which][b]<=bottom; ++b ); + for ( t=b; ends[which][t]<top; ++t ); + --t; + /* b points to an endpoint which is greater than bottom */ + /* t points to an endpoint which is less than top */ + test = (top+bottom)/2; + for ( i=b; i<=t; ++i ) { + if ( RealNearish(test,ends[which][i]) ) { + if ( i==b ) + test = (bottom+ends[which][i])/2; + else + test = (ends[which][i-1]+ends[which][i])/2; + break; + } + } + FigureNeeds(ms,which,test,space,ot,1); + } + free(ends[0]); + free(ends[1]); + free(space); + free(gaps); +} + +static void FindUnitVectors(Intersection *ilist) { + MList *ml; + Intersection *il; + BasePoint u; + double len; + + for ( il=ilist; il!=NULL; il=il->next ) { + for ( ml=il->monos; ml!=NULL; ml=ml->next ) { + if ( ml->m->isneeded ) { + Spline *s = ml->m->s; + double t1, t2; + t1 = ml->t; + if ( ml->isend ) + t2 = ml->t - (ml->t-ml->m->tstart)/20.0; + else + t2 = ml->t + (ml->m->tend-ml->t)/20.0; + u.x = ((s->splines[0].a*t1 + s->splines[0].b)*t1 + s->splines[0].c)*t1 - + ((s->splines[0].a*t2 + s->splines[0].b)*t2 + s->splines[0].c)*t2; + u.y = ((s->splines[1].a*t1 + s->splines[1].b)*t1 + s->splines[1].c)*t1 - + ((s->splines[1].a*t2 + s->splines[1].b)*t2 + s->splines[1].c)*t2; + len = u.x*u.x + u.y*u.y; + if ( len!=0 ) { + len = sqrt(len); + u.x /= len; + u.y /= len; + } + ml->unit = u; + } + } + } +} + +static void TestForBadDirections(Intersection *ilist) { + /* If we have a glyph with at least two contours one drawn clockwise, */ + /* one counter, and these two intersect, then our algorithm will */ + /* not remove what appears to the user to be an overlap. Warn about */ + /* this. */ + /* I think it happens iff all exits from an intersection are needed */ + MList *ml, *ml2; + int cnt, ncnt; + Intersection *il; + + /* If we have two splines one going from a->b and the other from b->a */ + /* tracing exactly the same route, then they should cancel each other */ + /* out. But depending on the order we hit them they may both be marked */ + /* needed */ /* OverlapBugs.sfd: asciicircumflex */ + for ( il=ilist; il!=NULL; il=il->next ) { + for ( ml=il->monos; ml!=NULL; ml=ml->next ) { + if ( ml->m->isneeded && ml->m->s->knownlinear && + ml->m->start!=NULL && ml->m->end!=NULL ) { + for ( ml2 = ml->next; ml2!=NULL; ml2=ml2->next ) { + if ( ml2->m->isneeded && ml2->m->s->knownlinear && + ml2->m->start == ml->m->end && + ml2->m->end == ml->m->start ) { + ml2->m->isneeded = false; + ml->m->isneeded = false; + ml2->m->isunneeded = true; + ml->m->isunneeded = true; + break; + } + } + } + } + } + + while ( ilist!=NULL ) { + cnt = ncnt = 0; + for ( ml = ilist->monos; ml!=NULL; ml=ml->next ) { + ++cnt; + if ( ml->m->isneeded ) ++ncnt; + } + ilist = ilist->next; + } +} + +static void MonoFigure(Spline *s,extended firstt,extended endt, SplinePoint *first, + SplinePoint *end) { + extended f; + Spline1D temp; + + f = endt - firstt; + /*temp.d = first->me.x;*/ + /*temp.a = s->splines[0].a*f*f*f;*/ + temp.b = (s->splines[0].b + 3*s->splines[0].a*firstt) *f*f; + temp.c = (s->splines[0].c + 2*s->splines[0].b*firstt + 3*s->splines[0].a*firstt*firstt) * f; + first->nextcp.x = first->me.x + temp.c/3; + end->prevcp.x = first->nextcp.x + (temp.b+temp.c)/3; + if ( temp.c>-.01 && temp.c<.01 ) first->nextcp.x = first->me.x; + if ( (temp.b+temp.c)>-.01 && (temp.b+temp.c)<.01 ) end->prevcp.x = end->me.x; + + temp.b = (s->splines[1].b + 3*s->splines[1].a*firstt) *f*f; + temp.c = (s->splines[1].c + 2*s->splines[1].b*firstt + 3*s->splines[1].a*firstt*firstt) * f; + first->nextcp.y = first->me.y + temp.c/3; + end->prevcp.y = first->nextcp.y + (temp.b+temp.c)/3; + if ( temp.c>-.01 && temp.c<.01 ) first->nextcp.y = first->me.y; + if ( (temp.b+temp.c)>-.01 && (temp.b+temp.c)<.01 ) end->prevcp.y = end->me.y; + first->nonextcp = false; end->noprevcp = false; + SplineMake3(first,end); + if ( SplineIsLinear(first->next)) { + first->nextcp = first->me; + end->prevcp = end->me; + first->nonextcp = end->noprevcp = true; + SplineRefigure(first->next); + } +} + +static Intersection *MonoFollow(Intersection *curil, Monotonic *m) { + Monotonic *mstart=m; + + if ( m->start==curil ) { + while ( m!=NULL && m->end==NULL ) { + m=m->next; + if ( m==mstart ) + break; + } + if ( m==NULL ) +return( NULL ); + +return( m->end ); + } else { + while ( m!=NULL && m->start==NULL ) { + m=m->prev; + if ( m==mstart ) + break; + } + if ( m==NULL ) +return( NULL ); + +return( m->start ); + } +} + +static int MonoGoesSomewhereUseful(Intersection *curil, Monotonic *m) { + Intersection *nextil = MonoFollow(curil,m); + MList *ml; + int cnt; + + if ( nextil==NULL ) +return( false ); + cnt = 0; + for ( ml=nextil->monos; ml!=NULL ; ml=ml->next ) + if ( ml->m->isneeded ) + ++cnt; + if ( cnt>=2 ) /* One for the mono that one in, one for another going out... */ +return( true ); + +return( false ); +} + +static MList *FindMLOfM(Intersection *curil,Monotonic *finalm) { + MList *ml; + + for ( ml=curil->monos; ml!=NULL; ml=ml->next ) { + if ( ml->m==finalm ) +return( ml ); + } +return( NULL ); +} + +static SplinePoint *MonoFollowForward(Intersection **curil, MList *ml, + SplinePoint *last, Monotonic **finalm) { + SplinePoint *mid; + Monotonic *m = ml->m, *mstart; + + forever { + for ( mstart = m; m->s==mstart->s; m=m->next) { + if ( !m->isneeded ) + SOError( "Expected needed monotonic.\n" ); + m->isneeded = false; /* Mark as used */ + if ( m->end!=NULL ) + break; + } + if ( m->s==mstart->s ) { + if ( m->end==NULL ) SOError( "Invariant condition does not hold.\n" ); + mid = SplinePointCreate(m->end->inter.x,m->end->inter.y); + } else { + m = m->prev; + mid = SplinePointCreate(m->s->to->me.x,m->s->to->me.y); + } + if ( mstart->tstart==0 && m->tend==1.0 ) { + /* I check for this special case to avoid rounding errors */ + last->nextcp = m->s->from->nextcp; + last->nonextcp = m->s->from->nonextcp; + mid->prevcp = m->s->to->prevcp; + mid->noprevcp = m->s->to->noprevcp; + SplineMake3(last,mid); + } else { + MonoFigure(m->s,mstart->tstart,m->tend,last,mid); + } + last = mid; + if ( m->end!=NULL ) { + *curil = m->end; + *finalm = m; +return( last ); + } + m = m->next; + } +} + +static SplinePoint *MonoFollowBackward(Intersection **curil, MList *ml, + SplinePoint *last, Monotonic **finalm) { + SplinePoint *mid; + Monotonic *m = ml->m, *mstart; + + forever { + for ( mstart=m; m->s==mstart->s; m=m->prev) { + if ( !m->isneeded ) + SOError( "Expected needed monotonic.\n" ); + m->isneeded = false; /* Mark as used */ + if ( m->start!=NULL ) + break; + } + if ( m->s==mstart->s ) { + if ( m->start==NULL ) SOError( "Invariant condition does not hold.\n" ); + mid = SplinePointCreate(m->start->inter.x,m->start->inter.y); + } else { + m = m->next; + mid = SplinePointCreate(m->s->from->me.x,m->s->from->me.y); + } + if ( m->s->knownlinear ) mid->pointtype = pt_corner; + if ( mstart->tend==1.0 && m->tstart==0 ) { + /* I check for this special case to avoid rounding errors */ + last->nextcp = m->s->to->prevcp; + last->nonextcp = m->s->to->noprevcp; + mid->prevcp = m->s->from->nextcp; + mid->noprevcp = m->s->from->nonextcp; + SplineMake3(last,mid); + } else { + MonoFigure(m->s,mstart->tend,m->tstart,last,mid); + } + last = mid; + if ( m->start!=NULL ) { + *curil = m->start; + *finalm = m; +return( last ); + } + m = m->prev; + } +} + +static SplineSet *JoinAContour(Intersection *startil,MList *ml) { + SplineSet *ss = chunkalloc(sizeof(SplineSet)); + SplinePoint *last; + Intersection *curil; + int allexclude = ml->m->exclude; + Monotonic *finalm; + MList *lastml; + + ss->first = last = SplinePointCreate(startil->inter.x,startil->inter.y); + curil = startil; + forever { + if ( allexclude && !ml->m->exclude ) allexclude = false; + finalm = NULL; + if ( ml->m->start==curil ) { + last = MonoFollowForward(&curil,ml,last,&finalm); + } else if ( ml->m->end==curil ) { + last = MonoFollowBackward(&curil,ml,last,&finalm); + } else { + SOError( "Couldn't find endpoint (%g,%g).\n", + curil->inter.x, curil->inter.y ); + ml->m->isneeded = false; /* Prevent infinite loops */ + ss->last = last; + break; + } + if ( curil==startil ) { + ss->first->prev = last->prev; + ss->first->prevcp = last->prevcp; + ss->first->noprevcp = last->noprevcp; + last->prev->to = ss->first; + SplinePointFree(last); + ss->last = ss->first; + break; + } + lastml = FindMLOfM(curil,finalm); + if ( lastml==NULL ) { + IError("Could not find finalm"); + /* Try to preserve direction */ + for ( ml=curil->monos; ml!=NULL && (!ml->m->isneeded || ml->m->end==curil); ml=ml->next ); + if ( ml==NULL ) + for ( ml=curil->monos; ml!=NULL && !ml->m->isneeded; ml=ml->next ); + } else { + int k; MList *bestml; double bestdot; + for ( k=0; k<2; ++k ) { + bestml = NULL; bestdot = -2; + for ( ml=curil->monos; ml!=NULL ; ml=ml->next ) { + if ( ml->m->isneeded && (ml->m->start==curil || k) ) { + double dot = lastml->unit.x*ml->unit.x + lastml->unit.y*ml->unit.y; + if ( dot>bestdot ) { + bestml = ml; + bestdot = dot; + } + } + } + if ( bestml!=NULL ) + break; + } + ml = bestml; + } + if ( ml==NULL ) { + for ( ml=curil->monos; ml!=NULL ; ml=ml->next ) + if ( ml->m->isunneeded && ml->m->start==curil && + MonoFollow(curil,ml->m)==startil ) + break; + if ( ml==NULL ) + for ( ml=curil->monos; ml!=NULL ; ml=ml->next ) + if ( ml->m->isunneeded && ml->m->end==curil && + MonoFollow(curil,ml->m)==startil ) + break; + if ( ml!=NULL ) { + SOError("Closing contour with unneeded path\n" ); + ml->m->isneeded = true; + } + } + if ( ml==NULL ) { + SOError( "couldn't find a needed exit from an intersection\n" ); + ss->last = last; + break; + } + } + SPLCatagorizePoints(ss); + if ( allexclude && SplinePointListIsClockwise(ss)) + SplineSetReverse(ss); +return( ss ); +} + +static SplineSet *FindMatchingContour(SplineSet *head,SplineSet *cur) { + SplineSet *test; + + for ( test=head; test!=NULL; test=test->next ) { + if ( test->first->prev==NULL && + test->first->me.x==cur->last->me.x && test->first->me.y==cur->last->me.y && + test->last->me.x==cur->first->me.x && test->last->me.y==cur->first->me.y ) + break; + } + if ( test==NULL ) { + for ( test=head; test!=NULL; test=test->next ) { + if ( test->first->prev==NULL && + test->last->me.x==cur->last->me.x && test->last->me.y==cur->last->me.y && + test->first->me.x==cur->first->me.x && test->first->me.y==cur->first->me.y ) { + SplineSetReverse(cur); + break; + } + } + } + if ( test==NULL ) { + for ( test=head; test!=NULL; test=test->next ) { + if ( test->first->prev==NULL && + ((test->first->me.x==cur->last->me.x && test->first->me.y==cur->last->me.y) || + (test->last->me.x==cur->first->me.x && test->last->me.y==cur->first->me.y ))) + break; + } + } + if ( test==NULL ) { + for ( test=head; test!=NULL; test=test->next ) { + if ( test->first->prev==NULL && + ((test->last->me.x==cur->last->me.x && test->last->me.y==cur->last->me.y) || + (test->first->me.x==cur->first->me.x && test->first->me.y==cur->first->me.y ))) { + SplineSetReverse(cur); + break; + } + } + } +return( test ); +} + +static SplineSet *JoinAllNeeded(Intersection *ilist) { + Intersection *il; + SplineSet *head=NULL, *last=NULL, *cur, *test; + MList *ml; + + for ( il=ilist; il!=NULL; il=il->next ) { + /* Try to preserve direction */ + forever { + for ( ml=il->monos; ml!=NULL && (!ml->m->isneeded || ml->m->end==il); ml=ml->next ); + if ( ml==NULL ) + for ( ml=il->monos; ml!=NULL && !ml->m->isneeded; ml=ml->next ); + if ( ml==NULL ) + break; + if ( !MonoGoesSomewhereUseful(il,ml->m)) { + SOError("Humph. This monotonic leads nowhere.\n" ); + /* break; */ + } + cur = JoinAContour(il,ml); + if ( head==NULL ) + head = cur; + else { + if ( cur->first->prev==NULL ) { + /* Open contours are errors. See if we had an earlier error */ + /* to which we can join this */ + test = FindMatchingContour(head,cur); + if ( test!=NULL ) { + if ( test->first->me.x==cur->last->me.x && test->first->me.y==cur->last->me.y ) { + test->first->prev = cur->last->prev; + cur->last->prev->to = test->first; + SplinePointFree(cur->last); + if ( test->last->me.x==cur->first->me.x && test->last->me.y==cur->first->me.y ) { + test->last->next = cur->first->next; + cur->first->next->from = test->last; + SplinePointFree(cur->first); + test->last = test->first; + } else + test->first = cur->first; + } else { + if ( test->last->me.x!=cur->first->me.x || test->last->me.y!=cur->first->me.y ) + SOError( "Join failed"); + else { + test->last->next = cur->first->next; + cur->first->next->from = test->last; + SplinePointFree(cur->first); + test->last = test->first; + } + } + cur->first = cur->last = NULL; + SplinePointListFree(cur); + cur=NULL; + } + } + if ( cur!=NULL ) + last->next = cur; + } + if ( cur!=NULL ) + last = cur; + } + } +return( head ); +} + +static SplineSet *MergeOpenAndFreeClosed(SplineSet *new,SplineSet *old, + enum overlap_type ot) { + SplineSet *next; + + while ( old!=NULL ) { + next = old->next; + if ( old->first->prev==NULL || + (( ot==over_rmselected || ot==over_intersel || ot==over_fisel) && + !SSIsSelected(old)) ) { + old->next = new; + new = old; + } else { + old->next = NULL; + SplinePointListFree(old); + } + old = next; + } +return(new); +} + +static void FreeMonotonics(Monotonic *m) { + Monotonic *next; + + while ( m!=NULL ) { + next = m->linked; + chunkfree(m,sizeof(*m)); + m = next; + } +} + +static void FreeMList(MList *ml) { + MList *next; + + while ( ml!=NULL ) { + next = ml->next; + chunkfree(ml,sizeof(*ml)); + ml = next; + } +} + +static void FreeIntersections(Intersection *ilist) { + Intersection *next; + + while ( ilist!=NULL ) { + next = ilist->next; + FreeMList(ilist->monos); + chunkfree(ilist,sizeof(*ilist)); + ilist = next; + } +} + +static void MonoSplit(Monotonic *m) { + Spline *s = m->s; + SplinePoint *last = s->from; + SplinePoint *final = s->to; + extended lastt = 0; + + last->next = NULL; + final->prev = NULL; + while ( m!=NULL && m->s==s && m->tend<1 ) { + if ( m->end!=NULL ) { + SplinePoint *mid = SplinePointCreate(m->end->inter.x,m->end->inter.y); + if ( m->s->knownlinear ) mid->pointtype = pt_corner; + MonoFigure(s,lastt,m->tend,last,mid); + lastt = m->tend; + last = mid; + } + m = m->linked; + } + MonoFigure(s,lastt,1.0,last,final); + SplineFree(s); +} + +static void FixupIntersectedSplines(Monotonic *ms) { + /* If all we want is intersections, then the contours are already correct */ + /* all we need to do is run through the Monotonic list and when we find */ + /* an intersection, make sure it has real splines around it */ + Monotonic *m; + int needs_split; + + while ( ms!=NULL ) { + needs_split = false; + for ( m=ms; m!=NULL && m->s==ms->s; m=m->linked ) { + if ( (m->tstart!=0 && m->start!=NULL) || (m->tend!=1 && m->end!=NULL)) + needs_split = true; + } + if ( needs_split ) + MonoSplit(ms); + ms = m; + } +} + +static int BpClose(BasePoint *here, BasePoint *there, double error) { + extended dx, dy; + + if ( (dx = here->x-there->x)<0 ) dx= -dx; + if ( (dy = here->y-there->y)<0 ) dy= -dy; + if ( dx<error && dy<error ) +return( true ); + +return( false ); +} + +static SplineSet *SSRemoveTiny(SplineSet *base) { + DBounds b; + double error; + extended test, dx, dy; + SplineSet *prev = NULL, *head = base, *ssnext; + SplinePoint *sp, *nsp; + + SplineSetQuickBounds(base,&b); + error = b.maxy-b.miny; + test = b.maxx-b.minx; + if ( test>error ) error = test; + if ( (test = b.maxy)<0 ) test = -test; + if ( test>error ) error = test; + if ( (test = b.maxx)<0 ) test = -test; + if ( test>error ) error = test; + error /= 30000; + + while ( base!=NULL ) { + ssnext = base->next; + for ( sp=base->first; ; ) { + if ( sp->next==NULL ) + break; + nsp = sp->next->to; + if ( BpClose(&sp->me,&nsp->me,error) ) { + if ( BpClose(&sp->me,&sp->nextcp,2*error) && + BpClose(&nsp->me,&nsp->prevcp,2*error)) { + /* Remove the spline */ + if ( nsp==sp ) { + /* Only this spline in the contour, so remove the contour */ + base->next = NULL; + SplinePointListFree(base); + if ( prev==NULL ) + head = ssnext; + else + prev->next = ssnext; + base = NULL; + break; + } + SplineFree(sp->next); + if ( nsp->nonextcp ) { + sp->nextcp = sp->me; + sp->nonextcp = true; + } else { + sp->nextcp = nsp->nextcp; + sp->nonextcp = false; + } + sp->nextcpdef = nsp->nextcpdef; + sp->next = nsp->next; + if ( nsp->next!=NULL ) { + nsp->next->from = sp; + SplineRefigure(sp->next); + } + if ( nsp==base->last ) + base->last = sp; + if ( nsp==base->first ) + base->first = sp; + SplinePointFree(nsp); + if ( sp->next==NULL ) + break; + nsp = sp->next->to; + } else { + /* Leave the spline, but move the two points together */ + BasePoint new; + new.x = (sp->me.x+nsp->me.x)/2; + new.y = (sp->me.y+nsp->me.y)/2; + dx = new.x-sp->me.x; dy = new.y-sp->me.y; + sp->me = new; + sp->nextcp.x += dx; sp->nextcp.y += dy; + sp->prevcp.x += dx; sp->prevcp.y += dy; + dx = new.x-nsp->me.x; dy = new.y-nsp->me.y; + nsp->me = new; + nsp->nextcp.x += dx; nsp->nextcp.y += dy; + nsp->prevcp.x += dx; nsp->prevcp.y += dy; + SplineRefigure(sp->next); + if ( sp->prev ) SplineRefigure(sp->prev); + if ( nsp->next ) SplineRefigure(nsp->next); + } + } + sp = nsp; + if ( sp==base->first ) + break; + } + if ( sp->prev!=NULL && !sp->noprevcp ) { + int refigure = false; + if ( sp->me.x-sp->prevcp.x>-error && sp->me.x-sp->prevcp.x<error ) { + sp->prevcp.x = sp->me.x; + refigure = true; + } + if ( sp->me.y-sp->prevcp.y>-error && sp->me.y-sp->prevcp.y<error ) { + sp->prevcp.y = sp->me.y; + refigure = true; + } + if ( sp->me.x==sp->prevcp.x && sp->me.y==sp->prevcp.y ) + sp->noprevcp = true; + if ( refigure ) + SplineRefigure(sp->prev); + } + if ( sp->next!=NULL && !sp->nonextcp ) { + int refigure = false; + if ( sp->me.x-sp->nextcp.x>-error && sp->me.x-sp->nextcp.x<error ) { + sp->nextcp.x = sp->me.x; + refigure = true; + } + if ( sp->me.y-sp->nextcp.y>-error && sp->me.y-sp->nextcp.y<error ) { + sp->nextcp.y = sp->me.y; + refigure = true; + } + if ( sp->me.x==sp->nextcp.x && sp->me.y==sp->nextcp.y ) + sp->nonextcp = true; + if ( refigure ) + SplineRefigure(sp->next); + } + if ( base!=NULL ) + prev = base; + base = ssnext; + } + +return( head ); +} + +static void RemoveNextSP(SplinePoint *psp,SplinePoint *sp,SplinePoint *nsp, + SplineSet *base) { + if ( psp==nsp ) { + SplineFree(psp->next); + psp->next = psp->prev; + psp->next->from = psp; + SplinePointFree(sp); + SplineRefigure(psp->prev); + } else { + psp->next = nsp->next; + psp->next->from = psp; + psp->nextcp = nsp->nextcp; + psp->nonextcp = nsp->nonextcp; + psp->nextcpdef = nsp->nextcpdef; + SplineFree(sp->prev); + SplineFree(sp->next); + SplinePointFree(sp); + SplinePointFree(nsp); + SplineRefigure(psp->next); + } + if ( base->first==sp || base->first==nsp ) + base->first = psp; + if ( base->last==sp || base->last==nsp ) + base->last = psp; +} + +static void RemovePrevSP(SplinePoint *psp,SplinePoint *sp,SplinePoint *nsp, + SplineSet *base) { + if ( psp==nsp ) { + SplineFree(nsp->prev); + nsp->prev = nsp->next; + nsp->prev->to = nsp; + SplinePointFree(sp); + SplineRefigure(nsp->next); + } else { + nsp->prev = psp->prev; + nsp->prev->to = nsp; + nsp->prevcp = nsp->me; + nsp->noprevcp = true; + nsp->prevcpdef = psp->prevcpdef; + SplineFree(sp->prev); + SplineFree(sp->next); + SplinePointFree(sp); + SplinePointFree(psp); + SplineRefigure(nsp->prev); + } + if ( base->first==sp || base->first==psp ) + base->first = nsp; + if ( base->last==sp || base->last==psp ) + base->last = nsp; +} + +static SplinePoint *SameLine(SplinePoint *psp, SplinePoint *sp, SplinePoint *nsp) { + BasePoint noff, poff; + real nlen, plen, normal; + + noff.x = nsp->me.x-sp->me.x; noff.y = nsp->me.y-sp->me.y; + poff.x = psp->me.x-sp->me.x; poff.y = psp->me.y-sp->me.y; + nlen = esqrt(noff.x*noff.x + noff.y*noff.y); + plen = esqrt(poff.x*poff.x + poff.y*poff.y); + if ( nlen==0 ) +return( nsp ); + if ( plen==0 ) +return( psp ); + normal = (noff.x*poff.y - noff.y*poff.x)/nlen/plen; + if ( normal<-.0001 || normal>.0001 ) +return( NULL ); + + if ( noff.x*poff.x < 0 || noff.y*poff.y < 0 ) +return( NULL ); /* Same line, but different directions */ + if ( (noff.x>0 && noff.x>poff.x) || + (noff.x<0 && noff.x<poff.x) || + (noff.y>0 && noff.y>poff.y) || + (noff.y<0 && noff.y<poff.y)) +return( nsp ); + +return( psp ); +} + +static double AdjacentSplinesMatch(Spline *s1,Spline *s2,int s2forward) { + /* Is every point on s2 close to a point on s1 */ + double t, tdiff, t1 = -1; + double xoff, yoff; + double t1start, t1end; + extended ts[2]; + int i; + + if ( (xoff = s2->to->me.x-s2->from->me.x)<0 ) xoff = -xoff; + if ( (yoff = s2->to->me.y-s2->from->me.y)<0 ) yoff = -yoff; + if ( xoff>yoff ) + SplineFindExtrema(&s1->splines[0],&ts[0],&ts[1]); + else + SplineFindExtrema(&s1->splines[1],&ts[0],&ts[1]); + if ( s2forward ) { + t = 0; + tdiff = 1/16.0; + t1end = 1; + for ( i=1; i>=0 && ts[i]==-1; --i ); + t1start = i<0 ? 0 : ts[i]; + } else { + t = 1; + tdiff = -1/16.0; + t1start = 0; + t1end = ( ts[0]==-1 ) ? 1.0 : ts[0]; + } + + for ( ; (s2forward && t<=1) || (!s2forward && t>=0 ); t += tdiff ) { + double x1, y1, xo, yo; + double x = ((s2->splines[0].a*t+s2->splines[0].b)*t+s2->splines[0].c)*t+s2->splines[0].d; + double y = ((s2->splines[1].a*t+s2->splines[1].b)*t+s2->splines[1].c)*t+s2->splines[1].d; + if ( xoff>yoff ) + t1 = IterateSplineSolve(&s1->splines[0],t1start,t1end,x,.001); + else + t1 = IterateSplineSolve(&s1->splines[1],t1start,t1end,y,.001); + if ( t1<0 || t1>1 ) +return( -1 ); + x1 = ((s1->splines[0].a*t1+s1->splines[0].b)*t1+s1->splines[0].c)*t1+s1->splines[0].d; + y1 = ((s1->splines[1].a*t1+s1->splines[1].b)*t1+s1->splines[1].c)*t1+s1->splines[1].d; + if ( (xo = (x-x1))<0 ) xo = -xo; + if ( (yo = (y-y1))<0 ) yo = -yo; + if ( xo+yo>.5 ) +return( -1 ); + } +return( t1 ); +} + +static void SSRemoveBacktracks(SplineSet *ss) { + SplinePoint *sp; + + if ( ss==NULL ) +return; + for ( sp=ss->first; ; ) { + if ( sp->next!=NULL && sp->prev!=NULL ) { + SplinePoint *nsp = sp->next->to, *psp = sp->prev->from, *isp; + BasePoint ndir, pdir; + double dot, pdot, nlen, plen, t = -1; + + ndir.x = (nsp->me.x - sp->me.x); ndir.y = (nsp->me.y - sp->me.y); + pdir.x = (psp->me.x - sp->me.x); pdir.y = (psp->me.y - sp->me.y); + nlen = ndir.x*ndir.x + ndir.y*ndir.y; plen = pdir.x*pdir.x + pdir.y*pdir.y; + dot = ndir.x*pdir.x + ndir.y*pdir.y; + if ( (pdot = ndir.x*pdir.y - ndir.y*pdir.x)<0 ) pdot = -pdot; + if ( dot>0 && dot>pdot ) { + if ( nlen>plen && (t=AdjacentSplinesMatch(sp->next,sp->prev,false))!=-1 ) { + isp = SplineBisect(sp->next,t); + psp->nextcp.x = psp->me.x + (isp->nextcp.x-isp->me.x); + psp->nextcp.y = psp->me.y + (isp->nextcp.y-isp->me.y); + psp->nonextcp = isp->nonextcp; + psp->next = isp->next; + isp->next->from = psp; + SplineFree(isp->prev); + SplineFree(sp->prev); + SplinePointFree(isp); + SplinePointFree(sp); + if ( psp->next->order2 ) { + psp->nextcp.x = nsp->prevcp.x = (psp->nextcp.x+nsp->prevcp.x)/2; + psp->nextcp.y = nsp->prevcp.y = (psp->nextcp.y+nsp->prevcp.y)/2; + if ( psp->nonextcp || nsp->noprevcp ) + psp->nonextcp = nsp->noprevcp = true; + } + SplineRefigure(psp->next); + if ( ss->first==sp ) + ss->first = psp; + if ( ss->last==sp ) + ss->last = psp; + sp=psp; + } else if ( nlen<plen && (t=AdjacentSplinesMatch(sp->prev,sp->next,true))!=-1 ) { + isp = SplineBisect(sp->prev,t); + nsp->prevcp.x = nsp->me.x + (isp->prevcp.x-isp->me.x); + nsp->prevcp.y = nsp->me.y + (isp->prevcp.y-isp->me.y); + nsp->noprevcp = isp->noprevcp; + nsp->prev = isp->prev; + isp->prev->to = nsp; + SplineFree(isp->next); + SplineFree(sp->next); + SplinePointFree(isp); + SplinePointFree(sp); + if ( psp->next->order2 ) { + psp->nextcp.x = nsp->prevcp.x = (psp->nextcp.x+nsp->prevcp.x)/2; + psp->nextcp.y = nsp->prevcp.y = (psp->nextcp.y+nsp->prevcp.y)/2; + if ( psp->nonextcp || nsp->noprevcp ) + psp->nonextcp = nsp->noprevcp = true; + } + SplineRefigure(nsp->prev); + if ( ss->first==sp ) + ss->first = psp; + if ( ss->last==sp ) + ss->last = psp; + sp=psp; + } + } + } + if ( sp->next==NULL ) + break; + sp=sp->next->to; + if ( sp==ss->first ) + break; + } +} + +/* If we have a contour with no width, say a line from A to B and then from B */ +/* to A, then it will be ambiguous, depending on how we hit the contour, as */ +/* to whether it is needed or not. Which will cause us to complain. Since */ +/* they contain no area, they achieve nothing, so we might as well say they */ +/* overlap themselves and remove them here */ +static SplineSet *SSRemoveReversals(SplineSet *base) { + SplineSet *head = base, *prev=NULL, *next; + SplinePoint *sp; + int changed; + + while ( base!=NULL ) { + next = base->next; + changed = true; + while ( changed ) { + changed = false; + if ( base->first->next==NULL || + (base->first->next->to==base->first && + base->first->nextcp.x==base->first->prevcp.x && + base->first->nextcp.y==base->first->prevcp.y)) { + /* remove single points */ + if ( prev==NULL ) + head = next; + else + prev->next = next; + base->next = NULL; + SplinePointListFree(base); + base = prev; + break; + } + for ( sp=base->first; ; ) { + if ( sp->next!=NULL && sp->prev!=NULL && + sp->nextcp.x==sp->prevcp.x && sp->nextcp.y==sp->prevcp.y ) { + SplinePoint *nsp = sp->next->to, *psp = sp->prev->from, *isp; + if ( psp->me.x==nsp->me.x && psp->me.y==nsp->me.y && + psp->nextcp.x==nsp->prevcp.x && psp->nextcp.y==nsp->prevcp.y ) { + /* We wish to remove sp, sp->next, sp->prev & one of nsp/psp */ + RemoveNextSP(psp,sp,nsp,base); + changed = true; + break; + } else if ( sp->nonextcp /* which implies sp->noprevcp */ && + psp->nonextcp && nsp->noprevcp && + (isp = SameLine(psp,sp,nsp))!=NULL ) { + /* We have a line that backtracks, but doesn't cover */ + /* the entire spline, so we intersect */ + /* We want to remove sp, the shorter of sp->next, sp->prev */ + /* and a bit of the other one. Also reomve one of nsp,psp */ + if ( isp==psp ) { + RemoveNextSP(psp,sp,nsp,base); + psp->nextcp = psp->me; + psp->nonextcp = true; + } else { + RemovePrevSP(psp,sp,nsp,base); + } + changed = true; + break; + } + } + if ( sp->next==NULL ) + break; + sp = sp->next->to; + if ( sp==base->first ) + break; + } + } + SSRemoveBacktracks(base); + prev = base; + base = next; + } +return( head ); +} + +SplineSet *SplineSetRemoveOverlap(SplineChar *sc, SplineSet *base,enum overlap_type ot) { + Monotonic *ms; + Intersection *ilist; + SplineSet *ret; + SplineSet *order3 = NULL; + int is_o2 = false; + SplineSet *ss; + + for ( ss=base; ss!=NULL; ss=ss->next ) + if ( ss->first->next!=NULL ) { + is_o2 = ss->first->next->order2; + break; + } + if ( is_o2 ) { + order3 = SplineSetsPSApprox(base); + SplinePointListsFree(base); + base = order3; + } + + if ( sc!=NULL ) + glyphname = sc->name; + + base = SSRemoveTiny(base); + SSRemoveStupidControlPoints(base); + SplineSetsRemoveAnnoyingExtrema(base,.3); + SSOverlapClusterCpAngles(base,.01); + base = SSRemoveReversals(base); + ms = SSsToMContours(base,ot); + ilist = FindIntersections(ms,ot); + Validate(ms,ilist); + if ( ot==over_findinter || ot==over_fisel ) { + FixupIntersectedSplines(ms); + ret = base; + } else { + FindNeeded(ms,ot); + FindUnitVectors(ilist); + if ( ot==over_remove || ot == over_rmselected ) + TestForBadDirections(ilist); + ret = JoinAllNeeded(ilist); + ret = MergeOpenAndFreeClosed(ret,base,ot); + } + FreeMonotonics(ms); + FreeIntersections(ilist); + glyphname = NULL; + if ( order3!=NULL ) { + ss = SplineSetsTTFApprox(ret); + SplinePointListsFree(ret); + ret = ss; + } +return( ret ); +} |