[Tex/LaTex] How one can draw a convex function
tikz-pgf
Related Solutions
With only TikZ but with functions.
Remark : I use samples=2
to draw the lines because two points are enough but for m
we need enough points to find the correct min values.
I use a part of the Jake's answer.
\documentclass{article}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[declare function={
f(\t)=tan(60)*\t+1.7;
g(\t)=tan(45)*\t+2.4;
h(\t)=tan(30)*\t+3.7;
i(\t)=tan(18)*\t+5.5;
m(\t)=min(f(\t) ,g(\t) ,h(\t),i(\t));}]
\draw[very thin,color=gray] (-0.1,-0.1) grid (10.1,10);
\draw[->] (-0.2,0) -- (10.2,0) node[right] {$x$};
\draw[->] (0,-0.2) -- (0,10.2) node[above] {$y$};
\clip (-1,-1) rectangle (10,10);
\foreach \func in {f,g,h,i}
\draw [blue, thin] plot [domain=0:10, samples=2] (\x,{\func(\x)});
\draw [red, thick] plot [domain=0:10, samples=100] (\x,{m(\x)});
\end{tikzpicture}
\end{document}
Robert Sedgewick's Algorithms in C has a whole chapter on convex hulls; here is the algorithm that he calls "package wrapping" implemented in Metapost.
prologues := 3;
outputtemplate := "%j%c.eps";
% following Sedgwick, "Algorithms in C", p.364
% make the first M points the hull of the first N points
vardef wrap(expr N) =
save theta, eta, tx, ty, M, m, a;
numeric theta, eta, tx, ty, M, m, a;
% find the point with the minimum y-coordinate
m = 1;
for i=2 upto N:
if y[i] < y[m]: m:=i; fi
endfor
x[N+1] = x[m];
y[N+1] = y[m];
% work round the points finding the least turning angle
% and swapping the hull points to the front of the list of points
theta := 0;
M = 1;
forever:
tx := x[M]; x[M] := x[m]; x[m] := tx;
ty := y[M]; y[M] := y[m]; y[m] := ty;
m := N+1;
eta := theta;
theta := 360;
for i=M+1 upto N+1:
a := if z[i]=z[M]: 0 else: angle (z[i]-z[M]) mod 360 fi;
if eta < a: if a < theta:
m := i;
theta := a;
fi fi
endfor
exitif (m=N+1);
M := M+1;
exitif (M>N);
endfor
% return the number of points in the hull
% z1, z2, .. z[M] are now the hull
M
enddef;
beginfig(1);
N = 42;
for i=1 upto N:
z[i] = (80 normaldeviate, 80 normaldeviate);
dotlabel.top(decimal i, z[i]);
endfor
m = wrap(N);
draw for i=1 upto m: z[i] -- endfor cycle withcolor .67 red;
for i=1 upto N:
label.bot(decimal i, z[i]) withcolor blue;
endfor
endfig;
end.
In the original you pass an array of points to the wrap
function, but passing arrays is a bit cumbersome in MP, so I've just used the normal global arrays x[]
and y[]
for the points. Note that the algorithm is destructive, in that it rearranges the order of the points so that the points on the hull are at the beginning of the array. I've tried to make this obvious by including before and after labels in the output.
This implementation has running time proportional to N^2
in the worst case, but is reasonably quick on my machine with up to 1200 points. You could speed it up with the interior elimination techniques that Sedgewick discusses in the chapter already mentioned.
Best Answer
A tikz solution