包围矩形的最小面积？
我需要一个算法来解决以下问题（我已经尝试过一些个人的 解决方案，但它们似乎不是最佳的）
如果给定一个带有标记和未标记区域（以矩阵形式）和2个矩形的表面 您可以以任何形式或位置进行操作，找到可能的形状和位置 的矩形，使其覆盖所有标记区域，同时保持最小 可能的表面积。
I need an idea for an algorithm to solve the following problem (I already tried some personal
solutions but they don't seem to be optimal)
If given a surface with marked and unmarked zones (in matrix form), and 2 rectangles
that you can manipulate in any form or position, find the possible shape and position
of the rectangles such that they cover all the marked zones while keeping the minimum
surface area possible.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个答案假设您无法旋转矩形，并且边始终平行于 x 轴和 y 轴。
首先，找到包围整个区域的矩形。其算法如下（假设原点位于左上角）：
然后，找到最大的水平间隙，如下所示：
垂直间隙也是如此。然后检查哪个差距最大。
然后使用最大的间隙作为分隔符将包含所有的矩形分成两部分。最后一步是折叠两个矩形（使用与顶部算法相反的算法）。
This answer is assuming you can not rotate the rectangles and the sides are always parallel to the x and y axis.
First, find the rectangle that encloses the complete area. An algorithm for that goes like this (assuming the origin is at the topleft):
Then, find the largest horizontal gap like this:
Same goes for vertical gap. Then check which gap is the biggest.
Then divide the all-including rectangle in two parts using the biggest gap as seperator. The final step is to collapse the two rectangles (using the reverse of the algorithm on the top).