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

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.

• Do I understand correctly that your vertices are provided in an unstructured soup, with no meaningful ordering whatsoever? Or is there some pattern to the way they're generated/provided? – DMGregory Feb 17 '18 at 18:49
• @DMGregory Yes they're unordered initially. I'm just iterating over the mesh vertices so it's however they were ordered by the creator I'd imagine but for this specific triangulation to work, they need to be in order. – jjmcc Feb 17 '18 at 18:52
• @DMGregory do you have any idea on how I'd achieve this? I'm essentially slicing a 3d object in half and using the intersection points as the points to triangulate. I construct an octree for the 3d object (so the triangles go into the octants in any order), and then find the intersected triangles, compute the intersections and then try to create a surface from the intersections. I have already tried Unity's triangulator and that produces worse results than what I have here. – jjmcc Feb 19 '18 at 10:24
• Ah, so if you're cutting the model in half, you probably know the orientation of the cutting plane, and roughly where the center of the cut is? Those details can save us some work. – DMGregory Feb 19 '18 at 12:42
• @DMGregory Yes I have the cutting plane data, but not the center of the cut. I can calculate it though. – jjmcc Feb 19 '18 at 16:35

## 1 Answer

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.

• Hi thanks for this explanation! It seems to work to an extent, however it produces some artefacts when triangulating whereas my original attempt doesn't. I have added an image to my OP if you wouldn't mind looking at it. I have compared the two sorted lists from both this algorithm, and my original one and they are totally different and I believe they are sorted correctly by angle. – jjmcc Feb 23 '18 at 17:50
• Hmm I think this could actually be on my part when triangulating. There is an issue sometimes with the triangle's winding order – jjmcc Feb 23 '18 at 18:15
• Yes seemed to be my triangulating, works nicely now. Thanks for this! – jjmcc Feb 24 '18 at 0:10
• Hi quick question, in order to save performance I want to try and eliminate the iteration over the points to get the centroid position as I'm currently doing this twice. Would you happen to know of any quicker way to achieve this? I was thinking something like a 2D collider which would wrap around all my points somehow, and then I could get the center of that. – jjmcc Feb 24 '18 at 18:46
• Sure, or you could try to sample a subset of your points. Or just pick one of the points to use as the hub of your fan, and sort by angle from there. Note that the original method works for star-shaped polygons, but starting from an edge will only work for polygons with no concavities. – DMGregory Feb 24 '18 at 18:49