Как эффективно рассчитать нормаль замкнутого контура, определенного копланарными точками?

Question

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

Мы хотим вычислить нормальное

У нас есть два вопроса.

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

2. Для вогнутой замкнутой петли некоторые нормали будут указывать противоположный путь.

Наше решение состоит в том, чтобы вычислить нормаль для всех последовательных сегментов, которые определяют замкнутый цикл. Таким образом, проблема 1 может быть преодолена путем отбрасывания внешних вычисленных нормалей. Проблему 2 можно преодолеть, зная, что направление большинства нормалей будет правильным.

Кажется, это работает, но очень дорого.

Есть ли более простое, дешевое, более элегантное решение?

Answer 1

Предполагая, что точки {p_i}, 0<=i<n, образуют многоугольник против часовой стрелки, вычисляют сумму перекрестного произведения каждого треугольника веерного треугольника многоугольника (даже в вогнутых частях):

normal = vector3(0, 0, 0);
for(int i=1; i<n-1; ++i) 
    normal += cross(p[i+1]-p[0],p[i]-p[0]);
normal /= norm(n);

Это получено из теоремы Стокса . Длина нормали (до нормализации) равна удвоенной области со знаком, заключенной в цикл. Таким образом, вам гарантировано, что оно не будет нулевым (если область не нулевым), и вам гарантировано, что оно будет указывать в правильном направлении.