XY座標上で四角形を構成する頂点が右回りか左回りか？

4頂点を左回りに並べ替える

C#で台形補正を以前作ったのですが、このアルゴリズムでは頂点を左上から左回りに並べる必要があります。
s51517765.hatenadiary.jp

つまり、XY座標上で4つの頂点により形成される交差しない4つの線分による四角形があるとして、この頂点の中で左上を見つけ出し左回りに頂点を並べ替える必要があります。
C#のCanvasに合わせて、左上を原点としマイナスは考えないものとします。

また、↓のような辺が交差する状態は考えないものとします。

台形補正したい対象物の4頂点は順番にクリックすることで取得しますが、これが人によっては左回りであったり右回りであったりする可能性があります。
右回りの時はP3とP1をいれかえる必要があります。
また、だれもが左上から始める、とも限りません。

最初に考えた方法

絶対だれか数学の得意な人が文書化しているはずだとは思いましたが、上手いキーワードが思いつかず、まず自分で実装できるか試してみました。

左回りであるという前提で考えると、四角形の重心に対して、P0がどこにあるかを考えると４つの頂点の位置と順番が決まります。
P0が左上の時はそのままでいいので、それ以外の3つの場合に頂点を入れ替えます。

private void point_normarize(ref System.Drawing.Point px0, ref System.Drawing.Point px1, ref System.Drawing.Point px2, ref System.Drawing.Point px3)
{
    int aveWidth = (px0.X + px1.X + px2.X + px3.X) / 4;
    int aveHight = (px0.Y + px1.Y + px2.Y + px3.Y) / 4;

    System.Drawing.Point tmp = px3;
    if (px0.Y > aveHight && px0.X < aveWidth)
    {
        px3 = px2;
        px2 = px1;
        px1 = px0;
        px0 = tmp;
    }
    else if (px0.Y > aveHight && px0.X > aveWidth)
    {
        System.Drawing.Point tmp2 = px2;
        px2 = px0;
        px0 = tmp2;
        px3 = px1;               
        px1 = tmp;              
    }
    else if (px0.Y < aveHight && px0.X > aveWidth)
    {
        px3 = px0;
        px0 = px1;
        px1 = px2;               
        px2 = tmp;                
    }
}

右回りの時も同様にできます。
しかし、左回りか右回りかを求める必要があります。
左回りか右回りかは以下に記す採用した方法と同じです。

採用した方法

採用した方法は、まず左上の点を求めます。
これはPN.X + PN.YがMinになる点といえます。

この図で斜めの赤線がX+Yが一定の線です。

これが左上の点といえることは、この反例としてP1を下図のように移動すると、実はこのときP1を左上と考えても「台形補正上は」問題がないのです。

次に右回りか左回りかですが、これは左回りと仮定したとき、左上の点と次の点、左上の点と前の点のYの差分を比較するif (y[(idx + 1) % 4] - y[idx] > y[(idx + 3) % 4] - y[idx])ことで判断できます。
idx→idx+1のときidx→idx-1よりYが増加すれば左回り、減少すれば右回りです。
そして、左回りと仮定したのに、Yが減少するときは右回りとなります。

左回りの時は、左上の点をpx0とするようにidxをオフセットします。

//左回り
px0 = p[idx];
px1 = p[(idx + 1) % 4];
px2 = p[(idx + 2) % 4];
px3 = p[(idx + 3) % 4];

右回りの時は、左上の点をpx0とし逆順にします。

//右回り
px0 = p[idx];
px1 = p[(idx + 3) % 4];
px2 = p[(idx + 2) % 4];
px3 = p[(idx + 1) % 4];

これで、4頂点を左上から左回りに変換できました。

private void point_normarize(ref System.Drawing.Point px0, ref System.Drawing.Point px1, ref System.Drawing.Point px2, ref System.Drawing.Point px3)
{
    System.Drawing.Point[] p = { px0, px1, px2, px3 };

    //左上の点を求める
    int[] x_y = { px0.X + px0.Y, px1.X + px1.Y, px2.X + px2.Y, px3.X + px3.Y };

    int tmp = 100000;
    int idx = 0;
    for (int i = 0; i < 4; i++)
    {
        if (x_y[i] < tmp)
        {
            tmp = x_y[i];
            idx = i;
        }
    }
    //左周りか右回りか
    int[] y = { px0.Y, px1.Y, px2.Y, px3.Y };

    if (y[(idx + 1) % 4] - y[idx] > y[(idx + 3) % 4] - y[idx])
    {
        //左回り
        px0 = p[idx];
        px1 = p[(idx + 1) % 4];
        px2 = p[(idx + 2) % 4];
        px3 = p[(idx + 3) % 4];
    }
    else
    {
        //右回り
        px0 = p[idx];
        px1 = p[(idx + 3) % 4];
        px2 = p[(idx + 2) % 4];
        px3 = p[(idx + 1) % 4];
    }
}

ただしこれらは考慮漏れがあったりバグがある可能性があります。

このようなアルゴリズムを実装した後、以下のようなものを見つけました。
符号付面積というものを算出すると右回り、左回りを算出できるらしいです。
私が考えた方法はこちらのアルゴリズムのある限定条件下に一致するものではないかと思います。
もしバグがあったらこちらに変更します。
www5d.biglobe.ne.jp

まとめ

4頂点が左回りか右回りかを考えるのは結構複雑でした。
しかしながら大抵のアルゴリズムは先人が考えつくしています。
基本的には自分で考えるより先人の知恵を使うべきですが、必ずしも見つけられるとは限らないのが悩みどころです。
github.com