genpfault - 1 year ago 98
C++ Question

# Sort points by angle from given axis?

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()`
.

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;
}
};
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download