Все возможные направления, в которых тело может двигаться в каком-то замкнутом пространстве

Question

Ввод : тело и некоторое закрытое пространство.Тело и пространство представлены в виде ячеек (или, если хотите, BReps ).Изначально тело не пересекает границу пространства.

Задача - найти все возможные направления, в которых тело может двигаться.Например, на следующем рисунке тело может двигаться только в направлениях от (-1,0) до (0,1).Если тело имеет поверхность круга (или сферы) - можно с некоторым шагом вернуть направление (например, для рисунка ниже, вывод может быть (-1,0), (-pi / 4, pi / 4), (0,1) с шагом = 3).

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

Задача должна быть решена в двухмерном и трехмерном пространстве.*

Answer 1

Вы хотите работать в пространстве конфигурации.В основном увеличьте размер вашей границы в зависимости от формы вашего тела, а затем рассматривайте тело как точечный объект.То, что осталось, это все действительные положения тела.Конечно, если ваше тело не является кругом и может вращаться, то ваше пространство конфигурации больше не является 2D или 3D.Он имеет столько же измерений, сколько ваше тело имеет степени свободы, поэтому 6 для твердого тела, которое может перемещаться и вращаться.

Это хорошо известная проблема в роботизированном планировании движения.Google для "пространства конфигурации" или "c-space" и "планирования движения".

Это хороший набор слайдов из класса в Carnegie Mellon: Лекция по конфигурации пространства

Answer 2

Полагаю, тело изначально не пересекает границы вашего пространства.

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

Итак, начните с полного диапазона [0, 2 * pi] действительных направлений.

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

Answer 3

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

Если столкновений нет, объект может двигаться в этом направлении. Если есть столкновение, то оно не может.