diff options
author | Karl Berry <karl@freefriends.org> | 2013-04-07 18:19:31 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2013-04-07 18:19:31 +0000 |
commit | 752012c605d34cd943795527a9738475a6958fcc (patch) | |
tree | 4ee06acdd8333a662c2d6f6ef716235053468f55 /Master/texmf-dist/asymptote/bezulate.asy | |
parent | 9789d09132f18a838e84f041b4b3aff28d3426ec (diff) |
texmf -> texmf-dist: start with unique dirs from texmf
git-svn-id: svn://tug.org/texlive/trunk@29712 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/asymptote/bezulate.asy')
-rw-r--r-- | Master/texmf-dist/asymptote/bezulate.asy | 254 |
1 files changed, 254 insertions, 0 deletions
diff --git a/Master/texmf-dist/asymptote/bezulate.asy b/Master/texmf-dist/asymptote/bezulate.asy new file mode 100644 index 00000000000..5b21d8c1605 --- /dev/null +++ b/Master/texmf-dist/asymptote/bezulate.asy @@ -0,0 +1,254 @@ +// Bezier triangulation routines written by Orest Shardt, 2008. + +private real fuzz=sqrtEpsilon; +real duplicateFuzz=1e-3; // Work around font errors. + +private real[][] intersections(pair a, pair b, path p) +{ + pair delta=fuzz*unit(b-a); + return intersections(a-delta--b+delta,p,fuzz); +} + +int countIntersections(path[] p, pair start, pair end) +{ + int intersects=0; + for(path q : p) + intersects += intersections(start,end,q).length; + return intersects; +} + +path[][] containmentTree(path[] paths) +{ + path[][] result; + for(path g : paths) { + // check if current curve contains or is contained in a group of curves + int j; + for(j=0; j < result.length; ++j) { + path[] resultj=result[j]; + int test=inside(g,resultj[0],zerowinding); + if(test == 1) { + // current curve contains group's toplevel curve; + // replace toplevel curve with current curve + resultj.insert(0,g); + // check to see if any other groups are contained within this curve + for(int k=j+1; k < result.length;) { + if(inside(g,result[k][0]) == 1) { + resultj.append(result[k]); + result.delete(k); + } else ++k; + } + break; + } else if(test == -1) { + // current curve contained within group's toplevel curve + resultj.push(g); + break; + } + } + // create a new group if this curve does not belong to another group + if(j == result.length) + result.push(new path[] {g}); + } + return result; +} + +bool isDuplicate(pair a, pair b, real relSize) +{ + return abs(a-b) <= duplicateFuzz*relSize; +} + +path removeDuplicates(path p) +{ + real relSize = abs(max(p)-min(p)); + bool cyclic=cyclic(p); + for(int i=0; i < length(p); ++i) { + if(isDuplicate(point(p,i),point(p,i+1),relSize)) { + p=subpath(p,0,i)&subpath(p,i+1,length(p)); + --i; + } + } + return cyclic ? p&cycle : p; +} + +path section(path p, real t1, real t2, bool loop=false) +{ + if(t2 < t1 || loop && t1 == t2) + t2 += length(p); + return subpath(p,t1,t2); +} + +path uncycle(path p, real t) +{ + return subpath(p,t,t+length(p)); +} + +// returns outer paths +void connect(path[] paths, path[] result, path[] patch) +{ + path[][] tree=containmentTree(paths); + for(path[] group : tree) { + path outer = group[0]; + group.delete(0); + path[][] innerTree = containmentTree(group); + path[] remainingCurves; + path[] inners; + for(path[] innerGroup:innerTree) + { + inners.push(innerGroup[0]); + if(innerGroup.length>1) + remainingCurves.append(innerGroup[1:]); + } + connect(remainingCurves,result,patch); + real d=2*abs(max(outer)-min(outer)); + while(inners.length > 0) { + int curveIndex = 0; + pair direction=I*dir(inners[curveIndex],0,1); // Use outgoing direction + if(direction == 0) // Try a random direction + direction=expi(2pi*unitrand()); + pair start=point(inners[curveIndex],0); + + // find first intersection of line segment with outer curve + real[][] ints=intersections(start,start+d*direction,outer); + assert(ints.length != 0); + real endtime=ints[0][1]; // endtime is time on outer + pair end = point(outer,endtime); + + // find first intersection of end--start with any inner curve + real starttime=0; // starttime is time on inners[curveIndex] + real earliestTime=1; + for(int j=0; j < inners.length; ++j) { + real[][] ints=intersections(end,start,inners[j]); + if(ints.length > 0 && ints[0][0] < earliestTime) { + earliestTime=ints[0][0]; // time on end--start + starttime=ints[0][1]; // time on inner curve + curveIndex=j; + } + } + start=point(inners[curveIndex],starttime); + + real timeoffset=2; + bool found=false; + path portion; + path[] allCurves = {outer}; + allCurves.append(inners); + + while(!found && timeoffset > fuzz) { + timeoffset /= 2; + if(countIntersections(allCurves,start, + point(outer,endtime+timeoffset)) == 2) + { + portion = subpath(outer,endtime,endtime+timeoffset)--start--cycle; + found=true; + // check if an inner curve is inside the portion + for(int k = 0; found && k < inners.length; ++k) + { + if(k!=curveIndex && + inside(portion,point(inners[k],0),zerowinding)) + found = false; + } + } + } + + if(!found) timeoffset=-2; + while(!found && timeoffset < -fuzz) { + timeoffset /= 2; + if(countIntersections(allCurves,start, + point(outer,endtime+timeoffset))==2) + { + portion = subpath(outer,endtime+timeoffset,endtime)--start--cycle; + found = true; + // check if an inner curve is inside the portion + for(int k = 0; found && k < inners.length; ++k) + { + if(k!=curveIndex && + inside(portion,point(inners[k],0),zerowinding)) + found = false; + } + } + } + assert(found); + endtime=min(endtime,endtime+timeoffset); + timeoffset=abs(timeoffset); + + // depends on the curves having opposite orientations + path remainder=section(outer,endtime+timeoffset,endtime) + --uncycle(inners[curveIndex], + starttime)--cycle; + inners.delete(curveIndex); + outer = remainder; + patch.append(portion); + } + result.append(outer); + } +} + +bool checkSegment(path g, pair p, pair q) +{ + pair mid=0.5*(p+q); + return intersections(p,q,g).length == 2 && + inside(g,mid,zerowinding) && intersections(g,mid).length == 0; +} + +path subdivide(path p) +{ + path q; + int l=length(p); + for(int i=0; i < l; ++i) + q=q&subpath(p,i,i+0.5)&subpath(p,i+0.5,i+1); + return cyclic(p) ? q&cycle : q; +} + +path[] bezulate(path[] p) +{ + if(p.length == 1 && length(p[0]) <= 4) return p; + path[] patch; + path[] result; + connect(p,result,patch); + for(int i=0; i < result.length; ++i) { + path p=result[i]; + int refinements=0; + if(size(p) <= 1) return p; + if(!cyclic(p)) + abort("path must be cyclic and nonselfintersecting."); + p=removeDuplicates(p); + if(length(p) > 4) { + static real SIZE_STEPS=10; + static real factor=1.05/SIZE_STEPS; + for(int k=1; k <= SIZE_STEPS; ++k) { + real L=factor*k*abs(max(p)-min(p)); + for(int i=0; length(p) > 4 && i < length(p); ++i) { + bool found=false; + pair start=point(p,i); + //look for quadrilaterals and triangles with one line, 4 | 3 curves + for(int desiredSides=4; !found && desiredSides >= 3; + --desiredSides) { + if(desiredSides == 3 && length(p) <= 3) + break; + pair end; + int endi=i+desiredSides-1; + end=point(p,endi); + found=checkSegment(p,start,end) && abs(end-start) < L; + if(found) { + path p1=subpath(p,endi,i+length(p))--cycle; + patch.append(subpath(p,i,endi)--cycle); + p=removeDuplicates(p1); + i=-1; // increment will make i be 0 + } + } + if(!found && k == SIZE_STEPS && length(p) > 4 && i == length(p)-1) { + // avoid infinite recursion + ++refinements; + if(refinements > mantissaBits) { + warning("subdivisions","too many subdivisions",position=true); + } else { + p=subdivide(p); + i=-1; + } + } + } + } + } + if(length(p) <= 4) + patch.append(p); + } + return patch; +} |