Scanline

Geschrieben von Benjamin Schmid.

Wie die Dynamische Programmierung ist Scanline ein Muster zum Algorithementwurf und nicht ein einziges Problem. Ein Beispiel für ein Problem, das mit Scanline gelöst werden kann, ist die konvexe Hülle. Wir werden hier jedoch ein einfacheres Problem betrachten, und an diesem die Funktionsweise von Scanline zeigen.

Beispielproblem

Wir betrachten einige achsenparalelle Rechtecke, die sich überlappen (z.B. der Querschnitt einer Stadt). Für jedes Rechteck soll nun die Länge des von oben sichtbaren Teils der oberen Kante bestimmt werden (im Beispiel der Stadt z.B. um die Regenmenge zu bestimmen).

Die naive Lösung dieses Problems wäre, für jedes Rechteck jedes andere Rechteck zu betrachten und dann die jeweils abgedeckten Bereiche abzuziehen. Damit aber Bereiche nicht doppelt abgezogen werden, müsste hierfür eine Liste mit bereits abgezogenen Bereichen gespeichert und durchsucht werden. Dies hat eine Laufzeit von \(O(n^3)\), doch es geht besser. Schauen wir uns hierfür nun an, wie Scanline funktioniert.

Algorithmus

Der Trick der Scanline ist nun, dass wir mit einer imaginären Linie über das Problem fahren und an interessanten Orten anhalten. An jedem dieser Haltepunkte wird nun eine oder mehrere geeignete Datenstrukturen aktualisiert. Wenn alle Haltepunkte abgearbeitet worden sind, kann aus den Datenstrukturen die Lösung bestimmt werden.

In den meisten Fällen ist die Linie horizontal oder vertikal und fährt dann entsprechend von oben nach unten bzw. von links nach rechts. Ebenfalls oft rotiert die Linie um einen Punkt (wie z.B. in manchen Implementationen für die konvexe Hülle).

Betrachten wir nun diese Methode an unserem Beispiel. Zuerst überlegen wir, in welche Richtung die Scanline verlaufen soll. Rotieren macht eher wenig Sinn, also wird es horizontal oder vertikal sein. Es ist beides möglich, doch wir werden die vertikale Linie wählen, da diese einfacher ist. In diesem Fall können wir jeweils zum aktuell zuoberst gelegen Rechteck (anhand der y-Koordinate der oberen Kante) die zurückgelegte Distanz hinzufügen. So haben wir am Ende für jedes Rechteck die gesuchte Länge aufaddiert.

Überlegen wir nun, was interessante Punkte sind. Während dem die Linie über ein Rechteck fährt, gibt es nichts zu tun. Es ändert sich nur etwas, wenn ein Rechteck beginnt oder aufhört. Wir wählen daher die linken und rechten Kanten als Haltepunkte. Um nun das bewegen der Linie zu simulieren, sortieren wir die Haltepunkte nach aufsteigender x-Koordinate und verarbeiten diese der Reihe nach. Beachte, dass wenn mehrere Punkte die selbe x-Koordinate haben können, du dir gut überlegen musst, welche du zuerst bearbeiten möchtest. In unserem Fall spielt es keine Rolle.

Als nächstes ist eine geeignete Datenstruktur gefragt. Dazu muss man sich fragen, was genau man jeweils an einem Haltepunkt bzw. am Ende wissen muss. In diesem Fall müssen wir am Ende für jedes Rechteck die sichtbare Länge wissen. Hierfür bietet sich ein Integer-Array an. An jedem Haltepunkt müssen wir das momentan oberste Rechteck wissen. So können wir die seit dem letzten Haltepunkt zurückgelegte Distanz zu diesem hinzufügen (da es das oberste ist, war es offensichtlich sichtbar). Da sich das oberste Rechteck zwischen den beiden Punkten nicht geändert haben kann (sonst hätte ja ein Rechteck anfangen oder aufhören müssen), addieren wir die Distanz zum richtigen Rechteck. Wir suchen also eine Datenstruktur, die uns erlaubt, schnell das oberste Element abzufragen, neue Elemente hinzuzufügen und zu entfernen. Hierfür eignet sich z.B. ein Heap [1] oder ein balancierter Baum. Dies musst du natürlich nicht selbst implementieren sondern kannst die Implementation in der C++ Standard Library verwenden: priority_queue für einen Heap, set für einen balancirten Baum.

Implementierung

#include <iostream> // cin / cout
#include <vector> // vector
#include <set> // set
#include <algorithm> // sort

using namespace std;

struct rect{
  // a rectangle defined by two opposite corners
  int x1, y1, x2, y2;
  int dist;
};

struct rectComp{
  // comparator for rects such that the top rect is first
  bool operator()(const rect* x, const rect* y) const {
    return x->y1 < y->y1;
  }
};

void scanline(vector<rect>& rects){
  vector<pair<int, rect*> > stopPoints;

  // create all stop points
  for(rect& r : rects){
    r.dist = 0;
    stopPoints.push_back({r.x1, &r}); // start of rect
    stopPoints.push_back({r.x2, &r}); // end of rect
  }

  sort(stopPoints.begin(), stopPoints.end());

  // datastructure to hold the top rect
  set<rect*, rectComp> topRect;
  int lastStop = stopPoints[0].first;

  // simulate scanline
  for(auto& stopPoint : stopPoints){
    // add distance to top rect
    if(topRect.size() > 0){
      (**topRect.begin()).dist += stopPoint.first - lastStop;
    }

    // update datastructure
    lastStop = stopPoint.first;
    if(stopPoint.first == stopPoint.second->x1){
      // start of rect
      topRect.insert(stopPoint.second);
    } else {
      // end of rect
      topRect.erase(stopPoint.second);
    }
  }

  // solution is now already saved in rect#dist
}

int main(){
  // read input
  int n; cin >> n;
  vector<rect> rects(n);
  for(int i = 0; i < n; i++){
    // assert x1 < x2 && y1 < y2
    cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
  }

  scanline(rects);

  for(rect& r : rects){
    cout << r.dist << " ";
  }
  cout << endl;
}

Laufzeitanalyse

Die Laufzeitanalyse besteht aus zwei Teilen. Zuerst muss bestimmt werden, wie viele Haltepunkte bearbeitet werden. In unserem Fall sind das \(O(n)\) Haltepunkte, für jedes Rechteck genau zwei. Anschliessend muss noch die Laufzeit pro Haltepunkt bestimmt werden. In diesem Beispiel wird die Distanz berechnet (\(O(1)\)), diese zum obersten Rechteck hinzugefügt (\(O(1)\)) sowie das Rechteck hinzugefügt (\(O(\log n)\)) oder entfernt (\(O(\log n)\)). Pro Haltepunkt benötigen wir also \(O(\log n)\). Somit ist die gesamte Laufzeit \(O(n \log n)\). Es ist jeweils zu beachten, dass das Sortieren der Haltepunkte ebenfalss \(O(n \log n)\) benötigt.

[1]Hinweis für Fortgeschrittene: Da ein Heap Entfernen nur für das Maximum unterstützt, müssen wir einen kleinen Trick anwenden: statt ein Rechteck sofort zu entfernen, überprüfen wir bei jeder Anfrage nach dem Maximum, ob das Rechteck noch “aktiv” ist. Falls nicht, entfernen wir es jetzt. Da jedes Rechteck genau einmal eingefügt und einmal entfernt wird, ändert sich die (ammortisierte) Laufzeit nicht.