How can I generate a correct polygon from an array of unordered vertices?

I am working on a bmesh script that procedurally creates a mesh.

I'm having a problem determining how to order the vertices for the generated n-gon face.

I know the position of each vertex - but need to order them somehow so the face doesn't fold over itself.

Normally with blender UI you can select several vertices and use the fill feature to automatically create a face and fill the hole. Somehow this is automatically finding an order.

Should I be sorting the vertex positions by the position in space? I thought about sorting by X then Y or something like that but this won't work in all use cases in any dimension?

So the question is :

Given a list of vertices that are all aligned to a single arbitrary plane - how to determine which vertex order is best to generate a non-self-folding face?

• Try counterclockwise order. 870 871 872 874 873 Jul 19 '21 at 22:03
• You can see which numbers are counterclockwise by looking at the picture - how to determine order without looking at picture - i.e. by evaluating individual vertex positions. Jul 20 '21 at 0:21
• yes counterclockwise order works - but the problem is how to derive "clockwise" order from a list of verts (no picture) Jul 20 '21 at 0:22
• @Gorgious - thanks for helping to format the question Jul 20 '21 at 10:38

The Blender function that makes a poly from a point cloud is BM_vert_sort_radial_plane.

/**
* Makes an NGon from an un-ordered set of verts
*
* assumes...
* - that verts are only once in the list.
* - that the verts have roughly planer bounds
* - that the verts are roughly circular
* there can be concave areas but overlapping folds from the center point will fail.
*
* a brief explanation of the method used
* - find the center point
* - find the normal of the vcloud
* - order the verts around the face based on their angle to the normal vector at the center point.
*
* \note Since this is a vcloud there is no direction.
*/


(If you want to read it, here's some quick links to BM_verts_calc_normal_from_cloud_ex and angle_signed_on_axis_v3v3v3_v3 too).

So for verts in a plane, it looks like the idea is to simply sweep out a circle around the centroid, taking verts in the order you hit them.

Assuming the verts are roughly a circle (no verts at the centroid, no edges pointing radially away from the centroid) you can do this with something like the function below. (These assumptions are pretty easy to lift if you need to, they just simplify the code a bit.)

import math
import mathutils
from mathutils import Vector

"""
Given a list of vertex positions (vs) and indices
for verts making up a circular-ish planar polygon,
returns the vertex indices in order around that poly.
"""
assert len(vs) >= 3

# Centroid of verts
cent = Vector()
for v in vs:
cent += (1/len(vs)) * v

# Normalized vector from centroid to first vertex
# ASSUMES: vs[0] is not located at the centroid
r0 = (vs[0] - cent).normalized()

# Normal to plane of poly
# ASSUMES: cent, vs[0], and vs[1] are not colinear
nor = (vs[1] - cent).cross(r0).normalized()

# Pairs of (vertex index, angle to centroid)
vpairs = []
for vi, vpos in zip(indices, vs):
r1 = (vpos - cent).normalized()
dot = r1.dot(r0)
angle = math.acos(max(min(dot, 1), -1))
angle *= 1 if nor.dot(r1.cross(r0)) >= 0 else -1
vpairs.append((vi, angle))

# Sort by angle and return indices
vpairs.sort(key=lambda v: v[1])
return [vi for vi, angle in vpairs]


Example:

vs = [
Vector((   0,    1, 0)),
Vector((  -1,    0, 0)),
Vector((-0.5, -0.5, 0)),
Vector((   1,    0, 0)),
Vector(( 0.5, -0.5, 0))
]
indices = [
870,
871,
872,
873,
874,
]

• It works perfectly with 5 vectors. If you comment out one of the input Vectors (only supply 4 vertices) the angle = math.acos(r1.dot(r0)) line generates a ValueError: math domain error. Jul 20 '21 at 21:46