在不规则多边形中查找多个矩形的算法

Question

我有一个由多条线组成的不规则多边形，如下所示：

我正在尝试找到可以在此多边形中看到的多个不同的大矩形，如下图所示：

我找不到能给我这个结果（或任何接近）的算法。我已经执行了BFS的修改版本以确定形状的边界/轮廓，但到目前为止它没有帮助很多。

我正在用C＃编写（但是任何可能有用的代码都会受到高度赞赏）。

Answer 1

我总是从最简单的算法开始，看看它是否符合我的性能预算。

此图中不能有超过几百个矩形，因此请枚举所有这些矩形。把它们放在一套。

现在形成该组中矩形的子集，这些矩形不完全位于原始集合中的另一个矩形内。

现在形成该集合的子集，其是特定最小面积/周长/任何的矩形。

而且你已经完成了。不要乱用搜索和遍历等等。你想找到一套中最重要的东西吗？列出所有这些并扔掉小的。

即使这个草图的天真实现也应该在顶点数量的O（n2）附近，这看起来非常小。您可以通过实现某种间隔树集合来做得更好，但这听起来很复杂且不必要;再次，看看最简单的方法是否在您的绩效预算中，如果是，请不要对其进行优化。花时间做别的事情。