29

配列内の 4 つの 2D ポイント。それらを時計回りに並べ替える必要があります。1回のスワップ操作でできると思いますが、これを正式に書き留めることはできませんでした。

編集: 私の場合、4 つの点は凸多角形です。

編集: 4 つの点は、凸多角形の頂点です。それらは順番である必要はありません。

4

16 に答える 16

18

より数学的観点を取りたい場合は、4 点の順列を考えることができます。

この場合、時計回りに 4 つの順列があります。

A B C D
B C D A
C D A B
D A B C

他のすべての可能な順列は、0 または 1 回のスワップでこれらの形式のいずれかに変換できます。（対称であるため、Aで始まる順列のみを検討します）

  1. ABCD - 完了
  2. ABDC - C と D を入れ替える
  3. ACBD - B と C を入れ替えます
  4. ACDB - A と B を入れ替えます
  5. ADBC - A と D を入れ替えます
  6. ADCB - B と D を入れ替える

したがって、必要なスワップは 1 つだけですが、どのスワップかを特定するには多少の作業が必要になる場合があります。

最初の 3 点を見て、ABC の署名された領域の符号を確認することで、それらが時計回りかどうかを判断できます。それらが時計回りの場合、1 2 または 5 の場合です。

これらのケースを区別するには、さらに 2 つの三角形をチェックする必要があります。ACD が時計回りの場合は、ケース 1 に絞り込むことができます。そうでない場合は、ケース 2 または 5 でなければなりません。

ケース 2 と 5 のどちらかを選択するために、ABD をテストできます。

ABC反時計回りの場合も同様に確認できます。

最悪の場合、3 つの三角形をテストする必要があります。

ポイントが凸状でない場合は、内側のポイントを見つけ、残りを並べ替えてから、任意のエッジに追加します。四角形が凸状の場合、4 つの点が四角形を一意に決定しなくなり、3 つの等しく有効な四角形が存在することに注意してください。

于 2008-10-28T22:15:07.603 に答える
7

ここで検討する価値のある考えがいくつかあります。

  • 時計回りは、原点に関してのみ意味があります。私は原点を一連の点の重心と考える傾向があります。たとえば、おそらく非常に遠い原点ではなく、4 つのポイントの平均位置にあるポイントに対して時計回りです。

  • 4 つの点 a、b、c、d がある場合、原点の周りにこれらの点の時計回りの順序が複数存在します。たとえば、(a,b,c,d) が時計回りの順序を形成する場合、(b,c,d,a)、(c,d,a,b)、および (d,a,b,c)

  • あなたの 4 点はすでに多角形を形成していますか? もしそうなら、ポイントをソートするのではなく、ワインディングをチェックして逆にすることです。例えば、a,b,c,d は d,c,b,a になります。そうでない場合は、ウェッジの応答に従って、各ポイントと原点の間の結合方位に基づいて並べ替えます。

編集：どのポイントを交換するかについてのコメントについて。

三角形 (a,b,c) の場合、3 番目の点cが直線abの右側にある場合、時計回りであると言えます。次の副次関数を使用して、ポイントの座標に基づいてこれを決定します。

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

4 点の凸多角形 (a、b、c、d) がある場合、これを (a、b、c) と (c、d、a) の 2 つの三角形と見なすことができます。(a,b,c) が反時計回りの場合、ワインディング (a,b,c,d) を (a,d,c,b) に変更して、ポリゴン全体のワインディングを時計回りに変更します。

私が話していることを理解するために、いくつかのサンプルポイントでこれを描くことを強くお勧めします. 凹面多角形、共線点、一致点など、対処すべき例外的なケースがたくさんあることに注意してください...

于 2008-10-28T07:53:44.783 に答える
4

誰かが興味を持っている場合は、同様の問題に対する私の迅速で汚い解決策を次に示します。

私の問題は、長方形の角を次の順序で並べることでした。

左上 > 右上 > 右下 > 左下

基本的には左上から時計回りです。

アルゴリズムのアイデアは次のとおりです。

コーナーを行で並べてから、コーナーペアを列で並べます。

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {    
    if(corners.size() == 4) {    
        ordCorners = orderPointsByRows(corners);

        if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
            Point tmp = ordCorners.get(0);
            ordCorners.set(0, ordCorners.get(1));
            ordCorners.set(1, tmp);
        }

        if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
            Point tmp = ordCorners.get(2);
            ordCorners.set(2, ordCorners.get(3));
            ordCorners.set(3, tmp);
        }               
        return ordCorners;
    }    
    return empty list or something;
}

List<Point> orderPointsByRows(List<Point> points) {
    Collections.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) return -1;
        if (p1.y > p2.y) return 1;
        return 0;
        }
    });
    return points;
}
于 2012-04-11T16:55:18.047 に答える
3

ポイント順列ごとに、靴ひも式 (面積が正または負になるような絶対値を除いたもの) を使用して、座標から面積を計算します。最大面積値は、直接単純四角形に対応しているようです:靴ひも式で見つかった単純直接四角形

ここに画像の説明を入力

于 2012-12-20T11:35:18.883 に答える
3

オリバーは正しい。このコード (コミュニティ ウィキ化) は、4 つの点の配列のすべての可能な組み合わせを生成して並べ替えます。

#include <cstdio>
#include <algorithm>

struct PointF {
    float x;
    float y;
};

// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
    return a.x * b.y - a.y * b.x;
}

// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}

void Sort4PointsClockwise(PointF points[4]){
    PointF& a = points[0];
    PointF& b = points[1];
    PointF& c = points[2];
    PointF& d = points[3];

    if (Orientation(a, b, c) < 0.0) {
        // Triangle abc is already clockwise.  Where does d fit?
        if (Orientation(a, c, d) < 0.0) {
            return;           // Cool!
        } else if (Orientation(a, b, d) < 0.0) {
            std::swap(d, c);
        } else {
            std::swap(a, d);
        }
    } else if (Orientation(a, c, d) < 0.0) {
        // Triangle abc is counterclockwise, i.e. acb is clockwise.
        // Also, acd is clockwise.
        if (Orientation(a, b, d) < 0.0) {
            std::swap(b, c);
        } else {
            std::swap(a, b);
        }
    } else {
        // Triangle abc is counterclockwise, and acd is counterclockwise.
        // Therefore, abcd is counterclockwise.
        std::swap(a, c);
    }
}

void PrintPoints(const char *caption, const PointF points[4]){
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
        points[0].x, points[0].y, points[1].x, points[1].y,
        points[2].x, points[2].y, points[3].x, points[3].y);
}

int main(){
    PointF points[] = {
        {5.0f, 20.0f},
        {5.0f, 5.0f},
        {20.0f, 20.0f},
        {20.0f, 5.0f}
    };

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(j == i)  continue;
            for(int k = 0; k < 4; k++){
                if(j == k || i == k) continue;
                for(int l = 0; l < 4; l++){
                    if(j == l || i == l || k == l) continue;
                    PointF sample[4];
                    sample[0] = points[i];
                    sample[1] = points[j];
                    sample[2] = points[k];
                    sample[3] = points[l];

                    PrintPoints("input: ", sample);
                    Sort4PointsClockwise(sample);
                    PrintPoints("output: ", sample);
                    printf("\n");
                }
            }
        }
    }

    return 0;
}
于 2008-10-29T07:41:23.667 に答える
1 
var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b)  {
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
    if (aTanA < aTanB) return -1;
    else if (aTanB < aTanA) return 1;
    return 0;
});
console.log(arr);

基準点がポリゴン内にある場所。

詳しくはこちらのサイト

于 2012-08-27T11:56:39.160 に答える
1

それを長い道のりで解決してから、最適化してください。

より具体的な問題は、正の x 軸に対する角度を減少させて座標をソートすることです。この角度 (ラジアン単位) は、次の関数によって与えられます。

x>0
    AND y >= 0
       angle = arctan(y/x)
    AND y < 0
       angle = arctan(y/x) + 2*pi
x==0
    AND y >= 0
       angle = 0
    AND y < 0
       angle = 3*pi/2
x<0
    angle = arctan(y/x) + pi

後はもちろん、座標を角度でソートするだけです。x > z の場合のみ、arctan(w) > arctan(z) となるため、角度を相互に比較する関数を非常に簡単に最適化できます。

角度がウィンドウ全体で単調に減少する (または最大で 1 回増加する) ような並べ替えは、少し異なります。

大規模な証明の代わりに、1 回のスワップ操作で 4 つの 2D ポイントが時計回りにソートされることを確認したことを述べておきます。もちろん、どのスワップ操作が必要かを判断するのがコツです。

于 2008-10-28T07:30:07.357 に答える
1

以前の回答に追加する改善点がもう 1 つあります。

覚えておいてください-これらは私たちがいる可能性のあるケースです.

  1. あいうえお
  2. ABDC
  3. ACBD
  4. ACDB
  5. ADBC
  6. ADCB

ABC が反時計回り (マイナス符号の領域) の場合、ケース 3、4、6 になります。この場合、B と C を交換すると、次の可能性が残ります。

  1. あいうえお
  2. ABDC
  3. あいうえお
  4. ABDC
  5. ADBC
  6. ADBC

次に、ABD を確認し、反時計回りの場合は B と D を入れ替えます (ケース 5、6)。

  1. あいうえお
  2. ABDC
  3. あいうえお
  4. ABDC
  5. ABDC
  6. ABDC

最後に、ACD を確認し、ACD が反時計回りの場合は C と D を交換する必要があります。これで、ポイントがすべて整っていることがわかりました。

この方法は、以前の方法ほど効率的ではありません。これには、毎回 3 回のチェックと、複数回のスワップが必要です。しかし、コードははるかに単純になります。

于 2008-10-30T21:08:17.690 に答える
0 
if AB crosses CD
   swap B,C
elif AD crosses BC
   swap C,D

if area (ABC) > 0
   swap B,D

(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if  p*Cx + q*Cy + r  and  p*Dx + q*Dy + r
have different sign, i.e. their product is negative.

最初の 'if/elif' は、時計回りまたは反時計回りの順序で 4 つのポイントをもたらします。(ポリゴンが凸面であるため、他の唯一の「交差」代替手段は「AC クロス BD」です。これは、4 つの点が既にソートされていることを意味します。) 最後の「if」は、反時計回りの場合は常に向きを反転します。

于 2008-10-29T03:05:01.667 に答える
0

1回のスワップで、平面内の4つの点で表される多角形が凸面になることを保証できるというあなたの意見は正しいと思います。未解決の問題は次のとおりです。

  • この 4 点の集合は凸多角形ですか?
  • いいえの場合、どの 2 つのポイントを交換する必要がありますか?
  • 時計回りはどちらの方向ですか？

よく考えてみると、上記の 2 番目の質問に対する唯一の答えは「真ん中の 2 つ」だと思います。

于 2008-10-28T06:45:14.547 に答える
0

ポイント x がポイント y よりも大きいと仮定すると、ポイント (0,0) との角度が大きい場合、C# でこの方法を実装できます。

    class Point : IComparable<Point>
    {
        public int X { set; get; }
        public int Y { set; get; }

        public double Angle
        {
            get
            {
                return Math.Atan2(X, Y);
            }
        }

        #region IComparable<Point> Members

        public int CompareTo(Point other)
        {
            return this.Angle.CompareTo(other.Angle);
        }

        #endregion

        public static List<Point>  Sort(List<Point> points)
        {
            return points.Sort();
        }
}
于 2008-10-28T10:09:11.920 に答える
0

グラハムのスキャンを見てください。もちろん、反時計回りにポイントするため、調整する必要があります。

ps: 4 ポイントではやり過ぎかもしれませんが、ポイントが増えれば面白いかもしれません。

于 2008-10-29T03:25:58.927 に答える
0

これはどう？

// Take signed area of ABC.
// If negative,
//     Swap B and C.
// Otherwise,
//     Take signed area of ACD.
//     If negative, swap C and D.

アイデア？

于 2008-10-28T07:27:38.423 に答える
-1 
if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

「>」が間違った方向を向いている可能性がありますが、その考えはわかります。

于 2008-10-28T09:57:28.183 に答える
-1

ウェッジの答えは正しいです。

簡単に実装するには、smacl と同じように考えます。境界の中心を見つけて、ポイントをその中心に変換する必要があります。

このような：

centerPonintX = Min(x) + (  (Max(x) – Min(x)) / 2  )
centerPonintY = Min(y) + (  (Max(y) – Min(y)) / 2  )

次に、境界の原点に変換するために、各ポイントから centerPointX と centerPointY を減らします。

最後に、Wedge のソリューションを 1 つのひねりだけで適用します。すべてのインスタンスの arctan(x/y) の絶対値を取得します (そのように機能しました)。

于 2008-10-28T08:10:20.863 に答える