モンテカルロ法で面積を求めてみる(C# WinForms)
SF小説『三体』の三部作は数年前に読了しましたが、最近は少しずつ読み返していて、再びモンテルカルロ法が目に入りました。
不規則な形状の面積を求めるときに乱数を使う方法として本に登場しました。
調べてみたら、結構いろいろな領域で広く使われている方法で、私にとっては難しいのですが、本当に面積を求められるかどうか、素人なりに検証してみようと思いました。
目次
『三体』に出たモンテカルロ法とは
原文の引用はここで省略するとして、私の理解では大体こんな感じです：
不規則な形状の面積を求めるには、まずその形状を形の規則な範囲内に置いて、その範囲内に向けてランダムにボールを投げる。ひとつの点には最大1回投げられる。ある一定数を投げた後に、形状内と形状外に落ちたボールの数を統計して、その数の比率で面積を計算する。
つまり、計算式はこうなります：
形状の面積 = 範囲の面積 × 形状内ボール数 / 投げたトータルボール数
一般的に、不規則な形状の面積を求めるには、それを出来るだけ数多くの規則な形状に切り分けて、積分で計算する方法だと思いますが、モンテカルロ法は確率を利用するので、自分にとっては新鮮です。
『三体』アマゾンページシミュレーション用のC#でアプリを作成
早速こんなアプリを作りました。WinForms@.Net 6です。
主に以下の機能があります：
-
形状を生成する機能
テストのために300 x 300ピクセルの正方形と、ランダムに不規則な形状を生成する２つの機能があります。正方形生成ソースコード
private void FillRect(int wid, int hei, Graphics g) { int x = new Random().Next(0, picBox.Width - wid); int y = new Random().Next(0, picBox.Height - hei); g.FillRectangle(new SolidBrush(shapeColor), x, y, wid, hei); }不規則な形状生成ソースコード
private void FillRandomShape(Graphics g, int pointQty) { Point[] points = new Point[pointQty]; for (int i = 0; i < pointQty; i++) { int x = new Random().Next(0, picBox.Width); int y = new Random().Next(0, picBox.Height); points[i] = new Point(x, y); } g.FillClosedCurve(new SolidBrush(shapeColor), points); } -
形状の容器であるBitmapのすべてのピクセルを逐一チェックして、形状の面積を算出する機能
ソースコード
private async Task<int> CalcAreaDotByDot() { int area = 0; if (picBox.Image != null) { Bitmap bmp = (Bitmap)picBox.Image; await Task.Run(() => { for (int w = 0; w < bmp.Width; w++) { for (int h = 0; h < bmp.Height; h++) { Color color = bmp.GetPixel(w, h); if (color.Equals(shapeColor)|| color.Equals(shapeColorAlt)) { area++; } } } }); } return area; } -
形状にランダムにドットを打って、モンテカルロ法で面積を求める機能
ソースコード
private async Task<int> CalcAreaMonteCarlo() { int area = 0; if (picBox.Image != null) { Bitmap bmp = (Bitmap)picBox.Image; int totalPxl = bmp.Width * bmp.Height; int insidePxl = 0; int outsidePxl = 0; List<Point> lstUsedPt = new List<Point>(); int samples = (int)numSamples.Value; int times = (int)numTimes.Value; for (int t = 0; t < times; t++) {//実施回数 await Task.Run(() => { for (int s = 0; s < samples; s++) {//「投げる」ドット数 int x = new Random().Next(0, bmp.Width); int y = new Random().Next(0, bmp.Height); Point pt = new Point(x, y); if (lstUsedPt.Contains(pt)) {//1回「投げられた」ドットならやり直し s--; continue; } else { lstUsedPt.Add(pt); Color color = bmp.GetPixel(x, y); if (color.Equals(shapeColor) || color.Equals(shapeColorAlt)) {//形状内に落ちた場合 insidePxl++; //投げられたドットの色を変える bmp.SetPixel(x, y, shapeColorAlt); } else {//形状外に落ちた場合 outsidePxl++; bmp.SetPixel(x, y, Color.Red); } } } }); lstUsedPt.Clear(); picBox.Refresh(); } //面積を計算する double ratioInside = Convert.ToDouble(insidePxl) / Convert.ToDouble(insidePxl + outsidePxl); area = Convert.ToInt32(totalPxl * ratioInside); } return area; }
まず正方形で試してみる
モンテカルロ法で計算するまえに、全ドットを調べる方法がちゃんと動作しているかどうかを試すために、300 x 300ピクセルの正方形を生成して計算してみます。
「投げるボール」(ピクセル)数は100で、1回のみ実施します。
まず、全ピクセルチェックの方法では、ちゃんと90,000ピクセルになっていますので、面積の求め方自体は問題なさそうです。
そして、モンテカルロ法での計算結果は結構ばらつきます。10回の計算では正解との差は3.2%-34.33%の区間に分布します。
次は不規則な形状が登場！
さて、不規則な形状を生成して、いくつかの条件でテストしてみました。
テスト条件による誤差結果
| テスト# | 5,000個1回 | 500個10回平均 | 100個50回平均 | 1,000個100回平均 |
|---|---|---|---|---|
| 1 | 2.96% | 1.58% | 1.51% | 0.82% |
| 2 | 2.34% | 1.07% | 4.35% | 0.22% |
| 3 | 1.19% | 0.45% | 5.62% | 0.16% |
| 4 | 1.46% | 0.95% | 3.16% | 0.59% |
| 5 | 2.78% | 2.65% | 0.45% | 0.20% |
| 6 | 0.50% | 0.07% | 3.84% | 0.60% |
| 7 | 0.31% | 1.77% | 1.70% | 0.34% |
| 8 | 1.14% | 1.26% | 2.52% | 0.49% |
| 9 | 0.25% | 1.00% | 3.71% | 0.13% |
| 10 | 1.13% | 2.71% | 1.19% | 0.52% |
結論
このような手軽なテストでは結論を付けられませんが、自分の直感としては：
- 投げるボール数が多いほど正確である(テスト結果は省略)
- 投げるボール数が一定で、実施回数が多いほど、一定のバランスまで正確になる傾向があるが不安定。ボール数が極端に少ないと、回数を増やしても正確率が低い。ただ、そもそもランダムなので、ただの偶然の可能性がある
- 誤差と完全なはずれが許容され、スピーディーに参考面積を求めるシーンでは便利かもしれない
感想
良い遊びでした。
自分にとっては、まだどこでどう使うかとかはないのですが、数学或いはアルゴリズムの問題より、少し哲学に近いものと感じました。
ランダムとは何か？ と考えさせられました。ランダムはなぜある区域に集中せずにこんなにまんべんなく均等に分布するのか、そもそもプログラミング言語のRandom関数等は本当のRandomなのか、いろいろ不可解なことが多いです。
あまり深堀できませんが、多種多様な知識を吸収しながら楽しんでいきたいと思います。
コメント
コメントを投稿
個人情報を記入しないようご注意ください