c++ - 整数点的逆时针排序

Question

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

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

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

vector<point> p ;

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

Answer 1

尝试类似的事情（假设您的支点位于 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;
    }
}

Answer 2

您可以使用此代码（不需要规范化向量，也假设枢轴在（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 度。