How can I efficiently calculate the normal of a closed loop defined by coplanar points?

Question

We have set of coplanar points that define a closed loop, which are Counter clock wise wound. The loop is guaranteed to not be self intersecting.

We want to calculate the normal

We have two issues.

1. For points that are close to collinear, floating point precision causes erroneous normals to be calculated using cross-product.

2. For a concave closed loop, some normals will point the opposite way.

Our solution is to calculate the normal for all sequential segments that define the closed loop. This way, issue 1 can be overcome by discarding outlying calculated normals. Issue 2 can be overcome by knowing that the direction of the majority of the normals will be correct.

This seems to work, but is very expensive.

Is there a simpler, cheaper, more elegant solution?

Answer 1

Assuming points {p_i}, 0<=i<n, forms a counterclockwise polygon, compute the sum of the cross product of every triangle of a triangle fan of the polygon (even in the concave parts):

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);

This is derived from the Stoke's theorem. The length of the normal (before normalization) is equal to two times the signed area enclosed by the loop. So you are guaranteed that it will not be null (if the area is not null) and you are guaranteed that it will point in the right direction.