3

给定四边形的四个整数点,可以是任何类型的点(如菱形、矩形、梯形、平行四边形、正方形或普通四边形),我如何逆时针对这些点进行排序(不使用 atan2() 函数或任何双点计算)这样我就不会以对角线作为它的边了吗?

我已经将这样的代码编码为 struct :

typedef struct {
      long long x,y ;
} point ;

vector<point> p ;

在不使用任何双点计算的情况下,我无法弄清楚 sort 函数中的比较函数以 CCW 顺序对点进行排序。有人可以帮我吗?

4

2 回答 2

2

尝试类似的事情(假设您的支点位于 0, 0 ):

bool operator<(point other)
{
    // normalize both points
    if(y > 0 && other.y > 0)
        return x < other.x;
    else if(y < 0 && other.y < 0)
        return x > other.x;
    else
    {
        return y < other.y;
    }
}
于 2013-08-21T13:23:38.000 回答
1

您可以使用此代码(不需要规范化向量,也假设枢轴在(0,0)):

int Quadrant( const Point &pt ) {
    if( pt.x >= 0 && pt.y >= 0 )
        return 0;
    if( pt.x < 0 && pt.y >= 0 )
        return 1;
    if( pt.x < 0 && pt.y < 0 )
        return 2;
    if( pt.x >= 0 && pt.y < 0 )
        return 3;
}

std::sort( std::begin( pt ), std::end( pt ), []( const Point &lhs, const Point &rhs ) {
    return Quadrant(lhs) < Quadrant(rhs) || ( Quadrant(lhs) == Quadrant(rhs) && lhs.x*rhs.y - lhs.y*rhs.x > 0 );
    });

来自不同象限的点我们按它们的象限进行比较,为了比较同一象限中的点,我们找到从原点到第二点的向量的点积符号,并在逆时针向量上从原点到第一点旋转 90 度。

于 2013-08-21T16:01:26.863 回答