c# - 矩形内最大的空矩形

Question

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

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

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;
        }
    }
}

Answer 1

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

编辑:除了较小的 Rects 的对角线之外的所有订单对都应该在订单列表中，因为不应包含较小的 Rects，您还可以排除具有相同 x 或 y 值的对。