Эта проблема на самом деле связана с опрокидыванием, я просто обобщу ниже как таковой:
У меня есть двухмерный вид, и у меня есть несколько прямоугольников в области на экране. Как мне разложить эти поля так, чтобы они не перекрывали друг друга, а только настраивали их с минимальным перемещением?
Позиции прямоугольников являются динамическими и зависят от ввода пользователя, поэтому их положение может быть где угодно.
Прикрепленные изображения показывают проблему и желаемое решение
На самом деле реальная проблема связана с опрокидыванием.
Ответы на вопросы в комментариях
Размер прямоугольников не фиксирован и зависит от длины текста в ролловере.
Насчет размера экрана, прямо сейчас думаю лучше предположить, что размера экрана хватит на прямоугольники. Если прямоугольников слишком много, и алгоритм не дает решения, мне просто нужно настроить содержимое.
Требование «минимального перемещения» больше касается эстетики, чем абсолютного инженерного требования. Можно разделить два прямоугольника, добавив между ними большое расстояние, но это не будет хорошо смотреться как часть графического интерфейса. Идея состоит в том, чтобы сделать наведение / прямоугольник как можно ближе к его источнику (который затем я соединю с источником с помощью черной линии). Таким образом, можно либо «переместить только одну на x», либо «переместить оба на половину x».
Ответы:
Я немного работал над этим, так как мне тоже нужно было что-то подобное, но я задержал разработку алгоритма. Вы помогли мне получить импульс: D
Мне также был нужен исходный код, так что вот он. Я разработал это в Mathematica, но, поскольку я не особо использовал функциональные возможности, думаю, это будет легко перевести на любой процедурный язык.
Историческая перспектива
Сначала я решил разработать алгоритм для кругов, потому что пересечение легче вычислить. Это просто зависит от центров и радиусов.
Я смог использовать программу решения уравнений Mathematica, и она отлично справилась.
Взгляни:
Это было легко. Я только что загрузил решатель со следующей проблемой:
Все очень просто, и Mathematica сделала всю работу.
Я сказал: «Ха! Это легко, теперь займемся прямоугольниками!». Но я был неправ ...
Прямоугольный блюз
Основная проблема с прямоугольниками заключается в том, что запрос пересечения - неприятная функция. Что-то типа:
Итак, когда я попытался подкормить Mathematica множеством этих условий для уравнения, он работал так плохо, что я решил сделать что-то процедурное.
Мой алгоритм получился следующим:
Вы можете заметить, что условие «наименьшего движения» не выполняется полностью (только в одном направлении). Но я обнаружил, что перемещение прямоугольников в любом направлении для его удовлетворения иногда приводит к запутанному изменению карты для пользователя.
Когда я разрабатываю пользовательский интерфейс, я решаю сдвинуть прямоугольник немного дальше, но более предсказуемым образом. Вы можете изменить алгоритм, чтобы проверять все углы и все радиусы вокруг его текущего положения, пока не будет найдено пустое место, хотя это будет намного сложнее.
Во всяком случае, это примеры результатов (до / после):
Изменить> Больше примеров здесь
Как видите, «минимальное движение» не устраивает, но результаты достаточно хорошие.
Я отправлю код здесь, потому что у меня проблемы с моим репозиторием SVN. Уберу, когда решат проблемы.
Редактировать:
Вы также можете использовать R-деревья для поиска пересечений прямоугольников, но это кажется излишним для работы с небольшим количеством прямоугольников. И у меня еще нет реализованных алгоритмов. Возможно, кто-то еще может указать вам на существующую реализацию на выбранной вами платформе.
Предупреждение! Код - это первый подход ... пока не хорошего качества, и, конечно, есть некоторые ошибки.
Это Mathematica.
Основной
HTH!
Изменить: поиск под разными углами
Я реализовал изменение в алгоритме, позволяющее искать во всех направлениях, но отдавая предпочтение оси, обусловленной геометрической симметрией.
За счет большего количества циклов это привело к более компактным окончательным конфигурациям, как вы можете видеть здесь ниже:
Больше образцов здесь .
Псевдокод основного цикла изменен на:
Я не включаю исходный код для краткости, просто прошу его, если вы думаете, что можете его использовать. Я думаю, что если вы пойдете по этому пути, лучше перейти на R-деревья (здесь нужно много интервальных тестов)
источник
Вот предположение.
Найдите центр C ограничительной рамки ваших прямоугольников.
Для каждого прямоугольника R, перекрывающего другой.
При этом прямоугольники постепенно удаляются друг от друга и от центра всех прямоугольников. Это прекратится, потому что компонент v из шага 4 в конечном итоге самостоятельно распределит их достаточно.
источник
Я думаю, что это решение очень похоже на то, что дает cape1232, но оно уже реализовано, так что стоит проверить :)
Следуйте за этим обсуждением на Reddit: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ и ознакомьтесь с описанием и реализацией. Исходный код недоступен, поэтому вот мой подход к этой проблеме в AS3 (работает точно так же, но сохраняет прямоугольники привязанными к разрешению сетки):
источник
velocity
это сумма векторов между ее центром и центром других комнат, если все комнаты уложены в один и тот же центр,velocity.length == 0
для всех комнат и ничто не будет двигаться. Таким же образом, если две или более комнат имеют одинаковый прямоугольник с одним и тем же центром, они будут перемещаться вместе, но останутся сложенными.Мне очень нравится реализация b005t3r! Это работает в моих тестовых примерах, однако у меня слишком мало репутации, чтобы оставить комментарий с двумя предлагаемыми исправлениями.
Вы не должны переводить комнаты с единичным приращением разрешения, вы должны переводить с помощью скорости, которую вы только что без труда рассчитали! Это делает разделение более органичным, так как глубоко пересекающиеся комнаты разделяют каждую итерацию больше, чем не очень глубоко пересекающиеся комнаты.
Вы не должны предполагать, что velociites меньше 0,5 означает, что комнаты разделены, поскольку вы можете застрять в случае, когда вы никогда не разделены. Представьте, что две комнаты пересекаются, но не могут исправить себя, потому что всякий раз, когда одна из них пытается исправить проникновение, они вычисляют требуемую скорость как <0,5, поэтому повторяются бесконечно.
Вот решение для Java (: Ура!
источник
Вот алгоритм, написанный на Java для обработки кластера невращающихся
Rectangle
s. Он позволяет вам указать желаемое соотношение сторон макета и позиционировать кластер, используя параметризованнуюRectangle
точку привязки, на которую ориентируются все сделанные переводы. Вы также можете указать произвольное количество отступов, на которое вы хотите распространитьRectangle
s.}
Вот пример использования
AspectRatio
of1.2
, aFillPercentage
of0.8
и aPadding
of10.0
.Это детерминированный подход, который позволяет задавать интервалы вокруг анкера, оставляя при этом положение самого анкера неизменным. Это позволяет размещать макет везде, где находится точка интереса пользователя. Логика выбора позиции довольно упрощена, но я думаю, что окружающая архитектура сортировки элементов на основе их начального положения с последующим их повторением является полезным подходом для реализации относительно предсказуемого распределения. Кроме того, мы не полагаемся на итеративные тесты пересечения или что-то в этом роде, а просто создаем несколько ограничивающих рамок, чтобы дать нам общее представление о том, где выровнять вещи; после этого наложение отступов становится естественным.
источник
Вот версия, которая принимает ответ cape1232 и является автономным исполняемым примером для Java:
источник