How can I sort vertices efficiently in a specific direction (CW/CCW)?

Question

I am trying to triangulate a set of points using a very simple approach where a base vertex is chosen, and then every other vertex is joined to its neighbouring vertex and then back to the base vertex, to create a triangle-fan structure, which creates a solid surface.

The problem with this approach is that in order to triangulate it there is a lot of iterating, and for each triangulation point, it must iterate over the entire list again to find its nearest CW point which is very slow, but works.

    for (int i = 1; i < triangulationPoints.Count; i++)
        {
//this method iterates over available which is a copy of triangulationPoints
//and finds the closest vertex with no backtracking
            Vector3 vertex = findClosestVertex(currentVertex, available, ordered);
//...
available.Remove(vertex);
        }

Now I'm looking to speed up the algorithm so I get the same effect, but faster.

I implemented a binary insert function that sort each point based on distance from the base vertex as it is inserted into the triangulationPoint list which works nicely and is fast, but produces incorrect results as it doesn't take into account the next CW vertex, but any vertex.

Does anyone have any suggestions as to how I can speed this up, or perhaps another triangulation algorithm that is relatively easy to implement which would achieve fast speeds?

Edit I have tried Unity's triangulator and that produces results that are worse than my attempt. I have also tried a third-party triangulator (https://github.com/CiaccoDavide/Unity-UI-Polygon) and this seems to be exactly what I need, however it only draws on the UI and not in world space.

---

An attempt at implementing DMGregory's explanation

   Quaternion toPlaneSpace = Quaternion.Inverse(Quaternion.LookRotation(cutter.normal));

    centroidPosition = centroidPosition / sharedIntersectionPoints.Count;

    foreach (Vector3 v in sharedIntersectionPoints)
    {
        Vector3 offset = toPlaneSpace * (v - centroidPosition);

        IntersectionPoint ip = new IntersectionPoint(v, Mathf.Atan2(offset.y, offset.x));

        int index = binaryInsertAngle(new IntersectionPoint(v, Mathf.Atan2(offset.y, offset.x)), 0, points.Count);

        if (index > orderedTriangulationPoints.Count)
        {
            orderedTriangulationPoints.Add(ip.point);
            points.Add(ip);
        }
        else
        {
            orderedTriangulationPoints.Insert(index, ip.point);
            points.Insert(index, ip);
        }
    }

Both the new ordered list and the old ordered list are the same size so it should be stepping over the vertices correctly without missing any.

Answer 1

1. Iterate over the vertices and store a running average of their positions to compute an estimated centroid position.

2. Take your cutting plane and use it to form a quaternion or matrix you can use to transform vectors in the cutting plane back to a standard XY plane. eg:

   Quaternion toPlaneSpace = Quaternion.Inverse(Quaternion.LookRotation(planeNormal));

3. Iterate over the vertices again and compute the local offset within the plane:

   offset = toPlaneSpace * (vertexPosition - centroid)

4. Use this offset's x and y to compute a pseudo-angle.

   We could use pseudoAngle = Mathf.Atan2(y, x) but this is actually a little heavier-weight than we need. We don't care if it's a true angle, only that it increases monotonically with angle (ie. as we move our xy point counter-clockwise about the origin, the value of pseudoAngle keeps going up until our wrap-around point - that's enough to let us sort the vertices correctly)

   So, if you really want to shave every cycle, you can swap this out for the approximate Atan2 method of your choice.

5. Store your psuedoAngle somewhere that you can associate with the vertex, like a parallel array of floats (where the index of the vertex in your collection exactly matches the index of its corresponding pseudoAngle

6. Sort your vertex collection by pseudoAngle.

   This last step dominates the running time at O(n log n), which is still quite reasonable (and beats repeating a search every time we need to pick a new vertex)

Now you can walk the sorted list in order to build your triangles, as long as your polygon is always convex.