Нахождение свободной области на сцене

Question

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

Я думал о том, чтобы попробовать случайную позицию, проверь, свободна ли она с

private function containsRect(r:Rectangle):Boolean {
    var free:Boolean = true;
    for (var i:int = 0; i < numChildren; i++)
        free &&= getChildAt(i).getBounds(this).containsRect(r);
    return free;
}

и в случае возврата false попытаться использовать другую случайную позицию.

Проблема в том, что если свободного места нет, я застряну, пробуя случайные позиции навсегда.

Есть элегантное решение для этого?

Answer 1

Пусть S будет площадь сцены. Пусть A будет площадь наименьшего прямоугольника, который мы хотим нарисовать. Пусть N = S / A

Один из возможных детерминистических подходов:

Когда вы рисуете прямоугольник на пустой сцене, это делит сцену не более чем на 4 области, которые могут соответствовать вашему следующему прямоугольнику. Когда вы рисуете свой следующий прямоугольник, одна или две области делятся не более чем на 4 субрегиона (каждая), которые могут соответствовать прямоугольнику и т. Д. Вы никогда не создадите больше чем N областей, где S - это область вашей сцены, и А это площадь вашего самого маленького прямоугольника. Сохраните список регионов (несортированные - это хорошо), каждый из которых представлен своими четырьмя угловыми точками, и каждый помечен своей площадью, и используйте взвешенную по площади выборку резервуара с размером резервуара 1, чтобы выбрать область с вероятностью, пропорциональной его площади, самое большее за один проход по списку. Затем поместите прямоугольник в случайном месте в этой области. (Выберите случайную точку в нижней левой части области, которая позволяет рисовать прямоугольник с этой точкой в ​​качестве ее нижнего левого угла, не ударяя по верхней или правой стене.)

Если вы не начинаете с пустого этапа, просто создайте список доступных областей в O (N) (например, перерисовав все существующие прямоугольники на пустом этапе в любом порядке), прежде чем искать свой первый указать, чтобы нарисовать новый прямоугольник.

Примечание. Вы можете изменить размер резервуара на k, чтобы выбрать следующие k прямоугольников за один шаг.

Примечание 2. В качестве альтернативы можно сохранить доступные области в дереве, где вес каждого ребра равен сумме областей областей в поддереве над областью этапа. Затем, чтобы выбрать область в O (logN), мы рекурсивно выбираем корень с вероятностной областью корневой области / S или каждое поддерево с вероятностным весом края / S. Однако обновление весов при повторной балансировке дерева будет раздражать.

Один из возможных рандомизированных подходов:

Выберите случайную точку на сцене. Если вы можете нарисовать один или несколько прямоугольников, которые содержат точку (а не только тот, у которого точка находится в левом нижнем углу), то верните случайно расположенный прямоугольник, содержащий эту точку. Можно расположить прямоугольник без смещения с некоторыми тонкостями, но я оставлю это вам.

В худшем случае есть один пробел, достаточно большой для нашего прямоугольника, а остальная часть сцены заполнена. Таким образом, этот подход успешен с вероятностью> 1 / N или не с вероятностью <1-1 / N. Повторите N раз. Теперь мы терпим неудачу с вероятностью <(1-1 / N) ^ N <1 / e. Под неудачей мы подразумеваем, что есть место для нашего прямоугольника, но мы не нашли его. Под успехом мы подразумеваем, что нашли пространство, если оно существует. Чтобы достичь разумной вероятности успеха, мы повторяем либо Nlog (N) раз для вероятности отказа 1 / N, либо N² раз для вероятности отказа 1 / e ^ N. </p>

Резюме: Попробуйте случайные точки, пока мы не найдем пробел, останавливаясь после попыток NlogN (или N²), и в этом случае мы можем быть уверены, что пробела не существует.

Answer 2

Вы можете упростить вещи с помощью преобразования. Если вы ищете подходящее место для размещения вашего прямоугольника LxH, вы можете вместо этого вырастить все предыдущие прямоугольники на L единиц вправо, а H на единицы вниз, а затем искать одну точку, которая не пересекает ни одну из , Эта точка будет в правом нижнем углу допустимого места для размещения вашего нового прямоугольника.

Затем примените алгоритм сканирования линии сканирования, чтобы найти области, не покрытые каким-либо прямоугольником. Если вы хотите равномерное распределение, вы должны выбрать случайную y-координату (при условии, что вы развернетесь), взвешенную по распределению свободной области. Затем выберите случайную x-координату равномерно из открытых сегментов в выбранной вами линии сканирования.

Answer 3

Одной из возможных проверок, которую вы могли бы сделать, чтобы определить, достаточно ли места, было бы проверить, какую площадь занимает текущий набор прямоугольников. Если оставшаяся площадь меньше площади нового прямоугольника, вы можете немедленно сдаться и выручить. Я не знаю, какая информация у вас есть, или прямоугольники располагаются по регулярному шаблону, но если это так, вы можете изменить проверку, чтобы увидеть, очевидно ли недостаточно свободного места.

Возможно, это не самый подходящий метод для вас, но это было первое, что пришло мне в голову!

Answer 4

Я не уверен, насколько это будет элегантно, но вы можете настроить максимальное количество попыток. Может быть 100?

Конечно, у вас все еще может быть свободное место, но вы все равно можете вызвать событие "финиша". Это похоже на то, когда библиотеки анимации привязывают объект к точке назначения только потому, что он «достаточно близко».

НТН

Answer 5

Вот алгоритм, который я бы использовал

1. Запишите N произвольных точек, где N - количество нужных вам прямоугольников
2. итеративно увеличивайте размеры прямоугольников, созданных в каждой точке N, пока они не коснутся другого прямоугольника.

Вы можете ограничить способ начальных точек, если хотите иметь минимально допустимый размер прямоугольника.

Если вы хотите, чтобы все пространство было покрыто прямоугольниками, вы можете постепенно добавлять случайные точки к оставшемуся «свободному» пространству до тех пор, пока не останется открытой области.

Answer 6

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

Когда вы рисуете новый прямоугольник, обнуляйте соответствующий прямоугольный фрагмент массива. Тогда проверка на свободную область является постоянным ^ H ^ H ^ H ^ H ^ H ^ H ^ H время. Упс, это означает, что время поиска составляет O (нм), где n - длина, m - ширина. Должно быть решение на основе диапазона, ахх.

Edit2: По-видимому, ответ здесь , но, на мой взгляд, это может быть слишком много для реализации в ActionScript, особенно если вы не заинтересованы в геометрии.

Answer 7

Предполагая, что вы определяете размеры прямоугольника, прежде чем пытаться его нарисовать, я думаю, что-то вроде этого может сработать:

Установите сетку возможных центральных точек поперек сцены для предполагаемого прямоугольника. Таким образом, для прямоугольника 6x4 ваша первая точка будет в (3, 2), затем (3 + 6 * x, 2 + 4 * y). Если вы можете нарисовать прямоугольник между четырьмя соседними точками, возможно, существует пробел.

for (x = 0, x < stage.size / rect.width - 1, x++)
    for (y = 0, y < stage.size / rect.height - 1, y++)
        if can_draw_rectangle_at([x,y], [x+rect.width, y+rect.height])
            return true;

Это не говорит вам , где вы можете нарисовать его (хотя должна быть возможность составить список возможных областей рисования), просто вы можете.