[Visual Stadio2019]100個の点群からの凸包を生成したい

Question

###わからないこと
プログラムで平面上にランダムに100個の点を表示させて、その凸包を描画するプログラムを作成したいが、色々と調べて言葉としてはわかるものの、プログラムの部分でどのように実現させればいいかわからない。

###現在の解釈
凸包の領域は、辺を半時計回りに廻った場合、常に各辺の左側になる。
⇒ある点が凸包内部にあるか判断ができる。

x成分が最高値の点を出す。
↓
その点から各点へのベクトルのうち、y軸方向と最も角度が小さいものを探す。
↓
辺と各点へのベクトルのうち角度が小さいものを探して繰り返せばできる？

###サンプルコード
現在課されたお題にサンプルコードが上がったので記載しておきます。

using FK_CLI;
using System;


namespace Kadai5_1
{
    class Program
    {
        static void Main(string[] args)
        {
            // ウィンドウの生成
            var window = new fk_AppWindow();
            window.Size = new fk_Dimension(600, 600);
            window.BGColor = new fk_Color(1.0, 1.0, 1.0);
            window.TrackBallMode = true;
            window.Open();

            // 点群配列作成
            var posArray = new fk_Vector[100];
            var point = new fk_Point();
            for (int i = 0; i < 100; i++)
            {
                // x,y成分を -25～25までのランダムに設定する。
                posArray[i] = new fk_Vector(fk_Math.DRand(-25.0, 25.0), fk_Math.DRand(-25.0, 25.0), 0.0);
                // point変数に頂点を追加
                point.PushVertex(posArray[i]);
            }

            // 点群表示用モデルの準備
            var pointModel = new fk_Model();
            pointModel.Shape = point;
            pointModel.PointColor = new fk_Color(0.0, 0.0, 0.0);
            pointModel.PointSize = 2.0;
            window.Entry(pointModel);

            // 線分群表示用モデルの準備
            var line = new fk_Line();
            var lineModel = new fk_Model();
            lineModel.Shape = line;
            lineModel.LineColor = new fk_Color(0.0, 0.0, 1.0);
            window.Entry(lineModel);

            

            // 両端点の位置ベクトルを指定して線分を追加
            for (int i = 1; i < posArray.Length; i++)
            {
                line.PushLine(posArray[0], posArray[i]);
            }

            while (window.Update() == true)
            {
            }
        }
    }
}

Answer 1

現在の解釈

素朴な実装は、それでいいんじゃないですかね？（私は数学はからっきしですが^^;

意味は分かるがコードが思いつかないということだったら、↓に擬似コードがあります。C#に翻訳することも容易かと思います。
ギフト包装法 - Wikipedia

---

そもそも日本語で検索しても、いくつかは見つかりました。
凸包 アルゴリズム C# - Google 検索

日本語では物足りない場合は、英語で検索してください。
Convex hull algorithm C# - Google 検索

各アルゴリズムの説明・詳細なベンチマーク・C#実装時の注意点等、非常によい記事だと思います。
Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h) - CodeProject

Comments

[GReBan]

たくさんの参考ページありがとうございます！

英語での検索はしてなかったので、参考にさせていただきます！