real expansionfactor=sqrt(2); // A coordinate in "flex space." A linear combination of user and true-size // coordinates. struct coord { real user,truesize; // Build a coord. static coord build(real user, real truesize) { coord c=new coord; c.user=user; c.truesize=truesize; return c; } // Deep copy of coordinate. Users may add coords to the picture, but then // modify the struct. To prevent this from yielding unexpected results, deep // copying is used. coord copy() { return build(user, truesize); } void clip(real min, real max) { user=min(max(user,min),max); truesize=0; } } bool operator <= (coord a, coord b) { return a.user <= b.user && a.truesize <= b.truesize; } bool operator >= (coord a, coord b) { return a.user >= b.user && a.truesize >= b.truesize; } // Find the maximal elements of the input array, using the partial ordering // given. coord[] maxcoords(coord[] in, bool operator <= (coord,coord)) { // As operator <= is defined in the parameter list, it has a special // meaning in the body of the function. coord best; coord[] c; int n=in.length; if(n == 0) return c; int first=0; // Add the first coord without checking restrictions (as there are none). best=in[first]; c.push(best); static int NONE=-1; int dominator(coord x) { // This assumes it has already been checked against the best. for(int i=1; i < c.length; ++i) if(x <= c[i]) return i; return NONE; } void promote(int i) { // Swap with the top coord x=c[i]; c[i]=best; best=c[0]=x; } void addmaximal(coord x) { coord[] newc; // Check if it beats any others. for(int i=0; i < c.length; ++i) { coord y=c[i]; if(!(y <= x)) newc.push(y); } newc.push(x); c=newc; best=c[0]; } void add(coord x) { if(x <= best) return; else { int i=dominator(x); if(i == NONE) addmaximal(x); else promote(i); } } for(int i=1; i < n; ++i) add(in[i]); return c; } struct coords2 { coord[] x,y; void erase() { x.delete(); y.delete(); } // Only a shallow copy of the individual elements of x and y // is needed since, once entered, they are never modified. coords2 copy() { coords2 c=new coords2; c.x=copy(x); c.y=copy(y); return c; } void append(coords2 c) { x.append(c.x); y.append(c.y); } void push(pair user, pair truesize) { x.push(coord.build(user.x,truesize.x)); y.push(coord.build(user.y,truesize.y)); } void push(coord cx, coord cy) { x.push(cx); y.push(cy); } void push(transform t, coords2 c1, coords2 c2) { for(int i=0; i < c1.x.length; ++i) { coord cx=c1.x[i], cy=c2.y[i]; pair tinf=shiftless(t)*(0,0); pair z=t*(cx.user,cy.user); pair w=(cx.truesize,cy.truesize); w=length(w)*unit(shiftless(t)*w); coord Cx,Cy; Cx.user=z.x; Cy.user=z.y; Cx.truesize=w.x; Cy.truesize=w.y; push(Cx,Cy); } } void xclip(real min, real max) { for(int i=0; i < x.length; ++i) x[i].clip(min,max); } void yclip(real min, real max) { for(int i=0; i < y.length; ++i) y[i].clip(min,max); } } // The scaling in one dimension: x --> a*x + b struct scaling { real a,b; static scaling build(real a, real b) { scaling s=new scaling; s.a=a; s.b=b; return s; } real scale(real x) { return a*x+b; } real scale(coord c) { return scale(c.user) + c.truesize; } } // Calculate the minimum point in scaling the coords. real min(real m, scaling s, coord[] c) { for(int i=0; i < c.length; ++i) if(s.scale(c[i]) < m) m=s.scale(c[i]); return m; } // Calculate the maximum point in scaling the coords. real max(real M, scaling s, coord[] c) { for(int i=0; i < c.length; ++i) if(s.scale(c[i]) > M) M=s.scale(c[i]); return M; } /* Calculate the sizing constants for the given array and maximum size. Solve the two-variable linear programming problem using the simplex method. This problem is specialized in that the second variable, "b", does not have a non-negativity condition, and the first variable, "a", is the quantity being maximized. */ real calculateScaling(string dir, coord[] m, coord[] M, real size, bool warn=true) { from simplex2 access problem; problem p=new problem; void addMinCoord(coord c) { // (a*user + b) + truesize >= 0: p.addRestriction(c.user,1,c.truesize); } void addMaxCoord(coord c) { // (a*user + b) + truesize <= size: p.addRestriction(-c.user,-1,size-c.truesize); } for (int i=0; i < m.length; ++i) addMinCoord(m[i]); for (int i=0; i < M.length; ++i) addMaxCoord(M[i]); if(p.rows.length == 2) return 1; // Don't warn if there are no constraints int status=p.optimize(); if(status == problem.OPTIMAL) { // TODO: Could just be return a; return scaling.build(p.a(),p.b()).a; } else if(status == problem.UNBOUNDED) { if(warn) warning("unbounded",dir+" scaling in picture unbounded"); return 0; } else { if(!warn) return 1; bool userzero(coord[] coords) { for(var coord : coords) if(coord.user != 0) return false; return true; } if((userzero(m) && userzero(M)) || size >= infinity) return 1; warning("cannotfit","cannot fit picture to "+dir+"size "+(string) size +"...enlarging..."); return calculateScaling(dir,m,M,expansionfactor*size,warn); } } real calculateScaling(string dir, coord[] coords, real size, bool warn=true) { coord[] m=maxcoords(coords,operator >=); coord[] M=maxcoords(coords,operator <=); return calculateScaling(dir, m, M, size, warn); }