python - 查找具有最大表面积(不包括相交区域)的边界框轮廓

Question

我有一组来自对象检测系统的边界框。
它们的格式为:

[[x,y], [x,y], [x,y], [x,y]]

我想找到不与任何其他提供的框相交也不在排除框内的最大边界框。
我正在使用 python，但欢迎任何编程语言的响应:)
视觉示例

我如何尝试但未能解决这个问题。
方法一。
迭代每个点并找到 x 和 y 的最小值和最大值。
然后使用这些坐标裁剪为多边形。
问题是示例图像上的算法会删除图像的顶部，但没有必要，因为我们“错过”了左上角和右上角的框。
方法二。
尝试选择一次只裁剪一侧，因为通常在我的数据集中，要排除的内容位于一侧。例如删除前 100 像素
所以我像以前一样计算了 x 和 y 的最小值和最大值。
然后计算每个可能切割的面积 - 左、右、上、下，并选择面积最小的一个。
当图片左右两侧有框时，这种方法很快就失败了

Answer 1

考虑一个完整的重新调整(最初是整个图片)并去掉一个排除的框。您将获得 2x2x2x2=16 个可能的矩形分割，例如这个。

  ┌────────────────────────┐
  │                        │
  │                        │
  ├───────┬───────┬────────┤
  │       │  exc  │        │
  │       │ lude  │        │
  │       ├───────┴────────┤
  │       │                │
  │       │                │
  └───────┴────────────────┘

对于分割中的每个框，去掉下一个排除的框。
这样做N次，取最后一步最大的盒子。