idz*_*idz 11
通常,您使用所谓的扫描线算法来解决这些问题.在您的案例候选矩形中,他们一次检查一行(或扫描线)的数据,构建您正在寻找的答案.
这是一个如何工作的大致轮廓.
将图像中的所有行编号为0..6,我将从下往上工作.
检查第0行,你有两个矩形的开头(我假设你只对黑色方块感兴趣).我将使用(x,y,width,height)来引用矩形.两个活动矩形是(1,0,2,1)和(4,0,6,1).您将这些添加到活动矩形列表中.此列表按增加x坐标排序.
您现在已完成扫描线0,因此您可以增加扫描线.
检查第1行,您将看到行是否有以下任何一项:
- 新的活动矩形
- 现有矩形生长的空间
- 分裂现有矩形的障碍物
- 需要您从活动列表中删除矩形的障碍物
当您沿着该行工作时,您将看到您有一个新的活动矩形(0,1,8,1),我们可以将现有的一个活动矩阵增长到(1,0,2,2),我们需要删除有效(4,0,6,1)用两个较窄的替换它.我们需要记住这个.这是我们迄今为止看到的最大规模.它被两个新的活动替换:(4,0,4,2)和(9,0,1,2)
因此,在发送扫描线1时,我们有:
- 活动清单:(0,1,8,1),(1,0,2,2),(4,0,4,2),(9,0,1,2)
- 迄今为止最大的:(4,0,6,1)
您将继续这种方式,直到扫描线用完为止.
棘手的部分是编写沿扫描线运行的例程来更新活动列表.如果你做得正确,你只会考虑每个像素一次.
希望这可以帮助.描述有点棘手.
我喜欢这个区域增长的方法.
- 对于ARRAY中的每个开放点
- 尽可能地长出东方
- 尽可能地发展西部
- 通过添加行尽可能地增长NORTH
- 通过添加行尽可能地扩展SOUTH
- 保存所用种子像素的结果区域
- 循环遍历ARRAY中的每个点后,选择具有最大区域结果的种子像素
...将是一个彻底但可能不是最有效的方法.
我想你需要回答一个哲学问题"点线是一个瘦的矩形吗？" 如果一行==一个细长矩形,您可以进一步优化:
- 创建第二个名为LINES的整数数组,其大小与ARRAY相同
- 循环遍历ARRAY中的每个点
- 确定从每个点开始的EAST的最长有效行,并将其长度保存在LINES的相应单元格中.
- 在为ARRAY中的每个点执行此操作后,循环通过LINES
- 对于LINES中的每个点,确定有多少邻居SOUTH具有相同的长度值或更少.
- 接受长度较小的SOUTHERN邻居,如果这样做会增加矩形的面积.
- 使用该种子点的最大矩形是(Number_of_acceptable_southern_neighbors*the_length_of_longest_accepted_line)
- 计算每个种子的最大矩形区域时,检查是否有新的最大值并保存结果.
- 并且......你可以在不分配数组LINES的情况下做到这一点,但我认为在我的解释中使用它会使描述更简单.
- 并且...我认为你需要使用VERTICAL_LINES和EASTERN_NEIGHBORS做同样的事情,或者某些情况下可能会错过高而瘦的大矩形.所以也许第二种算法毕竟不是那么优化的.
使用第一种方法检查您的工作.我认为Knuth说"......过早的优化是所有邪恶的根源."
HTH,
佩里
附录:稍后进行了几次编辑,我认为这个答案值得一组投票.