Berechung der konvexen Hülle

Die Berechnung der konvexen Hülle einer Punktmenge kann komplett auf die Betrachtung von Vorzeichen entsprechender Determinanten zurückgeführt werden. Liegen keine drei Punkte auf einer Geraden, so gehört ein von zwei Punkten aufgespanntes Segment zur konvexen Hülle, wenn alle weiteren Punkte auf der gleiche Seite des Segmentes liegen. Diese Entscheidung kann aber komplett durch Vorzeichen-Betrachtungen getroffen werden.

Das folgende Applet zeigt die Berechnung der konvexen Hülle einer Punktmenge. Exemplarisch wurde ein Punktepaar herausgegriffen und die Punkte jenseits und diesseits der von ihnen aufgespannten Geraden rot bzw. grün gefärbt. Ist eine dieser beiden Teilmengen leer, so liegt die Kante in der konvexen Hülle.

Der Programmcode zum Bestimmen der zur konvexen Hülle gehörigen Segmente lässt sich z.B. wie folgt definieren:

eps=0.0001;

leftfrom(seg):=
   length(select(pts,area(#,seg_1,seg_2)>eps));
rightfrom(seg):=
   length(select(pts,area(#,seg_1,seg_2)<-eps));

pts=allpoints();
segs=pairs(pts);
hull=select(segs,or(leftfrom(#)==0, rightfrom(#)==0));

forall(hull,draw(#_1,#_2));