mbr

空間資料庫中的應用

Minimum bounding rectangle (MBR) 最小外包矩形

在已知物體的邊界時,用其外接矩形的尺寸來刻畫它的基本形狀是最簡單的方法。

目錄

正文


如果僅計算其在坐標系方向上的外接矩形是最簡單的,只需計算物體邊界點的最大和最小坐標值,就可得到物體的水平和垂直跨度。但通常需要計算反映物體形狀特徵的主軸方向上的長度和與之垂直方向上的寬度,這樣的外接矩形是物體最小的外接矩形(MER-Minimum Enclosing Rectangle)。
計算MER的一種方法是將物體在90度範圍內等間隔地旋轉,每次記錄其坐標系方向上的外接矩形參數,取其面積為最小的矩形的參數為主軸意義下的長度和寬度。通常主軸可以通過矩(moments)的計算得到,也可以用求物體的最佳擬合直線的方法求出。
1、獲取幾何對象的最小外接矩形,並得到其面積值賦給變數AreaMin;
2、對幾何對象進行旋轉一個角度Φ,並求旋轉后的幾何對象的最小外接矩形,獲得其面積值賦給變數AreaTmp;
3、比較AreaTmp和AreaMin的大小,將小面積值賦給AreaMin,此時的角度值賦給一個公共變數;
4、循環執行第2、3步的過程,最終獲取一個最小的面積值以及與之相對應的旋轉角度;
5、得到了最合適的旋轉角度β后,我們可以將旋轉后的矩形反旋轉一個β角度,這樣就可以獲得我們需要的斜矩形了。
///////////////////////////////////////////////
GetRgnBox得到包含一個區域的最小的矩形;
判斷兩個區域的交集,一般是根據其中一個區域的邊界點是否在另一個區域內,利用PtInRegion來判斷.
GetRgnBox
The GetRgnBox function retrieves the bounding rectangle of the specified region.
int GetRgnBox(
HRGN hrgn, // handle to a region LPRECT lprc // bounding rectangle); Parametershrgn [in] Handle to the region. lprc [out] Pointer to a RECT structure that receives the bounding rectangle in logical units.
為了提高空間檢索效率,有兩個解決的途徑。首先,可以計算每個地物的MBR,這樣進行空間關係計算時,可以先通過外包矩形來判斷,可以排除掉根本不可能具有相交或者包含關係的情形,然後再按照常規的演演算法(如射線演演算法等等)進行計算。其次,考慮到採用MBR后,仍舊要計算每一個地物Ai,當地物數目很多時,依然需要較長的查找時間。解決該問題的一個方案是將資料庫的空間範圍進行分割,一般是劃分成為矩形,然後計算並記錄每個矩形包含或者相交的地物,形成空間索引。在進行空間檢索時,根據給定的點(或區域)得到其對應的索引塊,這樣就可以只判斷與索引塊相關的地物,從而減少了查找時間。通常前一個操作稱為精化,后一個操作叫做過濾。