Пересечение двух вогнутых многоугольников в заданном направлении

Входные данные: два трехмерных вогнутых многоугольника A и B, единичный вектор d. Полигоны не пересекаются в момент времени t = 0. Ожидается, что направление d не будет меняться очень часто, поэтому требуется некоторая фаза предварительной обработки.

Задача: определить, можно ли пересечь два вогнутых многоугольника A и B в направлении d в некоторый момент >т. Другими словами: если мы переместим один многоугольник в заданном направлении d, пересечет ли он другой многоугольник?

Вывод: 1 - пересечение есть, 0 - нет.


algorithm 3d computational-geometry
person innochenti    schedule 28.03.2012    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Сначала вы должны найти плоскость, перпендикулярную вектору d.

Плоскость

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

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

person Jarosław Gomułka    schedule 28.03.2012
comment
насколько я понимаю, это верно только для выпуклых многоугольников. см. теорему SAT. поправьте меня, если я ошибаюсь. - person innochenti; 28.03.2012
comment
Я никогда не предполагаю в своем решении наличие какой-то разделяющей оси. Я думаю, что мое решение будет работать для невыпуклых 3D-полигонов. - person Jarosław Gomułka; 28.03.2012