整点计数器时钟智能排序
整点计数器时钟智能排序
提问于 2013-08-21 21:09:14
给定一个四边形的四个整点，它可以是它的任何类型(如菱形、矩形、梯形、平行四边形、正方形或普通四边形)，我如何按时钟方向对这些点进行排序(不使用atan2()函数或任何双点计算)，这样我就不会以对角线作为它的边？
我已经将类似这样的代码编写为struct：
typedef struct {
long long x,y ;
} point ;
vector<point> p ;我想不出排序功能中的比较功能是什么，以便在不使用任何双点calculation.Can的情况下对逆时针订单中的点进行排序。有人能帮我吗？
回答 2
Stack Overflow用户
发布于 2013-08-21 21:23:38
尝试这样的操作(假设轴点在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;
}
}Stack Overflow用户
发布于 2013-08-22 00:01:27
你可以使用这个代码(不需要规格化向量，也假设轴点在(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 );
});我们通过象限来比较来自不同象限的点，并且为了比较相同象限中的点，我们找到从原点到第二点的点积的signum，并且在从原点到第一点的CCW向量上旋转90度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18358352
复制相关文章
相似问题
腾讯云开发者
