3

四角形の4つの整数点が与えられた場合、その種類（ひし形、長方形、台形、平行四辺形、正方形、または通常の四角形など）のいずれかである場合、これらの点を反時計回りにソートするにはどうすればよいですか（atan2（）関数などを使用せずに）二重点計算）を使用して、対角線が辺にならないようにしますか？

私はこのようなものを struct としてコーディングしました:

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

vector<point> p ;

ダブルポイント計算を使用せずにポイントを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 );
    });

異なる象限の点を象限で比較し、同じ象限の点を比較するために、原点から 2 番目の点までのベクトルから内積の符号を見つけ、原点から最初の点まで CCW ベクトルで 90 度回転させます。

于 2013-08-21T16:01:26.863 に答える