algorithm - 矩形覆盖

Question

我有 N 个边平行于 x 轴和 y 轴的矩形。还有另一个矩形，模型。我需要创建一个算法来判断 模型 是否完全被 N 个矩形覆盖。

我有一些想法。我认为首先，我需要按左侧对矩形进行排序(可以在 O(n log n) 时间内完成)，然后使用垂直扫描线。

+------------------------------------------------------------> x
|O
|                  +----+
|   +---------+    |    |
|   |        ++----+--+ |
|   |      +-++----+-+| |
|   |      | |     +-++-+
|   +------+ +-------++
|          +---------+
|
|
|
|y

蓝色矩形是模型。

首先，我需要抽象算法。对于实现没有特殊要求。矩形可以表示为一对点(左上角和右下角)。

这是准备考试的任务之一。我知道最好的算法可以在 O(n log n) 时间内完成。

Answer 1

这是一个分而治之的算法。 AVERAGE 案例复杂度非常好，我会说它类似于 O(n log MaxCoords)。虽然最坏的情况可能是二次的，但我认为这样的测试很难创建。为了让它更难，让递归函数调用的顺序随机。也许@Larry 的建议可以平均达到 O(n log n)。

我想不出扫线解决方案，但对于我尝试过的测试来说，这是非常快的。

基本上，在蓝色矩形上使用递归函数。首先检查蓝色矩形是否完全被其他矩形之一覆盖。如果是，我们就完成了。如果不是，将它分成 4 个象限，并在这些象限上递归调用函数。所有 4 个递归调用都必须返回 true。我包括一些绘制矩形的 C# 代码。您也可以更改它以使用更大的值，但在这种情况下请删除绘图过程，因为这些过程将永远持续下去。我用生成的一百万个矩形和一个边长十亿的正方形对其进行了测试，这样它就不会被覆盖，并且提供的答案(false)在四核上花费了大约一秒钟。

我主要在随机数据上对此进行了测试，但它似乎是正确的。如果事实并非如此，我会删除它，但也许它会让你走上正确的道路。

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    List<Rectangle> Rects = new List<Rectangle>();

    private const int maxRects = 20;

    private void InitRects()
    {
        Random rand = new Random();

        for (int i = 0; i < maxRects; ++i) // Rects[0] is the model
        {
            int x = rand.Next(panel1.Width);
            int y = rand.Next(panel1.Height);

            Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y))));
        }
    }

    private void DrawRects(Graphics g)
    {
        g.DrawRectangle(Pens.Blue, Rects[0]);
        for (int i = 1; i < Rects.Count; ++i)
        {
            g.DrawRectangle(Pens.Red, Rects[i]);
        }
    }

    private bool Solve(Rectangle R)
    {
        // if there is a rectangle containing R
        for (int i = 1; i < Rects.Count; ++i)
        {
            if (Rects[i].Contains(R))
            {
                return true;
            }
        }

        if (R.Width <= 3 && R.Height <= 3)
        {
            return false;
        }

        Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));

        return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight);
    }

    private void Go_Click(object sender, EventArgs e)
    {
        Graphics g = panel1.CreateGraphics();
        panel1.Hide();
        panel1.Show();
        Rects.Clear();

        InitRects();
        DrawRects(g);

        textBox1.Text = Solve(Rects[0]).ToString(); 
    }