Sort points by angle from given axis?

Question

How can I sort an array of points/vectors by counter-clockwise increasing angle from a given axis vector?

For example:

If 0 is the axis vector I would expect the sorted array to be in the order 2, 3, 1.

I'm reasonably sure it's possible to do this with cross products, a custom comparator, and std::sort().

Answer 1

Yes, you can do it with a custom comparator based on the cross-product. The only problem is that a naive comparator won't have the transitivity property. So an extra step is needed, to prevent angles either side of the reference from being considered close.

This will be MUCH faster than anything involving trig. There's not even any need to normalize first.

Here's the comparator:

class angle_sort
{
    point m_origin;
    point m_dreference;

    // z-coordinate of cross-product, aka determinant
    static double xp(point a, point b) { return a.x * b.y - a.y * b.x; }
public:
    angle_sort(const point origin, const point reference) : m_origin(origin), m_dreference(reference - origin) {}
    bool operator()(const point a, const point b) const
    {
        const point da = a - m_origin, db = b - m_origin;
        const double detb = xp(m_dreference, db);

        // nothing is less than zero degrees
        if (detb == 0 && db.x * m_dreference.x + db.y * m_dreference.y >= 0) return false;

        const double deta = xp(m_dreference, da);

        // zero degrees is less than anything else
        if (deta == 0 && da.x * m_dreference.x + da.y * m_dreference.y >= 0) return true;

        if (deta * detb >= 0) {
            // both on same side of reference, compare to each other
            return xp(da, db) > 0;
        }

        // vectors "less than" zero degrees are actually large, near 2 pi
        return deta > 0;
    }
};

Demo: http://ideone.com/YjmaN