Algorithmus für den Treffertest in nicht überlappenden Rechtecken

StackOverflow https://stackoverflow.com/questions/97762

  •  01-07-2019
  •  | 
  •  

Frage

Ich habe eine Sammlung nicht überlappender Rechtecke, die ein umschließendes Rechteck abdecken. Was ist der beste Weg, um das enthaltende Rechteck für einen Mausklick zu finden?

Die offensichtliche Antwort ist, eine Reihe von Rechtecken zu haben und sie nacheinander zu durchsuchen, wodurch die Suche o (n) durchgeführt wird. Gibt es eine Möglichkeit, sie nach Position zu bestellen, damit der Algorithmus weniger als O (n) ist, beispielsweise O (log n) oder o (SQRT (n))?

War es hilfreich?

Lösung

Sie können Ihre Rechtecke in einem Quad- oder KD-Baum organisieren. Das gibt dir o (log n). Das ist die Mainstream -Methode.

Eine weitere interessante Datenstruktur für dieses Problem sind R-Bäume. Diese können sehr effizient sein, wenn Sie sich mit vielen Rechtecken befassen müssen.

http://en.wikipedia.org/wiki/r- tree

Und dann gibt es die O (1) -Methode, um einfach eine Bitmap auf der gleichen Größe wie Ihr Bildschirm zu erzeugen, sie mit einem Platzhalter für "kein Rechteck" zu füllen und die Hit-Rectangle-Indizes in diese Bitmap zu zeichnen. Eine Suche wird so einfach wie:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

Offensichtlich funktioniert diese Methode nur gut, wenn sich Ihre Rechtecke nicht so oft ändern und wenn Sie den Speicher für die Bitmap ersparen können.

Andere Tipps

Erstellen Sie einen Intervallbaum. Fragen Sie den Intervallbaum ab. Wenden Sie sich an 'Algorithmen' von MIT Press.

Ein Intervallbaum wird am besten als rotschwarzer Baum implementiert.

Denken Sie daran, dass es nur ratsam ist, Ihre Rechtecke zu sortieren, wenn Sie mehr auf sie klicken, dann ändern Sie ihre Positionen normalerweise.

Sie müssen berücksichtigen, dass Sie Ihre Indizes für verschiedene Achse separat erstellen lassen. ZB, Sie müssen sehen, ob Sie ein Intervall auf x und auf Y überlappen. Eine offensichtliche Optimierung besteht darin, nur auf Überlappungen eines einzelnen X -Intervalls zu überprüfen.

Außerdem prüfen die meisten Aktien- oder Klassenbuch-Intervallbäume nur nach einem einzigen Intervall und geben nur ein einzelnes Intervall zurück (Sie sagten jedoch "nicht überlappend", oder?)

Schiebe sie in einen Quadtree.

Verwenden ein BSP Baum, um die Rechtecke zu speichern.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top