按给定轴的角度排序点？ [英] Sort points by angle from given axis?

问题描述

如何从一个给定的轴向量逆时针增加角度来排列一个点/向量的数组？

例如：

如果 0 是轴向量，我期望有序数组的顺序为 2,3,1 。

我相当确定可以使用交叉产品，自定义比较器和 std :: sort（）

解决方案

是的，您可以使用基于跨产品的自定义比较器来执行此操作。唯一的问题是一个天真的比较器不具备传递特性。所以需要额外的一步，以防止任何一方的参考被视为关闭。

这将比任何涉及trig更快。甚至没有任何需要首先进行标准化。

以下是比较：

  class angle_sort 
 {
 point m_origin; 
点m_dreference; 
 
 //交叉乘积的z坐标，又名行列式
 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）; 
 
 //没有任何东西小于零度
 if（detb == 0&& db.x * m_dreference.x + db.y * m_dreference.y> = 0）返回false; 
 
 const double deta = xp（m_dreference，da）; 
 
 //零度小于其他值
 if（deta == 0&& da.x * m_dreference.x + da.y * m_dreference.y> = 0 ）返回true; 
 
 if（deta * detb> = 0）{
 //在同一参考面上，相互比较
 return xp（da，db）> 0; 
} 
 
 //向量小于零度实际上很大，接近2 pi 
 return deta> 0; 
} 
}; 
  

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

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

Demo: http://ideone.com/YjmaN

这篇关于按给定轴的角度排序点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！