壓縮矩形列表

Question

我有一個未排序的矩形列表（描述爲左下角和右上角座標對）。我正在尋找一種有效的算法來通過替換相鄰或重疊的bbox來壓縮此列表。

這裏是我的代碼，我沿垂直軸排序所有bbox，嘗試沿水平軸壓縮和排序結果並再次壓縮。這是不理想的，但速度不夠快。

(** boundingbox, (x0,y0) means left down, (x1,y1) right upper edge *) 
type bbox_t = { x0 : int; y0 : int; x1 : int; y1 : int; } 

let _test_if_compressable a b = 
    assert(a.x0 >= 0); 
    assert(a.y0 >= 0); 
    assert(b.x0 >= 0); 
    assert(b.y0 >= 0); 
    assert(a.x1 >= a.x0); 
    assert(a.y1 >= a.y0); 
    assert(b.x1 >= b.x0); 
    assert(b.y1 >= b.y0); 
    let same_x_ab = (a.x0 == b.x0) && (a.x1 == b.x1) in 
    let same_y_ab = (a.y0 == b.y0) && (a.y1 == b.y1) in 
    (same_x_ab && same_y_ab) || 
    (same_x_ab && (a.y1 >= (b.y0-1)) && (a.y0 <= b.y0)) || 
    (same_x_ab && (b.y1 >= (a.y0-1)) && (b.y0 <= a.y0)) || 
    (same_y_ab && (a.x1 >= (b.x0-1)) && (a.x0 <= b.x0)) || 
    (same_y_ab && (b.x1 >= (a.x0-1)) && (b.x0 <= a.x0)) 
;; 

(* compresses list of bboxes by joining bboxes of same dimension 
    * @param sort1 primary sorting function (hsort) 
    * @param sort2 secondary sorting function (vsort) 
    * @param bboxlst list of bboxes 
    * @return list of bboxes 
    *) 
let compress_bboxes sort1 sort2 bboxlst = 
    let rec compr lst newlst = 
    let _calc_new bbox1 bbox2 = 
     let miny = min bbox1.y0 bbox2.y0 
     and maxy = max bbox1.y1 bbox2.y1 
     and minx = min bbox1.x0 bbox2.x0 
     and maxx = max bbox1.x1 bbox2.x1 
     in 
     {x0=minx; y0=miny; x1=maxx; y1=maxy} 
    in 
     match lst with 
      [] -> List.rev newlst 
     | hd::[] -> List.rev (hd::newlst) 
     | hd1::hd2::tl when hd1 = hd2 -> compr tl (hd1::newlst) 
     | hd1::hd2::tl when _test_if_compressable hd1 hd2 -> let b = _calc_new hd1 hd2 in compr tl (b::newlst) 
     | hd1::hd2::tl -> 
      compr (hd2::tl) (hd1::newlst) 
    in 
    let newxlst = compr (sort1 bboxlst) [] in 
    let newylst = compr (sort2 newxlst) [] in 
    newylst 
;; 

另一種解決方案是一個貪婪的一個，但非常低：

let first_partition e lst = 
    let rec _first_partition accu = 
     function 
      [] -> None 
     | hd::tl when not (_test_if_compressable hd e) -> 
      _first_partition (hd::accu) tl 
     | hd::tl -> Some (hd, (List.rev_append accu tl)) 
    in 
     _first_partition [] lst 
    in 
    let rec _compr accu = 
    function 
     [] -> List.rev accu 
     | hd::tl -> 
      match (first_partition hd tl) with 
       None -> _compr (hd::accu) tl 
      | Some (c,r) -> let newbbox = get_surrounding_bbox [c;hd] in 
       _compr (newbbox::accu) r 
    in 
_compr [] lst (* call this repeately to improve compression *) 

你有更多的提示嗎？該算法不能完美壓縮，但應該快速並減小所得矩形（bbox）的大小。任何人都可以幫忙嗎？

Answer 1

我會考慮使用kd tree。基本上你可以建立一個二叉樹，在每個級別上你可以在一個點上分割飛機。無論你在x還是y方向分割，你都會交替。

如果您使用左下角座標作爲您的鍵，則給定節點中矩形可以包含的唯一矩形是右子樹中的矩形。

編輯：實際上這可能不會像那樣工作。矩形可能被左子樹中的矩形包含。

在我的午休期間，我做了一個kd樹的快速實施。它的運行時間與您的第一個功能相當，但似乎取得了更好的結果。我沒有檢查它的正確性（儘管我使用的是與你使用的相同的測試和壓縮代碼），但是在100000個隨機矩形上（x，y值從（0,0）到（99,99） ）kd樹方法將其壓縮到47539個矩陣，而排序列表方法將其減小到68393.kd樹稍慢，特別是對於較小的輸入（對於100個矩形，它花費的時間是兩倍，對於100,000，它只減慢了4％ ）。這裏是我的代碼：

type 'a kdtree = Empty | Node of 'a kdtree * 'a * 'a kdtree 

let rect_comp d a b = 
    if d mod 2 = 0 then 
     a.x0 < b.x0 
    else 
     a.y0 < b.y0 

let kd_of_list l = 
    let rec kdl n = function [] -> Empty 
    | h::t -> 
     let right, left = List.partition (rect_comp n h) t in 
     Node (kdl (n+1) left, h, kdl (n+1) right) 
    in 
    kdl 0 l 

let rec kd_compress boxes = 
    let rec compress elt rest = function [] -> elt::rest 
     | h::t when _test_if_compressable elt h -> let b = _calc_new elt h in compress b rest t 
     | h::t when h = elt -> compress elt rest t 
     | h::t -> h::(compress elt rest t) 
    in 
    match boxes with Empty -> [] 
    | Node (l, m, r) -> 
     let left = kd_compress l in 
     let right = kd_compress r in 
     (compress m left right) 

有一些明顯的改進空間（一兩件事，我使用分區的第一個元素，而不是中間元素的kd樹）