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

Question

У меня есть (большое) горизонтальное представление с прокруткой и несколько прямоугольников, которые я бы хотел разместить на нем. Каждый прямоугольник имеет желаемое горизонтальное положение, но оно может варьироваться от этого положения до определенного значения (константа, K), если это необходимо. Прямоугольники не должны пересекаться. Вертикальное положение прямоугольников произвольно (конечно, ограничено высотой вида).

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

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

Я разбираюсь в концептуальных алгоритмах, но если вам нужны подробности, это будет выполняться на iPad, и вам нужно будет рассмотреть несколько тысяч (> 1000, но <10000) прямоугольников. В идеале я хотел бы, чтобы что-то было достаточно быстрым, чтобы каждый раз, когда пользователь изменял уровень масштабирования, запускалось заново, но если это не так просто, я могу кэшировать позиции. Объекты - это фотографии на временной шкале, и я хочу, чтобы они были приблизительно рядом, когда произошло событие - я собираюсь приблизиться к ним, чтобы их было больше. </p>

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

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

Answer 1

Я думаю, что это один из способов сделать это.

Шаг 1 - выяснить все места, где можно разместить новый желтый прямоугольник.Без ограничения общности мы можем сохранить это как список всех возможных положений XY верхнего левого угла прямоугольника.Естественно, для такой огромной стартовой области этот список будет содержать миллионы записей, поэтому для экономии места давайте сохраним этот список в виде набора прямоугольных областей.

Например, если на нашем экране есть пиксели от X= От 0 до X = 2999 включительно, и от Y = 0 до Y = 999 включительно, и наш новый прямоугольник имеет ширину 300 пикселей и высоту 150 пикселей, верхний левый угол нашего нового прямоугольника может появляться в любой позиции от (X, Y) = (0, 0) - (2699, 849) включительно.Давайте сохраним это как квадруплет [0, 0, 2699, 849].

Теперь, когда мы помещаем каждый существующий (красный) прямоугольник на экран, некоторые из этих возможностей исключаются, так как они приводят кновый (желтый) прямоугольник, перекрывающий их.Например, если есть красный прямоугольник [1100, 200, 1199, 299], то наш желтый прямоугольник не может иметь свой левый верхний угол в любом положении от (X, Y) = (801, 51) до (1199, 299)включительно.

Итак, замените [0, 0, 2699, 849] четырьмя прямоугольными зонами, которые покрывают одну и ту же область, но оставляют зазор.Есть много способов сделать это, но вот один: [0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849].

Продолжайте добавлять на экран больше красных прямоугольников.Каждый раз, добавляя один, вычитайте больше возможностей из списка (это обычно приводит к тому, что список содержит больше меньших «безопасных зон»).(Это может занять очень много времени для вашего полного экрана с 1000+ прямоугольниками на нем; если вместо этого вы начнете с только упомянутого пространства [XK, 0, X + K, H], то сравнительно немного из 1000+ будет перекрывать это, и вычисления будут выполняться намного быстрее.) Этот код должен быть написан с большой тщательностью и кучей юнит-тестов, потому что ошибок ограждения будет достаточно.

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

Шаг 2: просмотрите этот список и выберите наиболее желательное место.Любая прямоугольная зона, которая фактически пересекает вашу идеальную вертикальную линию, будет иметь приоритет.Но возможно, что не будет ни одного.В этом случае вам остается выбрать наиболее предпочтительный вариант из зон, падающих слева, и зон, падающих справа от идеальной линии.Подсказка: в каждом случае необходимо учитывать только один угол каждой зоны (верхний левый угол зон справа, верхний правый угол зон слева).