Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

MedieninformatikMedieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik

 

 

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 zusammensetzen.

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 Polygon­zug ist ein geschlossener Kantenzug

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

Ein Polygon­zug, 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 Polygon­zug.

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

Beispiel:  Bild 1 zeigt drei einfache Polygon­züge. Die Ecken sind durch dicke Punkte gekennzeichnet.

Einfache Polygonzüge
Bild 1:  Einfache Polygon­züge
Übung

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

Aufgabe 1:  Zeichnen Sie Polygon­zü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 Polygon­zuges und zum Testen der Eigenschaften des Polygon­zuges )

 

Fläche eines Polygons

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

Flächen unter den Kanten eines Polygonzugs
Bild 2:  Flächen unter den Kanten eines Polygon­zugs

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 Trapezflä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 Polygon­zug 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 Uhrzeigersinn durchlaufen, ist die Dreiecksfläche positiv, im anderen Fall negativ.

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 Polygon­zug 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 dargestellten Kanten eines Polygon­zugs bilden eine konvexe Ecke, die in Bild 4b dargestellten Kanten bilden eine konkave Ecke.

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

Um festzustellen, ob eine Ecke pi eines Polygon­zugs 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 Dreiecksfläche, so sind die Eckpunkte des Dreiecks entgegen dem Uhrzeigersinn nummeriert. In diesem Fall ist die Ecke konvex.

Wenn alle drei Punkte auf einer Geraden liegen, ist die Dreiecksflä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ächeninhalt des Dreiecks negativ, so sind die Eckpunkte des Dreiecks im Uhrzeigersinn nummeriert und die Ecke ist somit konkav.

Übung

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

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

Aufgabe 2:  Zeichnen Sie drei Polygon­zü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 Polygon­zuges 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) transformiert 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 tkreuzp; der Betrag dieses Wertes ist gleich dem doppelten Flächeninhalt des Dreiecks 0 t p. Diese Funktion wird als Hilfsfunktion 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 Voraussetzung, dass beide Punkte oberhalb der x-Achse liegen, ist dies ist genau dann der Fall, wenn die Punkte 0, t, p entgegen dem Uhrzeigersinn durchlaufen werden, der Flächeninhalt 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ächeninhalt 0 ist, aber t weiter vom Nullpunkt entfernt liegt als p.

Die Funktion area2(p0, p1) berechnet den doppelten Flächeninhalt des Dreiecks t p0 p1. Die Funktion area2(g) berechnet den doppelten Flächeninhalt eines Dreiecks, das durch die beiden Endpunkte g.p0 und g.p1 der Strecke g sowie den Punkt t gegeben ist. Ist der Flächeninhalt 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 Vektorprodukts oder Kreuzprodukts der beiden Ortsvektoren p1 und p2.

 

Weiter mit:   [Konvexe Hülle]   oder   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

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