[C#]角度によるソート

ランダムに打たれた点の集合Gのような入力あって、点Pが与えられたとき。
集合Gを、点Pを中心とした角度で並び替えたい。

何に使うかどうかはさておき、ちょっと何かの拍子に考えてしまったのでここに書いておきます。

・角度の求め方

まず角度の算出方法。
こちらを参照。

直線（ベクトル）の角度を求める
http://www.sm.rim.or.jp/~shishido/sheeta.html

単発で角度を求める分にはこれで問題ないようです。

角度を求めてそれを手がかりにソートさせれば、きっと想定する結果が求められそうはあります。
しかし、角度計算に使用する、アークサインも平方根の式もかなりの負荷となることは自明なので、少し考える。
そしてすぐに、単に外積を使えばできるのではと思い始める。

・C#における配列のソートの仕方

ソートに使用される比較方法を独自に指定するには、ListのSortメソッドに、IComparableを指定してあげます。
詳しくはこちら。

配列やコレクション内の要素を並び替える
http://dobon.net/vb/dotnet/programing/icomparer.html

取り出した二つの点を比較して、どちらが進行方向に向かってるのかの順序が判定できればいいだけです。
集合Gの任意の2点と点Pとのベクトルの外積の値が、正を持つのか負を持つのかで、どちら回りになっているのかが判定できるわけです。

ということで、実装してみる。

●角度でソート

//
private PointF p = PointF.Empty; // ←点P
private List<PointF> list = null; // ←集合G

private Random r = null; // 乱数作成用


private void Form1_Load(object sender, EventArgs e) {
    r = new Random();
    
    // 点Pと集合Gを作成する
    p = GetRandomPoint();
    list = CreatePointList();
    
    list.Sort(Compare); // ソート
    
    // これを描画するコードは省いています。
}

// 集合Gを作る
private List<PointF> CreatePointList(){
    List<PointF> l = new List<PointF>();
    for (int i = 0; i < 40; i++) {
        l.Add(GetRandomPoint());
    }
    return l;
}

// ランダムに点をつくる
private PointF GetRandomPoint() {
    int w = this.ClientRectangle.Width;
    int h = this.ClientRectangle.Height;
    return new PointF(r.Next(w), r.Next(h));
}

// 角度比較のためのコードはこれだけ
private int Compare(PointF a, PointF b) {
    return (int)((a.X - p.X) * (b.Y - p.Y) - (b.X - p.X) * (a.Y - p.Y));
}

なお描画部分のコードは省いています。
ソート部分、仰々しいコードが必要かと思ったけれど、わりと簡潔に書けたのはよいこと。演算だけでよいなんて魔法のようです。
実行結果。下に仕上がりをざっと並べました。

before（ソート前）	after（ソート後）

思いのほか爆発の吹き出しのような感じにならなかった。けれど、それは当然。普通に均等に点を配置しても、そもそも爆発の吹き出しの感じにはならないからでした。（三つ目の図形は人為的なものです）

できたけれど、はっきりいってこの比較方法では前も後ろもないわけで、ループするんじゃないの？と思っていたわけです。
でもループせずにうまくいきました。なんなんだろう。このあたりは留意事項。

●ランダムにソート

ちなみに、配列をぐちゃぐちゃにするほうは、戻り値を乱数にしてしまえばよろしいです。
簡単に書ける分、高速なやりかたではありませんので悪しからず。

// private Random r = new Random();
private int RandomCompare(PointF a, PointF b) {
    return r.Next(); // 乱数を返す
}

週末ラボ

2011/03/25