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