imported>Helium4: /* Repräsentation eines minimal umgebenden Rechtecks */Diagonale (Geometrie)

2023-05-27T09:13:44Z

Repräsentation eines minimal umgebenden Rechtecks: Diagonale (Geometrie)

Neue Seite

[[Datei:Minimum bounding rectangle.svg|thumb|MUR mehrerer Polygone]]

[[Bild:BoundingBox.jpg|thumb|Ein dreidimensionaler Körper und ein ihn minimal umgebender [[Quader]] (in weiß; rotiert)]]
Das '''minimal umgebende Rechteck''' (MUR) ([[Englische Sprache|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 [[Hyperrechteck|(Hyper-)Rechteck]]''.

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 [[Indexstruktur]]en (insbesondere im [[R-Baum]]), bei der [[Approximation]] von komplexen Objekten wie [[Polygon]]en und in der [[Computergrafik]] (siehe [[Bounding Volume]]) und in [[Geoinformationssystem]]en, 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 [[Diagonale (Geometrie)|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: <math>\textstyle \min_x</math>, <math>\textstyle \min_y</math>, <math>\textstyle \max_x</math>, <math>\textstyle \max_y</math> oder die zwei [[Tupel]] <math>\textstyle \min=(\min_x,\min_y)</math> (linke untere Ecke) und <math>\textstyle \max=(\max_x,\max_y)</math> (rechte obere Ecke).

Mathematisch gilt für ein MUR für alle Objekte <math>o</math> und Dimensionen <math>d</math>:
:<math>\forall o \forall d \quad \mbox{min}_d \leq o_d \leq \mbox{max}_d</math>
Wobei <math>\mbox{min}</math> der größte und <math>\mbox{max}</math> 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 <math>A \subseteq \operatorname{MUR}(A)</math> und die [[Monotone Abbildung|Monotonie]]
:<math>A \subseteq B \Rightarrow \operatorname{MUR}(A) \subseteq \operatorname{MUR(B)}</math>

In [[Suchbaum|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: <math>x \notin \operatorname{MUR}(A) \Rightarrow x \notin A</math>.
Die Monotonie erlaubt es, auch Anfragebereiche mittels ihres MUR abzuschätzen.

Sind <math>n</math> Objekte <math>A_i, i=1\dots n</math> gegeben, so gilt
:<math>\operatorname{MUR}\left(\bigcup_{i=1}^n A_i\right)=\operatorname{MUR}\left(\bigcup_{i=1}^n \operatorname{MUR}\left(A_i\right)\right)</math>

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 [[Konvexe Hülle|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 [[Geodaten|geographischen Daten]] wie [[Landkarte]]n überwiegen hier aber deutlich die Vorteile.

[[Kategorie:Datenstruktur]]
[[Kategorie:Algorithmische Geometrie]]
[[Kategorie:Geoinformatik]]

Minimal umgebendes Rechteck - Versionsgeschichte

imported>Helium4: /* Repräsentation eines minimal umgebenden Rechtecks */Diagonale (Geometrie)