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

Question

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

Проблема: Определить, могут ли два вогнутых многоугольника A и B пересекаться в направлении d , в какое-то время т . Другими словами: если мы переместим один многоугольник в заданном направлении d , пересекает ли он другой многоугольник?

Вывод: 1 - пересечение существует, 0 - в противном случае.

Answer 1

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

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

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