[Tex/LaTex] Compute and draw a convex hull

asymptotediagramsmetapostpstrickstikz-pgf

How can I use TikZ (+ LuaTeX), PSTricks, MetaPost, Asymptote, etc. to draw the convex hull of a set of points specified in no particular order?

Here's an example where the convex hull was computed by hand:

\documentclass[png]{standalone}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}
  % doesn't work:
  %\draw[mark=*] convex hull[points={(0,0),(1,1),(2,2),(0,1),(2,0)}];

  %should produce something similar to the following:
  \draw (0,0) -- (0,1) -- (2,2) -- (2,0) -- cycle;
  \foreach \point in {(0,0),(1,1),(2,2),(0,1),(2,0)} {
    \fill[black] \point circle[radius=1pt];
  }
\end{tikzpicture}
\end{document}

output

Best Answer

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.

enter image description here

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.

Related Solutions

[Tex/LaTex] 3d axis and polyhedron with line segment towards origin

\documentclass{article}
\usepackage[dvipsnames]{pstricks}
\usepackage{pst-solides3d}
\begin{document}

\begin{pspicture}[solidmemory,fontsize=20](-4,-4)(4,4)
\psset{Decran=30,viewpoint=20 40 30 rtp2xyz, lightsrc=viewpoint}
\psSolid[object=dodecahedron,a=2.5,action=draw*,name=my_dodecahedron,
         fillcolor=green!50!white]
\psSolid[object=point,definition=solidgetsommet,
  args=my_dodecahedron 0,linecolor=blue,text=A,pos=uc,name=A]
\psSolid[object=point,definition=solidgetsommet,
  args=my_dodecahedron 4,linecolor=blue,text=B,pos=uc,name=B]
\psSolid[object=line,args=A B,linecolor=blue]
\psSolid[object=vecteur,args=A,linecolor=blue]
\psSolid[object=vecteur,args=B,linecolor=blue]
\axesIIID(2.5,2.5,2.5)(3.5,3,3)
\end{pspicture}
%
\begin{pspicture}[solidmemory,fontsize=20](-4,-4)(4,4)
\psset{Decran=30,viewpoint=20 40 35 rtp2xyz, lightsrc=viewpoint}
\psSolid[object=dodecahedron,a=2.5,action=draw*,RotX=22.5,RotY=22.5,
  fillcolor=red!50!white,name=my_dodecahedron,action=draw**,
%  numfaces=all,num=all,
]
\psSolid[object=point,definition=solidcentreface,
   args=my_dodecahedron 2,linecolor=white,text=Centre face 2,pos=uc]
\psSolid[object=point,definition=solidgetsommet,
  args=my_dodecahedron 0,linecolor=white,text=A,pos=cl,name=A]
\psSolid[object=point,definition=solidgetsommet,
  args=my_dodecahedron 4,linecolor=white,text=B,pos=cl,name=B]
\psSolid[object=line,args=A B,linecolor=white]
\end{pspicture}

\end{document}

enter image description here

[Tex/LaTex] TikZ: Drawing an arc from an intersection to an intersection

A solution which allows to draw intersection segments of any two intersections is available as tikz library fillbetween.

This library works as general purpose tikz library, but it is shipped with pgfplots and you need to load pgfplots in order to make it work:

\documentclass{standalone}

\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{fillbetween}

\begin{document}

\begin{tikzpicture}

\draw [name path=red,red] (120:1.06) circle (1.9);
%\draw [name path=yellow,yellow] (0:1.06) circle (2.12);
\draw [name path=green,green!50!black] (0:0.77) circle (2.41);
\draw [name path=blue,blue] (0:0) circle (1.06);

% substitute this temp path by `\path` to make it invisible:
\draw[name path=temp1, intersection segments={of=red and blue,sequence=L1}];
\draw[red,-stealth,ultra thick, intersection segments={of=temp1 and green,sequence=L3}];

\end{tikzpicture}

\end{document}

enter image description here

The key intersection segments is described in all detail in the pgfplots reference manual section "5.6.6 Intersection Segment Recombination"; the key idea in this case is to

create a temporary path temp1 which is the first intersection segment of red and blue, more precisely, it is the first intersection segment in the Left argument in red and blue : red. This path is drawn as thin black path. Substitute its \draw statement by \path to make it invisible.
Compute the desired intersection segment by intersecting temp1 and green and use the correct intersection segment. By trial and error I figured that it is the third segment of path temp1 which is written as L3 (L = left argument in temp1 and green and 3 means third segment of that path).

The argument involves some trial and error because fillbetween is unaware of the fact that end and startpoint are connected -- and we as end users do not see start and end point.

Note that you can connect these path segments with other paths. If such an intersection segment should be the continuation of another path, use -- as before the first argument in sequence. This allows to fill paths segments:

\documentclass{standalone}

\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{fillbetween}

\begin{document}

\begin{tikzpicture}

\draw [name path=red,red] (120:1.06) circle (1.9);
%\draw [name path=yellow,yellow] (0:1.06) circle (2.12);
\draw [name path=green,green!50!black] (0:0.77) circle (2.41);
\draw [name path=blue,blue] (0:0) circle (1.06);

% substitute this temp path by `\path` to make it invisible:
\draw[name path=temp1, intersection segments={of=red and blue,sequence=L1}];
\draw[red,fill=blue,-stealth,ultra thick, intersection segments={of=temp1 and green,sequence=L3}]  
    [intersection segments={of=temp1 and green, sequence={--R2}}]
;

\end{tikzpicture}

\end{document}

enter image description here

Best Answer

Related Solutions

[Tex/LaTex] 3d axis and polyhedron with line segment towards origin

[Tex/LaTex] TikZ: Drawing an arc from an intersection to an intersection

Related Question