1real legendlinelength=50;
2real legendhskip=1.2;
3real legendvskip=legendhskip;
4real legendmargin=10;
5real legendmaxrelativewidth=1;
6
7// Return a unit polygon with n sides.
8path polygon(int n)
9{
10  guide g;
11  for(int i=0; i < n; ++i) g=g--expi(2pi*(i+0.5)/n-0.5*pi);
12  return g--cycle;
13}
14
15// Return a unit n-point cyclic cross, with optional inner radius r and
16// end rounding.
17path cross(int n, bool round=true, real r=0)
18{
19  assert(n > 1);
20  real r=min(r,1);
21  real theta=pi/n;
22  real s=sin(theta);
23  real c=cos(theta);
24  pair z=(c,s);
25  transform mirror=reflect(0,z);
26  pair p1=(r,0);
27  path elementary;
28  if(round) {
29    pair e1=p1+z*max(1-r*(s+c),0);
30    elementary=p1--e1..(c,s)..mirror*e1--mirror*p1;
31  } else {
32    pair p2=p1+z*(max(sqrt(1-(r*s)^2)-r*c),0);
33    elementary=p1--p2--mirror*p2--mirror*p1;
34  }
35
36  guide g;
37  real step=360/n;
38  for(int i=0; i < n; ++i)
39    g=g--rotate(i*step-90)*elementary;
40
41  return g--cycle;
42}
43
44path[] plus=(-1,0)--(1,0)^^(0,-1)--(0,1);
45
46typedef void markroutine(picture pic=currentpicture, frame f, path g);
47
48// On picture pic, add frame f about every node of path g.
49void marknodes(picture pic=currentpicture, frame f, path g) {
50  for(int i=0; i < size(g); ++i)
51    add(pic,f,point(g,i));
52}
53
54// On picture pic, add n copies of frame f to path g, evenly spaced in
55// arclength.
56// If rotated=true, the frame will be rotated by the angle of the tangent
57// to the path at the points where the frame will be added.
58// If centered is true, center the frames within n evenly spaced arclength
59// intervals.
60markroutine markuniform(bool centered=false, int n, bool rotated=false) {
61  return new void(picture pic=currentpicture, frame f, path g) {
62    if(n <= 0) return;
63    void add(real x) {
64      real t=reltime(g,x);
65      add(pic,rotated ? rotate(degrees(dir(g,t)))*f : f,point(g,t));
66    }
67    if(centered) {
68      real width=1/n;
69      for(int i=0; i < n; ++i) add((i+0.5)*width);
70    } else {
71      if(n == 1) add(0.5);
72      else {
73        real width=1/(n-1);
74        for(int i=0; i < n; ++i)
75          add(i*width);
76      }
77    }
78  };
79}
80
81// On picture pic, add frame f at points z(t) for n evenly spaced values of
82// t in [a,b].
83markroutine markuniform(pair z(real t), real a, real b, int n)
84{
85  return new void(picture pic=currentpicture, frame f, path) {
86    real width=b-a;
87    for(int i=0; i <= n; ++i) {
88      add(pic,f,z(a+i/n*width));
89    }
90  };
91}
92
93struct marker {
94  frame f;
95  bool above=true;
96  markroutine markroutine=marknodes;
97  void mark(picture pic=currentpicture, path g) {
98    markroutine(pic,f,g);
99  };
100}
101
102marker marker(frame f=newframe, markroutine markroutine=marknodes,
103              bool above=true)
104{
105  marker m=new marker;
106  m.f=f;
107  m.above=above;
108  m.markroutine=markroutine;
109  return m;
110}
111
112marker marker(path[] g, markroutine markroutine=marknodes, pen p=currentpen,
113              filltype filltype=NoFill, bool above=true)
114{
115  frame f;
116  filltype.fill(f,g,p);
117  return marker(f,markroutine,above);
118}
119
120// On picture pic, add path g with opacity thinning about every node.
121marker markthin(path g, pen p=currentpen,
122                real thin(real fraction)=new real(real x) {return x^2;},
123                filltype filltype=NoFill) {
124  marker M=new marker;
125  M.above=true;
126  filltype.fill(M.f,g,p);
127  real factor=1/abs(size(M.f));
128  M.markroutine=new void(picture pic=currentpicture, frame, path G) {
129    transform t=pic.calculateTransform();
130    int n=size(G);
131    for(int i=0; i < n; ++i) {
132      pair z=point(G,i);
133      frame f;
134      real fraction=1;
135      if(i > 0) fraction=min(fraction,abs(t*(z-point(G,i-1)))*factor);
136      if(i < n-1) fraction=min(fraction,abs(t*(point(G,i+1)-z))*factor);
137      filltype.fill(f,g,p+opacity(thin(fraction)));
138      add(pic,f,point(G,i));
139    }
140  };
141  return M;
142}
143
144marker nomarker;
145
146real circlescale=0.85;
147
148path[] MarkPath={scale(circlescale)*unitcircle,
149                 polygon(3),polygon(4),polygon(5),invert*polygon(3),
150                 cross(4),cross(6)};
151
152marker[] Mark=sequence(new marker(int i) {return marker(MarkPath[i]);},
153                       MarkPath.length);
154
155marker[] MarkFill=sequence(new marker(int i) {return marker(MarkPath[i],Fill);},
156                           MarkPath.length-2);
157
158marker Mark(int n)
159{
160  n=n % (Mark.length+MarkFill.length);
161  if(n < Mark.length) return Mark[n];
162  else return MarkFill[n-Mark.length];
163}
164
165picture legenditem(Legend legenditem, real linelength)
166{
167  picture pic;
168  pair z1=(0,0);
169  pair z2=z1+(linelength,0);
170  if(!legenditem.above && !empty(legenditem.mark))
171    marknodes(pic,legenditem.mark,interp(z1,z2,0.5));
172  if(linelength > 0)
173    Draw(pic,z1--z2,legenditem.p);
174  if(legenditem.above && !empty(legenditem.mark))
175    marknodes(pic,legenditem.mark,interp(z1,z2,0.5));
176  if(legenditem.plabel != invisible)
177    label(pic,legenditem.label,z2,E,legenditem.plabel);
178  else
179    label(pic,legenditem.label,z2,E,currentpen);
180  return pic;
181}
182
183picture legend(Legend[] Legend, int perline=1, real linelength,
184               real hskip, real vskip, real maxwidth=0, real maxheight=0,
185               bool hstretch=false, bool vstretch=false)
186{
187  if(maxwidth <= 0) hstretch=false;
188  if(maxheight <= 0) vstretch=false;
189  if(Legend.length <= 1) vstretch=hstretch=false;
190
191  picture inset;
192  size(inset,0,0,IgnoreAspect);
193
194  if(Legend.length == 0)
195    return inset;
196
197  // Check for legend entries with lines:
198  bool bLineEntriesAvailable=false;
199  for(int i=0; i < Legend.length; ++i) {
200    if(Legend[i].p != invisible) {
201      bLineEntriesAvailable=true;
202      break;
203    }
204  }
205
206  real markersize=0;
207  for(int i=0; i < Legend.length; ++i)
208    markersize=max(markersize,size(Legend[i].mark).x);
209
210  // If no legend has a line, set the line length to zero
211  if(!bLineEntriesAvailable)
212    linelength=0;
213
214  linelength=max(linelength,markersize*(linelength == 0 ? 1 : 2));
215
216  // Get the maximum dimensions per legend entry;
217  // calculate line length for a one-line legend
218  real heightPerEntry=0;
219  real widthPerEntry=0;
220  real totalwidth=0;
221  for(int i=0; i < Legend.length; ++i) {
222    picture pic=legenditem(Legend[i],linelength);
223    pair lambda=size(pic);
224    heightPerEntry=max(heightPerEntry,lambda.y);
225    widthPerEntry=max(widthPerEntry,lambda.x);
226    if(Legend[i].p != invisible)
227      totalwidth += lambda.x;
228    else {
229      // Legend entries without leading line need less space in one-line legends
230      picture pic=legenditem(Legend[i],0);
231      totalwidth += size(pic).x;
232    }
233  }
234  // Does everything fit into one line?
235  if(((perline < 1) || (perline >= Legend.length)) &&
236     (maxwidth >= totalwidth+(totalwidth/Legend.length)*
237      (Legend.length-1)*(hskip-1))) {
238    // One-line legend
239    real currPosX=0;
240    real itemDistance;
241    if(hstretch)
242      itemDistance=(maxwidth-totalwidth)/(Legend.length-1);
243    else
244      itemDistance=(totalwidth/Legend.length)*(hskip-1);
245    for(int i=0; i < Legend.length; ++i) {
246      picture pic=legenditem(Legend[i],
247                             Legend[i].p == invisible ? 0 : linelength);
248      add(inset,pic,(currPosX,0));
249      currPosX += size(pic).x+itemDistance;
250    }
251  } else {
252    // multiline legend
253    if(maxwidth > 0) {
254      int maxperline=floor(maxwidth/(widthPerEntry*hskip));
255      if((perline < 1) || (perline > maxperline))
256        perline=maxperline;
257    }
258    if(perline < 1) // This means: maxwidth < widthPerEntry
259      perline=1;
260
261    if(perline <= 1) hstretch=false;
262    if(hstretch) hskip=(maxwidth/widthPerEntry-perline)/(perline-1)+1;
263    if(vstretch) {
264      int rows=ceil(Legend.length/perline);
265      vskip=(maxheight/heightPerEntry-rows)/(rows-1)+1;
266    }
267
268    if(hstretch && (perline == 1)) {
269      Draw(inset,(0,0)--(maxwidth,0),invisible());
270      for(int i=0; i < Legend.length; ++i)
271        add(inset,legenditem(Legend[i],linelength),
272            (0.5*(maxwidth-widthPerEntry),
273             -quotient(i,perline)*heightPerEntry*vskip));
274    } else
275      for(int i=0; i < Legend.length; ++i)
276        add(inset,legenditem(Legend[i],linelength),
277            ((i%perline)*widthPerEntry*hskip,
278             -quotient(i,perline)*heightPerEntry*vskip));
279  }
280
281  return inset;
282}
283
284frame legend(picture pic=currentpicture, int perline=1,
285             real xmargin=legendmargin, real ymargin=xmargin,
286             real linelength=legendlinelength,
287             real hskip=legendhskip, real vskip=legendvskip,
288             real maxwidth=perline == 0 ?
289             legendmaxrelativewidth*size(pic).x : 0, real maxheight=0,
290	     bool hstretch=false, bool vstretch=false, pen p=currentpen)
291{
292  frame F;
293  if(pic.legend.length == 0) return F;
294  F=legend(pic.legend,perline,linelength,hskip,vskip,
295           max(maxwidth-2xmargin,0),
296           max(maxheight-2ymargin,0),
297           hstretch,vstretch).fit();
298  box(F,xmargin,ymargin,p);
299  return F;
300}
301
302pair[] pairs(real[] x, real[] y)
303{
304  if(x.length != y.length) abort("arrays have different lengths");
305  return sequence(new pair(int i) {return (x[i],y[i]);},x.length);
306}
307
308filltype dotfilltype = Fill;
309
310void dot(frame f, pair z, pen p=currentpen, filltype filltype=dotfilltype)
311{
312  if(filltype == Fill)
313    draw(f,z,dotsize(p)+p);
314  else {
315    real s=0.5*(dotsize(p)-linewidth(p));
316    if(s <= 0) return;
317    path g=shift(z)*scale(s)*unitcircle;
318    begingroup(f);
319    filltype.fill(f,g,p);
320    draw(f,g,p);
321    endgroup(f);
322  }
323}
324
325void dot(picture pic=currentpicture, pair z, pen p=currentpen,
326         filltype filltype=dotfilltype)
327{
328  pic.add(new void(frame f, transform t) {
329      dot(f,t*z,p,filltype);
330    },true);
331  pic.addPoint(z,dotsize(p)+p);
332}
333
334void dot(picture pic=currentpicture, Label L, pair z, align align=NoAlign,
335         string format=defaultformat, pen p=currentpen, filltype filltype=dotfilltype)
336{
337  Label L=L.copy();
338  L.position(z);
339  if(L.s == "") {
340    if(format == "") format=defaultformat;
341    L.s="("+format(format,z.x)+","+format(format,z.y)+")";
342  }
343  L.align(align,E);
344  L.p(p);
345  dot(pic,z,p,filltype);
346  add(pic,L);
347}
348
349void dot(picture pic=currentpicture, Label[] L=new Label[], pair[] z,
350	 align align=NoAlign, string format=defaultformat, pen p=currentpen,
351	 filltype filltype=dotfilltype)
352{
353  int stop=min(L.length,z.length);
354  for(int i=0; i < stop; ++i)
355    dot(pic,L[i],z[i],align,format,p,filltype);
356  for(int i=stop; i < z.length; ++i)
357    dot(pic,z[i],p,filltype);
358}
359
360void dot(picture pic=currentpicture, Label[] L=new Label[],
361	 explicit path g, align align=RightSide, string format=defaultformat,
362	 pen p=currentpen, filltype filltype=dotfilltype)
363{
364  int n=size(g);
365  int stop=min(L.length,n);
366  for(int i=0; i < stop; ++i)
367    dot(pic,L[i],point(g,i),-sgn(align.dir.x)*I*dir(g,i),format,p,filltype);
368  for(int i=stop; i < n; ++i)
369    dot(pic,point(g,i),p,filltype);
370}
371
372void dot(picture pic=currentpicture, path[] g, pen p=currentpen,
373         filltype filltype=dotfilltype)
374{
375  for(int i=0; i < g.length; ++i)
376    dot(pic,g[i],p,filltype);
377}
378
379void dot(picture pic=currentpicture, Label L, pen p=currentpen,
380         filltype filltype=dotfilltype)
381{
382  dot(pic,L,L.position,p,filltype);
383}
384
385// A dot in a frame.
386frame dotframe(pen p=currentpen, filltype filltype=dotfilltype)
387{
388  frame f;
389  dot(f,(0,0),p,filltype);
390  return f;
391}
392
393frame dotframe=dotframe();
394
395marker dot(pen p=currentpen, filltype filltype=dotfilltype)
396{
397  return marker(dotframe(p,filltype));
398}
399
400marker dot=dot();
401
402