«перемещение мебели»: разрешение столкновений в 2-мерном пространстве (не вращающиеся 2-мерные прямоугольники)
В 2d пространстве у нас есть коллекция прямоугольников.
Вот картинка:
Вертикальная линия справа представляет собой неподвижную «стенку».
Стрелка слева показывает направление движения.
Мне нужно переместить крайний левый прямоугольник вправо.
- Прямоугольники не могут вращаться.
- Прямоугольники не могут перекрываться по горизонтали.
- Прямоугольник может уменьшаться (по горизонтали) до определенной минимальной ширины (которая устанавливается индивидуально для каждого прямоугольника)
- Прямоугольники могут двигаться только горизонтально (влево / вправо) и сжиматься горизонтально.
- Крайний левый прямоугольник (на который указывает стрелка) не может сжиматься.
- Ширина и координаты хранятся в виде целых чисел.
Мне нужно переместить крайний левый прямоугольник вправо на X единиц, толкая все на своем пути вправо.
Есть две проблемы:
- Мне нужно определить, как далеко я могу переместиться в крайний левый прямоугольник вправо (возможно, не удастся продвинуться для единиц X).
- Переместить прямоугольник на X единиц (или, если невозможно переместить на X единиц, переместиться на максимально возможную величину, меньшую X) и получить новые координаты и размеры для каждого прямоугольника в системе.
Дополнительные осложнения:
Вы не можете использовать координату Y и высоту прямоугольника для чего-либо, вместо этого
у каждого прямоугольника есть список (реализованный в виде указателей) прямоугольников, по которым он попадет, если вы продолжите перемещать его вправо, вы можете получить только координату x, ширину и минимальную ширину. Эта модель данных не может быть изменена. (технически, представление этого как набора прямоугольников в 2d является упрощением)
Важно: дети из разных уровней и ветвей могут иметь один и тот же прямоугольник в списке «потенциальных столкновений». Вот исходное изображение с указателями, отображаемыми в виде красных линий:
Как мне это сделать?
Я знаю тупой способ (это сработает) решить эту проблему: итеративно. То есть
- Запомните текущее состояние системы. Если состояние системы уже запомнено, забудьте о ранее запомненном состоянии.
- Нажмите крайний левый прямоугольник на 1 единицу.
- Рекурсивно разрешать коллизии (если есть).
- Если столкновение не удалось разрешить, верните запомненное состояние системы.
- Если конфликты могут быть разрешены, и мы уже переместились на X единиц, возвращаем текущее состояние системы.
- В противном случае перейдите к 1.
Это решит проблему, но такое итеративное решение может быть медленным, если X большое. Есть ли лучший способ решить это?
Решение
Одно возможное решение, которое приходит на ум:
Вы сказали, что каждый прямоугольник содержит указатели на все объекты, которые он ударит при движении вправо. Я бы посоветовал взять список указателей из большого прямоугольника (тот, на который указывает стрелка), взять все его узлы (прямоугольники, которые он будет сталкивать), найти минимальную ширину, затем сделать то же самое для всех дочерних узлов, добавить ширина для каждой ветви рекурсивно. Рассматривайте проблему как проблему глубины дерева. Каждый узел имеет минимальное значение ширины, поэтому ответом на ваш вопрос будет расстояние между стеной и значением x правого края большого прямоугольника за вычетом величайшей суммы наименьшей ширины прямоугольников. Создайте вектор, в котором хранится глубина (сумма минимальных ширин) каждой ветви дерева, и найдите максимальное значение. Расстояние минус макс ваш ответ.
представьте себе ту же картину с 4 коробками. один слева, один справа и затем стена. давайте назовем им поле 1, поле 2 (середина вверху), поле 3 (середина внизу) и последнее поле 4 (справа). каждая коробка имеет ширину 4. Все могут сжиматься, кроме левой. поле 2 может уменьшиться на 2, поле 3 может уменьшиться на 1, поле 4 может уменьшиться на 2. Вычисление двух ветвей дает
* Филиал 1: 2 + 2 = 4
* Филиал 2: 3 + 2 = 5
* Относится только к ветви 2, потому что ветвь 1 МЕНЬШЕ, чем ветка 2, следовательно, поместится в пространстве, параллельном ветви 2, и может уменьшаться настолько сильно.
Другие решения
Других решений пока нет …