Генерация неперекрывающихся тестовых наборов прямоугольников

Question

Увы, это вопрос университетского типа, но я все еще борюсь с ним.

Мне нужно создать большие тестовые наборы прямоугольников, не перекрывающихся, которые затем можно использовать для проверки алгоритма, который находит смежность между ними. Тестовые наборы, вероятно, должны иметь более 10000 - 100000 прямоугольников. Я искал в сети примеры того, как генерировать тестовые наборы, как это, но ничего не нашел. Я знаю, что я мог бы использовать метод чисто грубой силы, и каждый раз, когда генерируется случайный прямоугольник, проверяйте, перекрывается ли он с любым другим прямоугольником, но похоже, что генерация тестовых наборов в конечном итоге займет несколько дней, если не дольше !

Кто-нибудь знает, как это сделать, или, по крайней мере, где я должен начать искать?

Answer 1

Я нашел вашу идею забавной и вызывающей и поэтому попытался найти решение с помощью матрицы.

По сути, идея состоит в том, чтобы (при разговоре в пикселях) создать матрицу логических значений той же ширины и высоты, что и корень квадратный из MaxWidthOfRectangle * (NumberOfRectangles) (просто для простоты те же ширина и высота).

Далее для каждой записи в матрице создайте случайный прямоугольник между минимальной и максимальной границами. и установить все bools в матрице для конкретного прямоугольника. Теперь при создании следующего прямоугольника вы можете просто проверить «вокруг» нужного места, чтобы определить, сколько места вы можете занять, вместо того, чтобы оценивать размер и сравнивать друг с другом прямоугольник, если он конфликтует.

Мой код:

   class RectangleGenerator
    {
        readonly bool[,] _matrix;
        readonly int _size;
        readonly int _minimalBoxSize;
        readonly int _maximumBoxSize;
        readonly Random _random = new Random(1);

        readonly List<Point> _offsets;

        public bool[,] Matrix { get { return _matrix; } }

        public RectangleGenerator(int size, int minimalBoxSize, int maximumBoxSize)
        {
            _matrix = new bool[size, size];
            _size = size;
            _minimalBoxSize = minimalBoxSize;
            _maximumBoxSize = maximumBoxSize;

            _offsets = new List<Point>(size * size);

            Reset();
        }

        public IEnumerable<Rectangle> Calculate()
        {
            while (_offsets.Count > 0)
            {
                Point currentPoint = _offsets[_offsets.Count - 1];
                _offsets.RemoveAt(_offsets.Count - 1);

                if (!_matrix[currentPoint.X, currentPoint.Y])
                {
                    Rectangle rectangle;
                    if (TryCreateNextRectangle(currentPoint.X, currentPoint.Y, out rectangle))
                    {
                        // fill the matrix with the rectangle + padding
                        int startFillX = Math.Max(0, rectangle.Left);
                        int startFillY = Math.Max(0, rectangle.Top);
                        int endFillX = Math.Min(_size, rectangle.Right);
                        int endFillY = Math.Min(_size, rectangle.Bottom);

                        for (int fillX = startFillX; fillX < endFillX; fillX++)
                        for (int fillY = startFillY; fillY < endFillY; fillY++)
                        {
                            _matrix[fillX, fillY] = true;
                        }

                        yield return rectangle;
                    }
                }
            }
        }

        private bool TryCreateNextRectangle(int x, int y, out Rectangle rectangle)
        {
            int maxWidth = DetermineMaxWidth(x, y, _minimalBoxSize);
            int maxHeight = DetermineMaxHeight(y, x, maxWidth);

            if (maxWidth < _minimalBoxSize || maxHeight < _minimalBoxSize)
            {
                rectangle = Rectangle.Empty;
                return false;
            }

            int width = _random.Next(_minimalBoxSize, maxWidth);
            int height = _random.Next(_minimalBoxSize, maxHeight);

            rectangle = new Rectangle(x, y, width, height);

            return true;
        }

        private int DetermineMaxWidth(int x, int y, int height)
        {
            int result = Math.Min(_maximumBoxSize, _size - x);

            for (int offsetX = 0; offsetX < result; offsetX++)
            for (int offsetY = 0; offsetY < height; offsetY++)
            {
                if (_matrix[x + offsetX, y + offsetY])
                {
                    result = offsetX;
                    break;
                }
            }

            return result;
        }

        private int DetermineMaxHeight(int y, int x, int width)
        {
            int result = Math.Min(_maximumBoxSize, _size - y);

            for (int offsetY = 0; offsetY < result; offsetY++)
            for (int offsetX = 0; offsetX < width; offsetX++ )
            {
                if (_matrix[x + offsetX, y + offsetY])
                {
                    result = offsetY;
                    break;
                }
            }

            return result;
        }

        public void Reset()
        {
            // append for padding:
            for (int x = 0; x < _size; x++)
            for (int y = 0; y < _size; y++)
            {
                _matrix[x, y] = false;
                if (_size - x >= _minimalBoxSize && _size - y >= _minimalBoxSize)
                {
                    _offsets.Add(new Point(x, y));
                }
            }

            _offsets.Sort((x, y) => x == y ? 0 : _random.Next(-1, 1));
        }
    }