3

我的数学不是很好，所以我很难将公式转换为代码，而且我找不到任何现成的谷歌搜索。我有一个包含很多小矩形的大矩形......我需要做的就是计算最大的空矩形。任何人都可以帮助我吗？

这是我想出的……没什么好说的，这是一个很大的失败。

Rect result = new Rect();

for (Double l = 0; l < bigRect.Width; ++l)
{
    for (Double t = 0; t < bigRect.Height; ++t)
    {
        Double h = 0;
        Double w = 0;

        while ((h <= bigRect.Width) && (w <= bigRect.Height))
        {
            Rect largestEmpty = new Rect(l, t, w, h);

            if (smallRects.TrueForAll(smallRect => !smallRect.IntersectsWith(largestEmpty)) && ((largestEmpty.Height * largestEmpty.Width) > (result.Height * result.Width)))
                result = largestEmpty;
            else
                break;

            ++h;
            ++w;
        }
    }
}
4

1 回答 1

0

来自您的Perdue 文档链接它说在 Big Rect 中有一组点（我们称之为 ASD），你会找到不包含集合 ASD 的点的最大 Rect。查看您的代码，您似乎没有（直接）合并这些要点。我会从较小的 Rects 中提取点并创建集 ASD。由于您使用的是 double 类型，因此您应该可以访问这些点，否则该算法的运行时间会显着增加，因为您需要检查特定范围（整个 Big Rect）中所有可能的 double。使用这些点，我会尝试找到彼此距离最短的点 (sqrt(dx^2+ dy^2)) （最短的不应该包含任何点）然后转到下一个最短的点，看看是否有任何点包含等等。换句话说，创建所有组合的顺序列表（不是排列，（a，b）到（c，d) 应该 == (c, d) 到 (a,b)) 按它们之间的距离排序。可能不是最佳的，但可以完成工作。

EDIT: All order pair besides the diagonals of the smaller Rects should be in the order list, since the smaller Rects should not be conatined, You can also exclude pairs with the same x or y value.

于 2013-03-16T16:23:18.987 回答