summaryrefslogtreecommitdiff
path: root/Master/texmf/asymptote/bezulate.asy
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2009-06-08 01:04:41 +0000
committerKarl Berry <karl@freefriends.org>2009-06-08 01:04:41 +0000
commitefda44c2e2e6bd08bf58ebdfb2f1879cff9e6f37 (patch)
tree105b5092688d84851b40816150f4a5c77df3ed08 /Master/texmf/asymptote/bezulate.asy
parent9e32dd6aee7faf4e59888cfbd7a927d497b563ad (diff)
first commit of asymptote binaries + support
git-svn-id: svn://tug.org/texlive/trunk@13665 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf/asymptote/bezulate.asy')
-rw-r--r--Master/texmf/asymptote/bezulate.asy261
1 files changed, 261 insertions, 0 deletions
diff --git a/Master/texmf/asymptote/bezulate.asy b/Master/texmf/asymptote/bezulate.asy
new file mode 100644
index 00000000000..01b3024f7b6
--- /dev/null
+++ b/Master/texmf/asymptote/bezulate.asy
@@ -0,0 +1,261 @@
+// Bezier triangulation routines written by Orest Shardt, 2008.
+
+private real fuzz=1e-6;
+real duplicateFuzz=1e-3; // Work around font errors.
+
+int countIntersections(path[] p, pair start, pair end)
+{
+ int intersects=0;
+ for(path q : p)
+ intersects += intersections(q,start--end,fuzz).length;
+ return intersects;
+}
+
+path[][] containmentTree(path[] paths)
+{
+ path[][] result;
+ for(int i=0; i < paths.length; ++i) {
+ bool classified=false;
+ // check if current curve contains or is contained in a group of curves
+ for(int j=0; !classified && j < result.length; ++j)
+ {
+ int test = inside(paths[i],result[j][0],zerowinding);
+ if(test == 1) // current curve contains group's toplevel curve
+ {
+ // replace toplevel curve with current curve
+ result[j].insert(0,paths[i]);
+ classified = true;
+ }
+ else if(test == -1) // current curve contained in group's toplevel curve
+ {
+ result[j].push(paths[i]);
+ classified = true;
+ }
+ }
+ // create a new group if this curve does not belong to another group
+ if(!classified)
+ result.push(new path[] {paths[i]});
+ }
+
+ // sort group so that later paths in the array are contained in previous paths
+ bool comparepaths(path i, path j) {return inside(i,j,zerowinding)==1;}
+ for(int i=0; i < result.length; ++i)
+ result[i] = sort(result[i],comparepaths);
+
+ 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
+ path line = start--start+d*direction;
+ real[][] ints=intersections(line,outer,fuzz);
+ assert(ints.length != 0);
+ real endtime=ints[0][1]; // endtime is time on outer
+ pair end = point(outer,endtime);
+ line = start--end;
+ path rline = reverse(line);
+
+ // find first intersection of rline segment 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(rline,inners[j],fuzz);
+ if(ints.length > 0 && ints[0][0] < earliestTime) {
+ earliestTime=ints[0][0]; // time on rline
+ starttime=ints[0][1]; // time on inner curve
+ curveIndex=j;
+ }
+ }
+ start=point(inners[curveIndex],starttime);
+ line = start--end;
+
+ 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);
+ }
+}
+
+int countIntersections(path g, pair p, pair q)
+{
+ int ints=0;
+ int l=length(g);
+ for(int i=1; i <= l; ++i)
+ ints += intersections(subpath(g,i-1,i),p--q,fuzz).length;
+ return ints;
+}
+
+bool checkSegment(path g, pair p, pair q)
+{
+ pair mid=0.5*(p+q);
+ return countIntersections(g,p,q) == 4 && 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) {
+ write("warning: too many subdivisions");
+ } else {
+ p=subdivide(p);
+ i=-1;
+ }
+ }
+ }
+ }
+ }
+ if(length(p) <= 4)
+ patch.append(p);
+ }
+ return patch;
+}