Largest Empty Rectangle Within a Rectangle

问题:

I'm not really good in maths, so I'm having really hard times converting formulas into code, and I can't find anything ready-made googling around. I have a big rectangle containing a lot of small rectangles... and all what I need to do is to calculate the largest empty rectangle. Anyonne can help me?

Here is what I came up with... nothing to say, it's a big fail.

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

回答1:

From your Perdue Docs Link it says there is a set (let's call it ASD) of points in the Big Rect and you would to have find the largest Rect containing no points of the set ASD. Looking at your code, it seems you didn't (directly) incorporate these points. I would extract the points from the smaller Rects ans create set ASD. Since your working in type double, you should have access to the points, otherwise the algorithm would have a significantly higher run time since you need to check all possible doubles in a specific range (the entire Big Rect). Using the points, I would trying find the points with the shortest distance form each other (sqrt(dx^2+ dy^2)) (shortest shouldn't contain any points) then go to the next shortest and see if any points are contained and etc. In other words, create a order list of all combinations (not permutations, (a,b) to (c, d) should be == (c, d) to (a,b)) ordered by the distance in between them. Might not be optimal, but gets the job done.

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.