2.5 Jarvis' March

Geschichte und Idee

• 1973 von Ray A. Jarvis entwickelt.
• Bekannt als „Gift Wrapping“ (Geschenkpapier-Methode).

Idee: Man wickelt eine Schnur um die Punktmenge, bis sie mit der konvexen Hülle übereinstimmt. Man hält die Schnur an einem sicheren Hüllpunkt fest und dreht sie, bis sie an einen Punkt stößt. Das ist die nächste Ecke. Von dort weiter, bis man wieder am Anfang ist.

Unterschied zu Graham: Graham verarbeitet alle Eingabepunkte nacheinander. Jarvis erzeugt direkt die Ausgabe, eine Hüllecke nach der anderen. Pro Ecke wird einmal über alle Punkte gesucht.

Startpunkt

Wie bei Graham's Scan startet man mit dem lexikographisch kleinsten Punkt. Der liegt garantiert auf der Hülle.

Bei Jarvis legt die Folie fest: zuerst kleinste $y$-Koordinate, dann kleinste $x$-Koordinate, also der unterste Punkt, bei Gleichstand der linkeste davon.

Warum liegt er sicher auf der Hülle? Kein Punkt liegt tiefer, also ist die waagrechte Gerade durch ihn eine Stützgerade. Unter den Punkten auf dieser Geraden ist er der linkeste, also ein Endpunkt und damit eine echte Ecke (kein Zwischenpunkt einer Kante).

Ausgabe: Jarvis' March berechnet die „extremen“ Punkte der Hülle gegen den Uhrzeigersinn (anders als Graham auf den Folien).

Algorithmus (Folie 20)

 1  Polygon JarvisMarch(Points P)
 2  {
 3      Finde lexikographisch kleinsten Punkt p1;
 4      q1 = p1;
 5      i = 2;
 6      qi = Endpunkt der Strecke p1 qi mit kleinstem Winkel
            zur Horizontalen durch p1;
 7      repeat {
 8          i++;
 9          qi = Endpunkt der Strecke q(i-1) qi mit kleinstem Winkel
                zur Strecke q(i-2) q(i-1) in q(i-1);
10      } until (qi == p1);
11      Füge alle Punkte q1,...,qk in eine Liste L ein;
12      return L;
13  }

Zeile für Zeile:

Zeile	Bedeutung
3–4	Startpunkt $q_1=p_1$ (unterster, dann linkester)
6	Erster Schritt: Es gibt noch keine vorige Kante, also misst man den Winkel zur Horizontalen durch $p_1$ (nach rechts). Der Punkt mit dem kleinsten Winkel ist die nächste Ecke $q_2$, also die Schnur, die von rechts kommend als erste einen Punkt trifft
9	Allgemeiner Schritt: Verlängere die letzte Kante $\overline{q_{i-2}q_{i-1}}$ über $q_{i-1}$ hinaus. Der Punkt mit dem kleinsten Winkel zu dieser Verlängerung ist $q_i$, die Schnur dreht sich um $q_{i-1}$ gegen den Uhrzeigersinn, bis sie anstößt
10	Ende, sobald man wieder bei $p_1$ ankommt. Die Hülle ist geschlossen

Interaktiv durchspielen: Die Schnur dreht sich um die aktuelle Ecke (Ring). Gestrichelt ist der aktuelle Kandidat, rot schattiert seine rechte Seite. Liegt dort ein Punkt, wird er neuer Kandidat. ⏩ springt zur nächsten Ecke.

Schritt 1/62: Start bei p5: kleinstes y, bei Gleichstand kleinstes x – liegt sicher auf der Hülle.

langsamnormalschnellsehr schnell

Klicken: hinzufügen · Ziehen: verschieben · Rechtsklick: löschen

bisherige Hülleaktueller Kandidatrechte Seite (muss leer sein)besserer Kandidat

Kleinster Winkel = Orientierungstest (Ergänzung)

Wörtlich Winkel zu berechnen (atan2, acos) ist teuer und fehleranfällig. Es geht äquivalent ohne Winkel:

Von der aktuellen Ecke $p$ aus ist $r$ ein besserer Kandidat als $q$, wenn $r$ rechts von $\vec{pq}$ liegt, also $\operatorname{orient}(p,q,r)<0$.

Warum? Liegt $r$ rechts von $\vec{pq}$, muss sich die Schnur (die gegen den Uhrzeigersinn dreht) zuerst an $r$ anlegen, bevor sie $q$ erreicht. $r$ hat also den kleineren Winkel.

Damit wird jeder Schritt zu einer Maximumsuche mit dem Orientierungstest als Vergleich:

q = irgendein Punkt ≠ p
for alle Punkte r ≠ p:
    if (r liegt rechts von pq) q = r

Am Ende liegt kein Punkt mehr rechts von $\vec{pq}$, also liegen alle links oder darauf. Nach dem Kantenkriterium (hier gegen den Uhrzeigersinn, also „alles links“) ist $\overline{pq}$ eine Hüllkante. Die vorige Kante muss man sich dafür gar nicht merken.

Durchgerechnetes Beispiel

Punkte: $A(0,0)$, $B(1,2)$, $C(2,1)$, $D(3,3)$, $E(4,0)$, dieselben wie bei Graham.

1. Start: kleinstes $y=0$ haben A und E. Davon das kleinste $x$: A.
2. Von A: Welcher Punkt hat alle anderen links? E, denn $\vec{AE}$ läuft entlang der $x$-Achse und alle anderen Punkte haben $y>0$. → E
3. Von E: Kandidat D. Prüfung: orient(E,D,A) $=(-1)(0)-(3)(-4)=12>0$, orient(E,D,B) $=(-1)(2)-(3)(-3)=7>0$, orient(E,D,C) $=(-1)(1)-(3)(-2)=5>0$. Alle liegen links. → D
4. Von D: → B (A, C, E liegen links von $\vec{DB}$)
5. Von B: → A = Startpunkt, Ende.

Ergebnis: A → E → D → B, gegen den Uhrzeigersinn. Das sind dieselben Ecken wie bei Graham (A B D E), nur andersherum. ✔

Aufwand: $h=4$ Ecken, je ein Durchlauf über $n=5$ Punkte.

Dasselbe Beispiel zum Nachklicken (um $(5,2)$ verschoben):

Schritt 1/22: Start bei A: kleinstes y, bei Gleichstand kleinstes x – liegt sicher auf der Hülle.

langsamnormalschnellsehr schnell

Klicken: hinzufügen · Ziehen: verschieben · Rechtsklick: löschen

bisherige Hülleaktueller Kandidatrechte Seite (muss leer sein)besserer Kandidat

Laufzeit (Folie 21)

Sei $h$ die Anzahl der Ecken der konvexen Hülle.

• Eine Ecke $q_i$ zu berechnen kostet $O(n)$: Der kleinste Winkel wird nur mit Arithmetik und Vergleichen über alle Punkte bestimmt.
• Es gibt $h$ Ecken.

$\Rightarrow\quad \text{Gesamtlaufzeit } O(h\cdot n).$

Fall	$h$	Laufzeit	Vergleich zu Graham
Hülle ist Dreieck / Viereck	konstant	$O(n)$	besser
Zufallspunkte im Quadrat	erwartet $O(\log n)$	$O(n\log n)$	gleich
Alle Punkte auf einem Kreis	$n$	$O(n^2)$	viel schlechter

• Für kleines $h$ ist der Algorithmus sehr effizient.
• Für großes $h$ ist er ineffizient, denn seine Worst-Case-Laufzeit ist $O(n^2)$.
• Ein solches Verhalten heißt output-sensitiv: Die Laufzeit hängt von der Größe der Ausgabe ab.

Faustregel: Jarvis schlägt Graham, wenn $h<\log n$.

Frage der Folie: Welche Komplexität haben output-sensitive Hüllen-Algorithmen? Antwort im nächsten Abschnitt: $\Theta(n\log h)$.

Sonderfälle (Ergänzung)

Fall	Problem	Lösung
Mehrere Punkte mit kleinstem $y$	Ein Start auf einem Zwischenpunkt der unteren Kante wäre keine Ecke	bei Gleichstand kleinstes $x$ (so auf der Folie)
Kollineare Kandidaten ($\operatorname{orient}=0$)	Zwischenpunkte auf einer Kante würden als Ecken ausgegeben, oder die Suche springt hin und her	bei Gleichstand den weiter entfernten Punkt nehmen
Doppelte Punkte	Duplikat von $p$ hat Abstand 0 und ist kollinear mit allem	vorher entfernen
Rundungsfehler	Start wird evtl. nie wieder erreicht, Endlosschleife	zusätzlich abbrechen, wenn mehr als $n$ Ecken gefunden wurden
$n\le2$	kein Polygon	direkt zurückgeben

In C++ (Ergänzung)

Umsetzung von Folie 20 mit Orientierungstest statt Winkel

double dist2(const PointF& a, const PointF& b)
{
    const double dx = b.x - a.x, dy = b.y - a.y;
    return dx * dx + dy * dy;
}

std::vector<PointF> jarvisMarch(std::vector<PointF> P)
{
    std::sort(P.begin(), P.end(), lexLess);                          // nur fürs Entfernen von Duplikaten
    P.erase(std::unique(P.begin(), P.end(), samePoint), P.end());
    const size_t n = P.size();
    if (n < 3) return P;

    size_t start = 0;                                                // Zeile 3: kleinstes y, dann kleinstes x
    for (size_t i = 1; i < n; ++i)
        if (P[i].y < P[start].y || (P[i].y == P[start].y && P[i].x < P[start].x))
            start = i;

    std::vector<PointF> hull;
    size_t p = start;
    do {                                                             // Zeilen 7–10
        hull.push_back(P[p]);
        size_t q = (p + 1) % n;
        for (size_t r = 0; r < n; ++r) {
            if (r == p) continue;
            const double o = orient(P[p], P[q], P[r]);
            if (o < 0 || (o == 0 && dist2(P[p], P[r]) > dist2(P[p], P[q])))
                q = r;                                               // r hat kleineren Winkel
        }
        p = q;
    } while (p != start && hull.size() <= n);
    return hull;                                                     // gegen den Uhrzeigersinn
}

(orient, lexLess, samePoint wie bei Graham's Scan.)

Graham vs. Jarvis

	Graham's Scan	Jarvis' March
Prinzip	Sweep / inkrementell	Gift Wrapping
Vorverarbeitung	Sortieren	keine
Laufzeit	$O(n\log n)$ immer	$O(h\cdot n)$
Worst Case	$O(n\log n)$, optimal	$O(n^2)$
output-sensitiv	nein	ja
Ausgabe (Folien)	im Uhrzeigersinn ab $p_1$ (links)	gegen den Uhrzeigersinn ab $p_1$ (unten)
Startpunkt	kleinstes $x$, dann $y$	kleinstes $y$, dann $x$