minimum bounding rectangle

Angol

Főnév

minimum bounding rectangle (tsz. minimum bounding rectangles)

(informatika) A minimum bounding rectangle (MBR), magyarul minimális befoglaló téglalap, egy olyan geometriai fogalom, amely egy adott alakzatot vagy ponthalmazt egy tengelyekkel párhuzamos téglalappal ölel körül úgy, hogy a téglalap területe a lehető legkisebb legyen. Az MBR nagyon gyakran használatos a számítógépes grafika, térinformatika (GIS), számítógépes látás, robotika és adatbázisok területén, ahol hatékonyan kell reprezentálni komplex alakzatokat, illetve gyorsan kell végezni geometriai lekérdezéseket.

1. Az MBR jelentősége és alkalmazásai

Az MBR leegyszerűsíti a bonyolult alakzatokat oly módon, hogy egy egyszerű téglalappal veszi körbe az alakzatot. Ezáltal:

Gyors határeset-ellenőrzést tesz lehetővé. Például két objektum ütközésvizsgálatát először az MBR-jeik alapján lehet gyorsan eldönteni.
Hatékony térbeli indexelést biztosít térinformatikai adatbázisokban, például R-fákban, ahol az adatok MBR-ek szerint rendeződnek.
Memória- és számítási igény csökkentése történik, mivel az alakzat pontos pontjai helyett csak négy koordinátát (a téglalap sarokpontjait) kell tárolni.
Vizualizáció és elemzés egyszerűsítése, például földrajzi területek approximálása.

2. MBR definíciója

Adott egy halmaz pont vagy egy geometriai alakzat a síkban. Az MBR egy olyan téglalap, amely:

Tengelyekkel párhuzamos (azaz oldalai párhuzamosak az x és y tengellyel).
Teljesen befoglalja az alakzatot.
Területe minimális a fentiek közül.

Matematikailag, ha adott pontok halmaza ${\textstyle P=\{(x_{i},y_{i})|i=1,\ldots ,n\}}$ , akkor az MBR-t az alábbi koordináták adják meg:

${\textstyle x_{min}=\min _{i}x_{i}}$
${\textstyle x_{max}=\max _{i}x_{i}}$
${\textstyle y_{min}=\min _{i}y_{i}}$
${\textstyle y_{max}=\max _{i}y_{i}}$

Az MBR tehát a négy pontból áll, amelyek:

$(x_{min},y_{min}),\quad (x_{min},y_{max}),\quad (x_{max},y_{max}),\quad (x_{max},y_{min})$

3. MBR kiszámítása

Az MBR meghatározásának legegyszerűbb módja a pontok ${\textstyle x}$ és ${\textstyle y}$ koordinátáinak minimum és maximum értékeinek meghatározása.

Algoritmus lépései:

Inicializáljuk ${\textstyle x_{min},x_{max}}$ az első pont ${\textstyle x}$ koordinátájával, és ${\textstyle y_{min},y_{max}}$ az első pont ${\textstyle y}$ koordinátájával.
Bejárjuk az összes pontot, frissítjük ${\textstyle x_{min},x_{max},y_{min},y_{max}}$ értékeket.
Az MBR a négy fent definiált pont lesz.

Ez egy ${\textstyle O(n)}$ komplexitású művelet, ahol ${\textstyle n}$ a pontok száma.

4. MBR és forgatott téglalapok

Az alapvető MBR tengelyekkel párhuzamos téglalap, de létezik a minimum bounding box (minimális befoglaló doboz) fogalma is, amely megengedi, hogy a téglalap bármilyen szögben álljon, nem csak tengelyekkel párhuzamosan.

Ez az általánosabb probléma jóval bonyolultabb, és a következőképpen oldható meg:

Először meghatározzuk az alakzat konvex burkát (convex hull).
A konvex burkon végigpásztázunk minden él mentén, és kiszámoljuk a téglalapot, amely arra az élre illeszkedik.
Kiválasztjuk a legkisebb területű ilyen téglalapot.

Ez az algoritmus a rotating calipers technikán alapul.

5. Használati példák

Térinformatika: Városrészek, folyók, épületek reprezentációja, ahol a komplex alakzatokat MBR-ekkel tárolják az adatbázisban gyors lekérdezésekhez.
Ütközésdetektálás: Videójátékokban vagy robotikában először az objektumok MBR-jeit vizsgálják, hogy kizárják az ütközés lehetőségét.
Kép- és alakzatelemzés: Objektek gyors körülhatárolása képfeldolgozásban.
Adatbázis indexelés: R-fák, amelyek a térbeli adatok hatékony indexeléséhez használják az MBR-eket.

6. Példa C++ kódrészlet az MBR meghatározására pontok halmazára

#include <vector>
#include <limits>
#include <iostream>

struct Pont {
    double x, y;
};

struct Teglalap {
    double xmin, xmax, ymin, ymax;
};

Teglalap mbr(const std::vector<Pont>& pontok) {
    if (pontok.empty()) throw std::runtime_error("Üres pontlista");

    double xmin = std::numeric_limits<double>::max();
    double xmax = std::numeric_limits<double>::lowest();
    double ymin = std::numeric_limits<double>::max();
    double ymax = std::numeric_limits<double>::lowest();

    for (const auto& p : pontok) {
        if (p.x < xmin) xmin = p.x;
        if (p.x > xmax) xmax = p.x;
        if (p.y < ymin) ymin = p.y;
        if (p.y > ymax) ymax = p.y;
    }

    return Teglalap{ xmin, xmax, ymin, ymax };
}

int main() {
    std::vector<Pont> pontok = { {1, 2}, {3, 5}, {0, 4}, {2, 1} };
    Teglalap box = mbr(pontok);
    std::cout << "MBR: xmin=" << box.xmin << ", xmax=" << box.xmax
              << ", ymin=" << box.ymin << ", ymax=" << box.ymax << std::endl;
    return 0;
}

7. Összefoglalás

A minimum bounding rectangle egy egyszerű, de nagyon hasznos geometriai eszköz, amely egy komplex alakzatot egy tengelyekkel párhuzamos téglalappal ír le, minimális területtel. Számos területen megkönnyíti a számításokat, gyorsítja az algoritmusokat, és jelentősen csökkenti a komplexitást. Míg a tengelyekkel párhuzamos MBR egyszerű és gyorsan kiszámítható, a forgatott minimális befoglaló téglalap még pontosabb körülhatárolást nyújt, de bonyolultabb számításokat igényel.

További információk

minimum bounding rectangle - Szótár.net (en-hu)
minimum bounding rectangle - Sztaki (en-hu)
minimum bounding rectangle - Merriam–Webster
minimum bounding rectangle - Cambridge
minimum bounding rectangle - WordNet
minimum bounding rectangle - Яндекс (en-ru)
minimum bounding rectangle - Google (en-hu)
minimum bounding rectangle - Wikidata
minimum bounding rectangle - Wikipédia (angol)