How to sort points radially with a starting angle?

Question

Given a list of points, how can they be sorted radially around a center position with a defined starting angle? When I first started tackling this problem, I consulted this post and attempted a cross product solution:

public static void RadialCrossSort(Vector3 centerPoint, ref List<Vector3> vertices)
{
    vertices.Sort(delegate (Vector3 a, Vector3 b)
    {
        Vector3 aDifference = a - centerPoint;
        Vector3 bDifference = b - centerPoint;
        float comparison = bDifference.x * aDifference.y - aDifference.x * bDifference.y;
        return (int)Mathf.Sign(comparison);
    });
}

The problem here became that with this algorithm there seemed to be no way to define a starting angle, and the sorting would begin to overlap. You will notice many points are out of order:

So, I took a trigonometric approach instead:

public static float GetAngle(Vector3 centerPoint, Vector3 point)
{
    Vector3 pointFromOrigin = point - centerPoint;
    float angle = Mathf.Atan2(pointFromOrigin.y, pointFromOrigin.x) + Mathf.PI;
    return angle;
}

public static void RadialTrigSort(Vector3 centerPoint, ref List<Vector3> vertices)
{
    vertices.Sort(delegate (Vector3 a, Vector3 b)
    {
        float angleA = GetAngle(centerPoint, a);
        float angleB = GetAngle(centerPoint, b);
        return (int)Mathf.Sign(angleA - angleB);
    });
}

And it works:

However, I have very elementary trigonometry skills, and am unsure how to modify my code to adjust the starting angle of the sort. To anyone who can help me figure this out, thanks a ton in advance.

Also, the code pictured here was the prettier version of my code but not the same exact code used to generate the images (C# in Unity vs Java in Processing). It should have the exact same functionality.

Answer 1

It's still possible to perform the sort with cross-products and an arbitrary starting vector, by following some additional rules:

• If A and B are on the same side of the starting vector, then sort them according to the sign of A x B
• If A and B are on opposite sides, then the vector on the clockwise side of the starting vector takes precedence, regardless of A x B

Sample code:

public static float Cross2D(Vector3 a, Vector3 b)
{
    return a.x * b.y - a.y * b.x;
}
public static float Dot2D(Vector3 a, Vector3 b)
{
    return a.x * b.x + a.y * b.y;
}

private static const float epsilon = 0.0001f; // very "small" number

public static void RadialCrossSort
  (Vector3 centerPoint, Vector3 startVector, ref List<Vector3> vertices)
{
    vertices.Sort(delegate (Vector3 a, Vector3 b)
    {
        Vector3 aDiff = a - centerPoint;
        Vector3 bDiff = b - centerPoint;
        float aCross = Cross2D(startVector, aDiff);
        float bCross = Cross2D(startVector, bDiff);
        if (Mathf.Abs(aCross) < epsilon && Mathf.Abs(bCross) < epsilon) {
           // Extreme case:
           // both vectors are almost (anti-)parallel to the starting vector
           // the cross-product values are too small to be useful, so compare 
           // their directions relative to the starting vector instead
           int aDir = Mathf.Sign(Dot2D(startVector, aDiff));
           int bDir = Mathf.Sign(Dot2D(startVector, bDiff));
           return bDir - aDir;
        } else
        if (Mathf.Sign(aCross) == Mathf.Sign(bCross)) {
          // Same side
          return (int)Mathf.Sign(Cross2D(bDiff, aDiff));
        } else {
          // Operand on clockwise side takes precedence
          return (int)Mathf.Sign(bCross);
        }
    });
}