从给定轴按角度排序点？

Question

如何通过逆时针增加给定轴向量的角度对点/向量数组进行排序？

例如:

如果0是轴向量,我希望排序的数组按顺序排列2, 3, 1.

我有理由相信它可以用交叉产品,自定义比较器和std::sort().

Answer 1

是的,您可以使用基于跨产品的自定义比较器来完成.唯一的问题是天真的比较器不具备传递性.因此需要额外的步骤,以防止参考的任一侧的角度被认为是接近的.

这将比涉及trig的任何事情都快得多.甚至没有必要先进行标准化.

这是比较器:

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;
    }
};

演示:http://ideone.com/YjmaN

Answer 2

最简单但可能不是最佳方法是将笛卡尔坐标相对于中心点移动,然后将它们转换为极坐标.然后只需减去"起始矢量"模360的角度,最后按角度排序.

或者,你可以制作一个自定义比较器来处理所有可能的斜率和配置,但我认为极坐标更加透明.