алгоритм, чтобы проверить, если многоугольник является проекцией многогранника

Question

Я пытаюсь разработать алгоритм, который выполняет следующие действия:

Учитывая 2D многоугольник и 3D-многогранник, определить, является ли 2D многоугольник является проекцией 3D-многогранник (точнее, перспективный прогноз), не зная, какую матрицу преобразования мы, возможно, использовали для проекции.

вход

• {2D Многоугольник}
• {3D Многогранник}

выход

• {BOOL} является ли она проекция в перспективе

Я не прошу ввести код, но мне просто хотелось бы знать, возможно ли это в полиномиальное время.

Любая помощь будет принята с благодарностью.

Answer 1

Просто идея для алгоритма:

Возьмем треугольник проекции из трех точек рядом друг с другом не на одной и той же линии. Итерации через все соответствующие треугольники оригинала. Для всех возможных проекций, которые решают пару треугольников, проверьте соответствие остальных.

Должен признаться, что сейчас я не уверен, могут ли бесконечные решения для треугольников (что было бы трудно повторить)? Если это так, начните с четырех пунктов.

Answer 2

Я думаю, что это возможно, но вы должны сделать справедливое количество обратного проектирования. 2D-эскиз, представляющий трехмерный объект, известен как Orthographic Projection. Ссылка показывает вам необходимые матрицы преобразования, чтобы преобразовать трехмерную точку в ее 2D-проекцию. Теперь, как вы идете наоборот? Обратные матрицы с комбинацией некоторых обратных преобразований (перевод, масштабирование, вращение ...)? Я думаю, что это хорошее продолжение.

Answer 3

Прозрачная проекция 3D-2D имеет 7 степеней свободы (6 для относительного движения сцены по отношению к камере, 1 для фокусного расстояния).

Выберите четыре вершины в 2D-проекции и рассмотрите все возможные соответствия с многогранными вершинами (имеется многочленное число таких ассоциаций). Затем сформировать систему из 7 уравнений по 7 неизвестным параметрам (к сожалению, нелинейную, возможно, восьмое уравнение может быть полезно для выбора среди множества решений).

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

Все это займет многочленное время (четвертое, если я прав), если признать, что решатель занимает ограниченное время (следовательно, ограниченная точность).

---

Если фокусное расстояние известно, то лучше подход возможен.Действительно, всего с 6 неизвестными вы можете найти проекционные параметры от проекции всего трех точек. Известно, что эта проблема имеет решение (на самом деле до 4 из них), как подробно описано в «Новые алгоритмы для перспективы трехточечной задачи», GAO Xiaoshan & CHEN Hangfei, Vol.16 No.3 J Вычислительная техника & Technol. "

Это должно привести к точной процедуре O (N³).

---

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