Отслеживание 2D-многоугольника в 3D-пространстве - подходящий алгоритм?

Question

В настоящее время я работаю над проблемой, когда мне нужно правильно упорядочить (используя что-то вроде правила правой руки) узлы, которые составляют плоский многоугольник в трехмерном пространстве. Моя идея до сих пор состоит в том, чтобы построить матрицу преобразования для преобразования узлов в плоскость x-y, а затем использовать сканирование Грэма. Мне нужно убедиться, что пользователь вводит только выпуклые многоугольники, поэтому, если я найду какие-либо "внутренние" узлы, я знаю, что многоугольник является вогнутым и может выдать ошибку. В дополнение к проверке выпуклости процедура сортировки сканирования Грэма закажет мне узлы.

Я не очень знаком с алгоритмами оптимизированной геометрии. Похоже ли это на подходящий / эффективный процесс? Или есть лучший способ:

1) Упорядочить узлы многоугольника по некоторому правилу (например, правило относительной влажности) и 2) Убедитесь, что плоский многоугольник (который может не находиться в плоскости x-y) является выпуклым?

Answer 1

Да, это очень хорошее решение. Вот как это сделать, чтобы игнорировать неточности в цифрах.

- take any 3 points; these determine the plane, rotate appropriately
- check that abs(z)<THRESHOLD for all z-coordinates, now you can ignore them
- perform Graham scan which is O(n log(n)) time
- return order, else throw error if results.size < #points (non-convex)

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

С некоторыми допущениями, это доказуемо так же хорошо, как вы можете сделать асимптотически, потому что в противном случае вы могли бы использовать это для выполнения сортировки сравнения менее чем за O(n log(n)) время, что, как мы знаем, невозможно без дополнительных знаний (проблема состоит в том, чтобы поместить каждый элемент X несортированного массива в положение [X, X ^ 2] на плоскости плюс точку в [0, max ^ 2]).