Is there a better way to find the "outline" path for a set of points in $3D$ space?

Question

I am trying to create a $3D$ model. In $3D$ model file formats, a face is defined by ordering the vertices of that face clockwise as viewed from the center of the object. I have a script that generates the $xyz$ coordinates associated with each face, however I do not know the order they should be in. Here is an image of the problems caused from incorrect vertex ordering.

What is the best way to determine an "outline" order of a set of points approximately set on a plane, but oriented arbitrarily in $3D$ space? There will be anywhere from $4$ up to a dozen vertices.

I've been trying to develop a way to use the angle of each point with respect to a created center point to order them radially, but I'm having too much trouble accommodating different orientations. What also seems like it would work is finding the shortest closed loop path that goes through all points, but I can't figure out how to do this without simply brute forcing all possible paths, which has a factorial time complexity and will be impractical for the larger data sets I'll be using.

Answer 1

I had this exact problem and settled on the angle solution. You can probably get away with projecting the shape onto a carefully chosen one of the xy, xz, or yz planes and using $atan2$, but if you want a more proper solution:

• Calculate a vector $n$ normal to the surface using cross product.
• Let $c$ be the center point
• Arbitrarily pick a starting vertex $v_0$
• Calculate the signed angle from $v_0-c$ to $v_i-c$. You can calculate the angle using the dot product, then add a sign by checking if the cross product between the two vectors is in the same or opposite direction as $n$.
• Sort the vertices by signed angle.