相关疑难解决方法(0)

我有一组矩形,我想"减少"这个集合,所以我有最少的矩形来描述与原始集合相同的区域.如果可能的话,我希望它也快,但我更关心的是尽可能减少矩形的数量.我现在有一种方法,大部分时间都可以使用.

目前,我从最左上角的矩形开始,看看我是否可以在保持矩形的同时向右和向下展开它.我这样做,直到它不能再展开,删除并拆分所有相交的矩形,并在列表中添加展开的矩形.然后我再次使用下一个左上角的矩形开始该过程,依此类推.但在某些情况下,它不起作用.例如:

使用这组三个矩形,正确的解决方案最终会有两个矩形,如下所示:

但是,在这种情况下,我的算法从处理蓝色矩形开始.这会向下扩展并分割黄色矩形(正确).但是当处理黄色矩形的剩余部分时,它不是向下扩展,而是首先向右扩展并收回先前分离的部分.然后处理最后一个矩形,它不能向右或向下扩展,因此保留原始的矩形集.我可以调整算法,先向下扩展然后向右扩展.这将解决这种情况,但它会在翻转的类似场景中导致同样的问题.

编辑:只是为了澄清,原始的矩形集不重叠,不必连接.如果连接了矩形的子集,则完全覆盖它们的多边形可以在其中具有孔.

在使用 OpenCV 进行检测任务时，我一直遇到合并重叠边界框的问题；也就是说，本质上是在两个重叠边界框的并集​​周围找到边界框。当出于某种原因感兴趣的对象被分解为多个边界框，而不是一个包罗万象的边界框时，这在对象检测中会出现很多。

StackOverflow 上有一些关于算法解决方案和有用的外部库（例如this、this、this）的答案，还有groupRectanglesOpenCV 提供的函数（以及一连串相关问题/错误：this、this等）。

我似乎发现上述解决方案对于我尝试执行的任务来说有点过于复杂。许多算法解决方案从数学的角度解决了这个问题（更像是一个思想实验），而rect1 | rect2当矩形的数量很高（处理所有事情的时间是 O(N^2)）并且groupRectangles有一些使其仅部分有效的怪癖。所以我想出了一个有点骇人听闻的解决方案，它实际上非常有效。我想我会在下面分享给需要快速解决这个常见问题的其他人。

随意评论和批评它。