压缩矩形列表

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 树。基本上，您构建了一个二叉树，在每个级别上将平面分割在一个点上。您可以交替沿 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 树进行分区）