Konvexe Hülle

Polygon

 aufwärts

Grundlagen

Legt man ein Koordinaten­kreuz in die Zeichenebene, so ist jeder Punkt der Zeichenebene durch seinen x- und y-Wert bestimmt. Wir können also die Punkte der Ebene mit Paaren von reellen Zahlen gleichsetzen. Die Menge der Punkte der Ebene ist dann die Menge reelle Zahlen2. Die Menge reelle Zahlen2 bildet einen Vektorraum über reelle Zahlen.

Definition:  Ein Punkt in der Ebene ist ein Paar von reellen Zahlen, also ein Element p Element reelle Zahlen2 mit p = (x, y).

Geometrische Objekte wie Linien und Flächen sind Mengen von Punkten. Diese Punkte lassen sich durch Vektor­operationen beschreiben.

Definition:  Eine Gerade durch zwei Punkte p und q ist die Punktemenge

pq  =  { r Element reelle Zahlen2  |  r = p + a(q – p),  a Element reelle Zahlen }.

Ein Linien­segment ist die Verbindungs­strecke von zwei Punkten p und q:

pq  =  { r Element reelle Zahlen2  |  r = p + a(q – p),  a Element reelle Zahlen,  0kleiner gleichakleiner gleich1 }.

Wir lassen den Querstrich über pq auch weg, wenn klar ist, dass das Linien­segment zwischen p und q gemeint ist.

Aus Linien­segmenten lassen sich weitere geometrische Gebilde zusammen­setzen.

Definition:  Ein Kantenzug ist eine Kette von Linien­segmenten

w  =  p0p1p1p2, ...,  pn-1pn.

Die Punkte pi heißen Ecken des Kantenzugs, die Linien­segmente heißen Kanten.

Ein Polygonzug ist ein geschlossener Kantenzug

w  =  p0p1p1p2, ...,  pn-1p0.

Ein Polygonzug, bei dem alle Ecken pi verschieden sind und bei dem je zwei Kanten außer den gemeinsamen Ecken keine Punkte gemeinsam haben, heißt einfacher Polygonzug.

Das von einem einfachen Polygonzug umschlossene Gebiet, einschließ­lich des Polygonzugs selber, heißt Polygon.

Beispiel:  Bild 1 zeigt drei einfache Polygonzüge. Die Ecken sind durch dicke Punkte gekenn­zeichnet.

Bild 1: Einfache Polygonzüge
Bild 1: Einfache Polygonzüge
Übung

Mit folgendem Applet lassen sich Polygonzüge zeichnen (linke Maustaste: Ecken des Polygonzugs markieren, rechte Maustaste: abbrechen). Die Anzahl der Kanten ist auf maximal 20 begrenzt.

Aufgabe 1:  Zeichnen Sie Polygonzüge, die nicht einfach sind, weil sich (a) Kanten überlappen, (b) Kanten schneiden (c) Kanten berühren oder weil (d) Ecken mehrfach durchlaufen werden.

(Java-Applet zum Zeichnen eines Polygonzuges und zum Testen der Eigenschaften des Polygonzuges )

Fläche eines Polygons

Gegeben sei ein einfacher Polygonzug p0p1p1p2, ...,  pn-1p0. Die Ecken pi = (xi, yi) sind entgegen dem Uhrzeiger­sinn nummeriert, so dass die umschlossene Fläche stets links der Kanten pipi+1 liegt (Bild 2).

Bild 2: Flächen unter den Kanten eines Polygonzugs
Bild 2: Flächen unter den Kanten eines Polygonzugs

Die Fläche des Trapezes unter der Kante p0p1 berechnet sich als

A0,1  =  (x0 – x1) (y0 + y1) / 2.

Entsprechend berechnen sich auch die Flächen unter den anderen Kanten. Im Beispiel von Bild 2 ergibt sich für A3,4 eine negative Fläche, da x3<x4 ist.

Addiert man alle Trapez­flächen A0,1, ..., An-1,0, so heben sich die unterhalb des Polygons liegenden positiven und negativen Flächen auf und es ergibt sich die von dem Polygonzug umschlossene Fläche A:

A  =   Summe i = 0, ..., n-1  Ai,i+1.

Hierbei wird i+1 modulo n gerechnet.

Fläche eines Dreiecks

Die Flächen­berechnung gestaltet sich besonders einfach, wenn sie auf ein Dreieck mit den Eckpunkten p0, p1, p2 angewendet wird, dessen Eckpunkt p0 im Nullpunkt liegt (Bild 3). Dann gilt für die doppelte Fläche F des Dreiecks 1)

2F  =  x1y2 – x2y1.

Wichtig ist die Orientierung der Eckpunkte p0, p1 und p2. Werden die Punkte in dieser Reihenfolge entgegen dem Uhrzeiger­sinn durchlaufen, ist die Dreiecks­fläche positiv, im anderen Fall negativ.

Bild 3: Dreieck mit p0 im Nullpunkt
Bild 3: Dreieck mit p0 im Nullpunkt

Die Fläche eines beliebigen Dreiecks ergibt sich, indem die Punkte p1 und p2 relativ zu p0 als Nullpunkt dargestellt werden und dann die obige Berechnung ausgeführt wird.

Konvexe und konkave Ecken

Definition:  Eine Ecke pi in einem Polygonzug p0p1p1p2, ...,  pn-1p0 heißt konvex, wenn für den links liegenden Winkel α zwischen den Kanten pi-1pi und pipi+1 gilt 0° kleiner gleich α < 180° (i-1 und i+1 werden modulo n gerechnet). Anderenfalls heißt die Ecke konkav.

Die in Bild 4a dar­gestellten Kanten eines Polygonzugs bilden eine konvexe Ecke, die in Bild 4b dar­gestellten Kanten bilden eine konkave Ecke.

Bild 4: Konvexe Ecke eines Polygonzugs (a), konkave Ecke (b)
Bild 4: Konvexe Ecke eines Polygonzugs (a), konkave Ecke (b)

Um fest­zustellen, ob eine Ecke pi eines Polygonzugs konvex oder konkav ist, berechnet man mit der oben angegebenen Methode die Fläche des Dreiecks pi-1pipi+1. Ergibt die Flächen­berechnung eine positive Dreiecks­fläche, so sind die Eckpunkte des Dreiecks entgegen dem Uhrzeiger­sinn nummeriert. In diesem Fall ist die Ecke konvex.

Wenn alle drei Punkte auf einer Geraden liegen, ist die Dreiecks­fläche 0. Dann wird geprüft, ob die Ecke neben oder zwischen den beiden anderen Punkten liegt. Liegt sie neben den beiden anderen Punkten, ist der Winkel 0° und die Ecke damit konvex. Liegt sie zwischen den beiden anderen Punkten, ist der Winkel 180° und die Ecke damit konkav.

Ist der Flächen­inhalt des Dreiecks negativ, so sind die Eckpunkte des Dreiecks im Uhrzeiger­sinn nummeriert und die Ecke ist somit konkav.

Übung

Ein einfacher Polygonzug, der nur konvexe Ecken hat, umschließt ein konvexes Polygon.

Mit folgendem Applet lassen sich Polygonzüge, konvexe Polygone und Polygonzüge mit aus­schließ­lich konvexen Ecken zeichnen (linke Maustaste: Ecken des Polygonzugs markieren, rechte Maustaste: abbrechen). Die Anzahl der Kanten ist auf maximal 20 begrenzt.

Aufgabe 2:  Zeichnen Sie drei Polygonzüge, die nur konvexe Ecken haben, die aber nicht einfach sind, und zwar weil (a) sich Kanten überlappen, (b) sich Kanten schneiden und (c) eine Ecke mehrfach durchlaufen wird.

(Java-Applet zum Zeichnen eines Polygonzuges mit ausschließlich konvexen Ecken)

Implementierung

Die folgende Klasse Point modelliert einen Punkt in der Ebene. Die Klasse enthält bereits eine ganze Reihe von Methoden, die für die Berechnung der konvexen Hülle einer Menge von Punkten benötigt werden. Im Folgenden sei t der aktuelle Punkt (this), mit dem die jeweiligen Methoden aufgerufen werden.

Die Funktion relTo(p) erzeugt einen neuen Punkt, der t relativ zum Punkt p als Nullpunkt darstellt. Die Funktion makeRelTo(p) trans­formiert t entsprechend. Die Funktionen moved(x0, y0) und reversed() erzeugen einen zu t verschobenen Punkt bzw. einen zu t am Nullpunkt gespiegelten Punkt.

Die Funktion isLower(p) gibt true zurück, wenn t eine kleinere y-Koordinate als p hat, oder, bei gleicher y-Koordinate, eine kleinere x-Koordinate.

Die Funktion isFurther(p) prüft, ob t weiter vom Nullpunkt entfernt liegt als p. Als Maß für die Entfernung vom Nullpunkt genügt hier der Manhattan-Abstand |x| + |y|. Die Funktion mdist() berechnet den Manhattan-Abstand von t zum Nullpunkt.

Die Funktion isBetween(p0, p1) prüft im Falle dass t, p0 und p1 auf einer Linie liegen, ob t zwischen p0 und p1 liegt.

Die Funktion cross(p) berechnet das Kreuzprodukt t × p; der Betrag dieses Wertes ist gleich dem doppelten Flächen­inhalt des Dreiecks 0 t p. Diese Funktion wird als Hilfs­funktion mehrfach verwendet.

In der Funktion isLess(p) wird geprüft, ob der Ortsvektor von t einen kleineren Winkel zum Nullpunkt hat als der Ortsvektor eines Punktes p. Unter der Voraus­setzung, dass beide Punkte oberhalb der x-Achse liegen, ist dies ist genau dann der Fall, wenn die Punkte 0, t, p entgegen dem Uhrzeiger­sinn durchlaufen werden, der Flächen­inhalt des Dreiecks 0 t p also positiv ist. Die Funktion isLess(p) gibt in diesem Fall true zurück, und außerdem auch dann, wenn der Flächen­inhalt 0 ist, aber t weiter vom Nullpunkt entfernt liegt als p.

Die Funktion area2(p0, p1) berechnet den doppelten Flächen­inhalt des Dreiecks t p0 p1. Die Funktion area2(g) berechnet den doppelten Flächen­inhalt eines Dreiecks, das durch die beiden Endpunkte g.p0 und g.p1 der Strecke g sowie den Punkt t gegeben ist. Ist der Flächen­inhalt negativ, so liegt der Punkt t rechts von der Geraden g. Dies wird in der Funktion isRightOf(g) verwendet.

Die Funktion isConvex(p0, p1) prüft, ob die Ecke p0 t p1 konvex ist.

public class Point
{
    public double x, y;

    public Point(double x, double y)
    {
        this.x=x;
        this.y=y;
    }

    public Point(Point p)
    {
        this(p.x, p.y);
    }

    public Point relTo(Point p)
    {
        return new Point(x-p.x, y-p.y);
    }

    public void makeRelTo(Point p)
    {
        x-=p.x;
        y-=p.y;
    }

    public Point moved(double x0, double y0)
    {
        return new Point(x+x0, y+y0);
    }

    public Point reversed()
    {
        return new Point(-x, -y);
    }

    public boolean isLower(Point p)
    {
        return y<p.y || y==p.y && x<p.x;
    }

    public double mdist()   // Manhattan-Distanz
    {
        return Math.abs(x)+Math.abs(y);
    }

    public double mdist(Point p)
    {
        return relTo(p).mdist();
    }

    public boolean isFurther(Point p)
    {
        return mdist()>p.mdist();
    }

    public boolean isBetween(Point p0, Point p1)
    {
        return p0.mdist(p1)>=mdist(p0)+mdist(p1);
    }

    public double cross(Point p)
    {
        return x*p.y-p.x*y;
    }

    public boolean isLess(Point p)
    {
        double f=cross(p);
        return f>0 || f==0 && isFurther(p);
    }

    public double area2(Point p0, Point p1)
    {
        return p0.relTo(this).cross(p1.relTo(this));
    }

    public double area2(Line g)
    {
        return area2(g.p0, g.p1);
    }

    public boolean isRightOf(Line g)
    {
        return area2(g)<0;
    }

    public boolean isConvex(Point p0, Point p1)
    {
        double f=area2(p0, p1);
        return f<0 || f==0 && !isBetween(p0, p1);
    }

}    // end class Point

1)  Der Betrag von 2F entspricht dem Betrag des Vektor­produkts oder Kreuz­produkts der beiden Ortsvektoren p1 und p2.

 

Weiter mit:   [Konvexe Hülle]   oder   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 25.12.2002   Updated: 05.07.2015
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik