function Q=ConvexHull(P)
% function Q=ConvexHull(P)
%
% konvexe Huelle einer Punktmenge in der Ebene
%
% Input:  P ... (2xn)-Matrix der Punkte
% Output: Q ... (2,m)-Matrix der Punkte die die konvexe Huelle aufspannen
%

% Written by Joachim Wipper
% Modified by Joachim Gaukel, November 1998
%

n=length(P(:,1));       %Anzahl der Punkte
help=min(P(:,2));       %Startpunkt=Pkt mit kleinster y-Koordinate
glyk=find(P(:,2)==help);
[buffer,hilf]=min(P(glyk,1));
Q=glyk(hilf);           
aktPkt=Q(1);     
%-----
% So jetzt haben wir als Startpunkt den Punkt mit der kleinsten y-Koordinate
% Und wenn es mehrere Punkte mit kleinster y-Koordinate gibt, dann haben wir
% unter diesen denjenigen mit der kleinsten x-Koordinate.
%-----
wmin=0;                 
%-----
% Im Fall, dass es mehrere Punkte mit kleinster y-Koordinate gibt, muss der
% naechste Punkt der sein der unter diesen die groesste x-Koordinate besitzt
%-----
if length(glyk)>1
  [buffer,hilf]=max(P(glyk,1));
  Q(2)=glyk(hilf);
  aktPkt=Q(2);
end;

% 2.Fall verhindert Abbruch beim 1.Schleifendurchlauf
while aktPkt~=Q(1) | length(Q)==1
  R=P-ones(n,1)*P(aktPkt,:);  %Richtungsvektoren zu allen anderen Punkten
  w=atan2(R(:,2),R(:,1));     %Winkel der Richtungsvektoren
  w(w<0)=2*pi+w(w<0);         %shift [-pi,pi]->[0,2pi]
  w=w+(w<=wmin)*2*pi;         %Es kann nur mit Winkel > wmin weitergehen
  [wmin,hilf]=min(w);         %Minimalen Winkel bestimmen
  glWi=find(w==wmin);         %falls es >1 solche Punkte mit min. Winkel gibt
                              %diese Punkte finden und den mit dem max. Abstand
			      %zum letzten Punkt als naechsten nehmen
  [buffer,hilf]=max(R(glWi,1).*R(glWi,1)+R(glWi,2).*R(glWi,2));
  aktPkt=glWi(hilf);
  Q=[Q,aktPkt];               %Punkt in Liste aufnehmen
end;
Q=P(Q(1:length(Q)-1),:);                     %Umwandlung Indexvektor Q zu Punktmatrix Q