矩形覆盖

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

Answer 2

很难知道你在寻找什么，但在我看来R 树可能有用？