Minimal umgebendes Rechteck

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.

Ein dreidimensionaler Körper und ein ihn minimal umgebender Quader (in weiß; rotiert)

Mathematisch gesehen handelt es sich um einen sehr einfachen Hüllenoperator. Dafür muss man auch die gesamte Ebene als Grenzfall eines Rechtecks zulassen.

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

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 diagonal bzw. raumdiagonal 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

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

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