Minimal umgebendes Rechteck

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Ein dreidimensionaler Körper und ein ihn minimal umgebender Quader (in weiß; rotiert)

Das minimal umgebende Rechteck (MUR) (Englisch: minimum bounding rectangle, MBR, auch bounding box und envelope) bezeichnet das kleinstmögliche achsenparallele Rechteck, das eine vorgegebene Menge von Objekten umschließt. Auch wenn der Begriff scheinbar eine Zweidimensionalität impliziert, so spricht man auch in anderen Dimensionen von einem minimal umgebenden (Hyper-)Rechteck.

Mathematisch gesehen handelt es sich um einen sehr einfachen Hüllenoperator über n-dimensionalen Intervallen (Quadern).

Der Begriff kommt aus der Informatik und findet dort Anwendung unter anderem bei der Datenspeicherung in Indexstrukturen (insbesondere im R-Baum), bei der Approximation von komplexen Objekten wie Polygonen und in der Computergrafik (siehe Bounding Volume) und in Geoinformationssystemen, da für Computer Rechtecke schneller zu verarbeiten sind als komplexe Objekte.

Während in der Computergrafik auch rotierte Rechtecke als „bounding box“ auftreten können, so werden im Allgemeinen nur achsenparallele Quader als MBR zugelassen.

Repräsentation eines minimal umgebenden Rechtecks[Bearbeiten]

Ein minimal umgebendes Rechteck ist repräsentierbar durch das Minimum und Maximum in jeder einzelnen Dimension. Diese Werte können als zwei Vektoren interpretiert und gespeichert werden, einem Minimums-Vektor und einem Maximums-Vektor. Interpretiert man diese beiden Vektoren geometrisch, so sind sie zwei gegenüberliegende Ecken des MURs. Man sagt dazu auch, dass diese beiden Punkte das MUR „aufspannen“.

Im zweidimensionalen Fall sind dies also vier Werte: \textstyle \min_x, \textstyle \min_y, \textstyle \max_x, \textstyle \max_y oder die zwei Tupel \textstyle \min=(\min_x,\min_y) (linke untere Ecke) und \textstyle \max=(\max_x,\max_y) (rechte obere Ecke).

Mathematisch gilt für ein MUR für alle Objekte o und Dimensionen d:

\forall o \forall d \quad \mbox{min}_d \leq o_d \leq \mbox{max}_d

Wobei \mbox{min} der größte und \mbox{max} der kleinste Vektor mit dieser Eigenschaft sind, es also kein kleineres Rechteck mit dieser Eigenschaft gibt.

Extensivität und Monotonie[Bearbeiten]

Als Hüllenoperator verfügen MUR über wichtige Eigenschaften zur Verwendung in Algorithmen. Wichtig sind vor allem die Extensivität A \subseteq \operatorname{MUR}(A) und die Monotonie

A \subseteq B \Rightarrow \operatorname{MUR}(A) \subseteq \operatorname{MUR(B)}

In Suchbäumen wie dem R-Baum, werden sie zur Effizienzsteigerung verwendet. Hier erlaubt es die Extensivität, ganze Teilbäume bei der Suche auszuschließen anhand des MUR des Teilbaumes: x \notin \operatorname{MUR}(A) \Rightarrow x \notin A. Die Monotonie erlaubt es, auch Anfragebereiche mittels ihres MUR abzuschätzen.

Sind n Objekte A_i, i=1\dots n gegeben, so gilt

\operatorname{MUR}\left(\bigcup_{i=1}^n A_i\right)=\operatorname{MUR}\left(\bigcup_{i=1}^n \operatorname{MUR}\left(A_i\right)\right)

Das exakte MUR eines Objektes kann also alleine anhand der MURs von Teilobjekten berechnet werden.

Approximation mittels minimal umgebenden Rechtecks[Bearbeiten]

Ausgedehnte Objekte wie Polygone können durch ihr MUR angenähert gespeichert werden. Der Vorteil der Verwendung von MURs gegenüber beispielsweise der konvexen Hülle eines Objekte ist der wesentlich geringere Speicheraufwand und die schnellere Berechnung von Überlappungen. Diese Vorteile erkauft man sich mit einer geringen Genauigkeit der Approximation. Insbesondere auf geographischen Daten wie Landkarten überwiegen hier aber deutlich die Vorteile.