ラングレーの問題ソルバー

ここんとこ組み込みの話ばかりしていましたが、一応プログラミングのブログということで、今度はパソコン上で動くアプリケーションのプログラミングの話をしていきます。

ラングレーの問題という問題があります。

ラングレーの問題 - Wikipedia

はい。中学だか高校だかで一度は見たことある図形ですね。
各々の角度を計算して書きこむだけでは答えが出ないので、何か補助線を引いたり、何かしらの図形の相似を証明するなどしながら解いていかなければいけないので、結構難問として図形を覚えてる人もいるかと思います。

このラングレーの問題、別にこの形のこの角度である必要はどこにもなく、底辺の1本の線分に対してそれぞれの頂点から2本線を生やして交点をいい感じに結べばそれはラングレーの問題になるっぽいです。特に、それぞれの角度を10°の倍数にしておいたらいい感じに求める角xも10°の倍数になる問題が100以上もできるそうです。すごいですねー。

昨日出会ったのはこの問題でした。

(a,b,c,d)=(10°,70°,60°,20°)です。解いてみるとさっぱりわかりません。
結局、このような神がかった補助線を引くことで答えが出るらしいです。

はい。点Eは△DBCの外心、点Fは△ABCの内心です。点EはAC上に乗り、点D,E,Fは一直線に並びます。そして点D,A,F,Cは同一円周上に乗るので、ゴニョゴニョ計算してやると∠ADBが求まるわけです。こんなの思いつかねえよ…。

ところで、このラングレーの問題、神がかった補助線を思いつくかどうかは別問題として、線分BCの両端から生える線と線分BCのなす角を固定してやれば、点A,B,C,Dの位置は確定するので、力技で角度を求めることができるようになります。
ということは、コンピューターで答えを計算したくなりますよね？なってください。

早速ソフトを書いてみました。

パソコン上で動作するアプリケーションを開発するときは、私はいつもC#+WPF+Livetで作っちゃいます。そして、たいてい便利なコントロールを導入するためにExtended WPF Toolkitを入れます。
Livetはプロジェクトテンプレートを簡単にインストールできますし、Extended WPF ToolkitはNugetから簡単にインストールできます。とても便利です。

そしてこのようなウィンドウができました。右のプロパティ設定欄のInput Angleに4つの角度を入力するだけで、角度xを計算して表示してくれます。

計算はとても簡単です。
まず、図を描画するためにも、点Aと点Dの座標を計算します。
線分AB、線分DBの長さが分かれば後は角度のサインやコサインを掛けてやれば座標は出るのでその線分を求めればいいのですが、この線分は正弦定理を使うとすぐに求まります。
座標がわかってて角度を求めたかったら、ベクトルの内積ですよね。DBベクトルとDAベクトルの内積を取って、DBベクトルの長さとDAベクトルの長さで割って、arccos取ったら∠ADBが出てきます。
やっているのはそれだけのことです。

PointB = new Point() { X = 0, Y = 0 };
PointC = new Point() { X = BaseLineLength, Y = 0 };

double diameter = BaseLineLength / Math.Sin(DegToRad(180 - (AngleA + AngleB + AngleC)));
double length = diameter * Math.Sin(DegToRad(AngleA + AngleB));
PointA = new Point() {
    X = PointC.X - length * Math.Cos(DegToRad(AngleC)),
    Y = PointC.Y - length * Math.Sin(DegToRad(AngleC))
};

diameter = BaseLineLength / Math.Sin(DegToRad(180 - (AngleB + AngleC + AngleD)));
length = diameter * Math.Sin(DegToRad(AngleC + AngleD));
PointD = new Point() {
    X = PointB.X + length * Math.Cos(DegToRad(AngleB)),
    Y = PointB.Y - length * Math.Sin(DegToRad(AngleB))
};

const double margin = 20;

Point LeftTop = new Point() {
    X = Math.Min(Math.Min(PointA.X, PointB.X), Math.Min(PointC.X, PointD.X)) - margin,
    Y = Math.Min(Math.Min(PointA.Y, PointB.Y), Math.Min(PointC.Y, PointD.Y)) - margin,
};
Point RightBottom = new Point() {
    X = Math.Max(Math.Max(PointA.X, PointB.X), Math.Max(PointC.X, PointD.X)) + margin,
    Y = Math.Max(Math.Max(PointA.Y, PointB.Y), Math.Max(PointC.Y, PointD.Y)) + margin,
};

Vector VectorDB = Vector.FromPointDifference(PointD, PointB);
Vector VectorDA = Vector.FromPointDifference(PointD, PointA);

AnswerAngle = RadToDeg(Math.Acos(VectorDB.DotProduct(VectorDA) / VectorDA.Length / VectorDB.Length));

計算はこんなかんじです。
WPFはY軸が下へ行くと大きくなるので、その点だけ注意してください。
PointクラスやVectorクラスも同時に実装しちゃいましたが、そんな大した実装じゃないですし、C#なのでこのコードを見れば何をやっているかはわかると思います。

<Line Stroke="{Binding LineBrush}" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointA.X}" Y1="{Binding PointA.Y}"
  X2="{Binding PointB.X}" Y2="{Binding PointB.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointB.X}" Y1="{Binding PointB.Y}"
  X2="{Binding PointC.X}" Y2="{Binding PointC.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointC.X}" Y1="{Binding PointC.Y}"
  X2="{Binding PointD.X}" Y2="{Binding PointD.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointD.X}" Y1="{Binding PointD.Y}"
  X2="{Binding PointA.X}" Y2="{Binding PointA.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointB.X}" Y1="{Binding PointB.Y}"
  X2="{Binding PointD.X}" Y2="{Binding PointD.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointC.X}" Y1="{Binding PointC.Y}"
  X2="{Binding PointA.X}" Y2="{Binding PointA.Y}" />

描画のほうはもちろんXAMLに記述しています。
Polylineでやったほうがスマートだったかもしれませんが、なんていうか、この図形は一筆書きできないので、そういう観点からしたらPolyline使うのもなーって感じだったので、まあとりあえずLineにしておきました。

座標や角度の計算とWPFの描画に関わることはこのへんですかね。

まあ、他にもPropertyGridを使うためのプログラムや、LayoutTransformを使った図形の拡大縮小、各頂点や角の名前を表示するためのプログラム等々書きましたが、ラングレーの問題とその図形の本質ではあまりないので、今回は省略します。
またなにか機会があったら記事にしてみようかなって思います。はい。

こういうちょっとしたプログラムって大したこと無いんで、ソースコードからソフトまで丸々公開しちゃってもいいんですけど、他人が作ったライブラリ使ってるといろいろと面倒なんですよね…。ライセンスを熟読しなきゃいけませんし、どんなにゆるいライブラリでも、「アプリ内のどこかにこのソフトウェアのThanksみたいなのを書いてね」っていうものが結構あったりしますし、今回使っているExtended WPF Toolkitはまさにそれです。
つまり、公開するためにはわざわざAboutダイアログを作らなきゃいけないんですね…。そこまで熱意を持って作ってるソフトでもなしにそこまでやるのはなかなか大変だったりします…。はい…。

余談

上の方の図で補助線を引いたものも用意しましたが、これもせっかくなんでWPFで全部補助線を描いてみました。
直線の補助線は、まあ計算しやすい座標を適当に計算して結べばいいだけですが、円はなかなかめんどくさかったですね。
円の方程式を一般形で記述します。\[x^2+y^2+lx+mx+n=0\]これに、円が通る点のうち3点の座標を代入してやればl,m,nが求まるわけですが、それはすなわち3元1次方程式なので、コンピューターで計算するには行列を計算させるのがスマートですね。\[\begin{pmatrix} x_1 &y_1 &1 \\ x_2 &y_2 &1\\ x_3 &y_3 &1 \end{pmatrix}\begin{pmatrix} l \\m \\n \end{pmatrix}=\begin{pmatrix} -x_1^2-y_1^2 \\-x_2^2-y_2^2 \\-x_3^2-y_3^2 \end{pmatrix}\]この行列に関して左側から逆行列をぶつけてやれば一発でl,m,nが求まります。しかし、どうもC#は算術計算のための行列ライブラリっていうのは標準で提供してないっぽいですね…。算術計算のための座標、ベクトルライブラリみたいなのも無くて今回は適当に実装しましたし、その辺は改善してもらいたいところです。
はい。3x3の逆行列を求めるプログラムまで実装していては気が遠くなってしまいます。掃き出し法だの何だのあったと思いますが、やってられません。というわけで、 このあたりのライブラリを使用させてもらいました。

C# .NET Generic Matrix Maths Library

というわけで、補助線部分のプログラムはこんなかんじになっています。

PointE = new Point() {
    X = PointC.X - BaseLineLength * Math.Cos(DegToRad(AngleC)),
    Y = PointC.Y - BaseLineLength * Math.Sin(DegToRad(AngleC)),
};
Point2E = PointE - PointD + PointE;

diameter = BaseLineLength / Math.Sin(DegToRad(180 - (AngleC / 2 + 40)));
length = diameter * Math.Sin(DegToRad(40));
PointF = new Point() {
    X = PointC.X - length * Math.Cos(DegToRad(AngleC / 2)),
    Y = PointC.Y - length * Math.Sin(DegToRad(AngleC / 2)),
};

DoubleMatrix m1 = new double[,] {
    { PointD.X, PointD.Y, 1 },
    { PointA.X, PointA.Y, 1 },
    { PointC.X, PointC.Y, 1 },
};
DoubleMatrix m2 = new double[,] {
    { -PointD.X * PointD.X - PointD.Y * PointD.Y },
    { -PointA.X * PointA.X - PointA.Y * PointA.Y },
    { -PointC.X * PointC.X - PointC.Y * PointC.Y },
};

DoubleMatrix res = m1.Inverse * m2;

double Radius = Math.Sqrt(res[0, 0] * res[0, 0] / 4 + res[0, 1] * res[0, 1] / 4 - res[0, 2]);
CircleDiameter = Radius * 2;
CircleLeft = -res[0, 0] / 2 - Radius;
CircleTop = -res[0, 1] / 2 - Radius;

doubleの2次元配列をそのまま行列に変換できて便利なライブラリですね。
これで円の中心の座標と半径が求まりますが、WPFで楕円を描画するのに必要なのは幅、高さ、左上の座標なので、直径と左上の座標を計算しています。

<Line Stroke="{Binding LineBrush}" StrokeDashArray="1 2" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointD.X}" Y1="{Binding PointD.Y}"
  X2="{Binding Point2E.X}" Y2="{Binding Point2E.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeDashArray="1 2" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointE.X}" Y1="{Binding PointE.Y}"
  X2="{Binding PointB.X}" Y2="{Binding PointB.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeDashArray="1 2" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointC.X}" Y1="{Binding PointC.Y}"
  X2="{Binding PointF.X}" Y2="{Binding PointF.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeDashArray="1 2" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointB.X}" Y1="{Binding PointB.Y}"
  X2="{Binding PointF.X}" Y2="{Binding PointF.Y}" />
<Line Stroke="{Binding LineBrush}" StrokeDashArray="1 2" StrokeThickness="{Binding LineThickness}" StrokeEndLineCap="Round"
  X1="{Binding PointA.X}" Y1="{Binding PointA.Y}"
  X2="{Binding PointF.X}" Y2="{Binding PointF.Y}" />
<Ellipse Stroke="{Binding LineBrush}" StrokeDashArray="1 2" StrokeThickness="{Binding LineThickness}"
         Canvas.Left="{Binding CircleLeft}" Canvas.Top="{Binding CircleTop}" Width="{Binding CircleDiameter}" Height="{Binding CircleDiameter}" />

補助線は点線にするために、StrokeDashArrayというプロパティに値を入れています。
WPFはこんなふうにかなり柔軟に点線が引けるんですね。驚きました。

これでめでたく補助線が引けました。

あ、これ、問題の角度が変わってくると解き方も全くもって変わるので、この補助線が使えなくなることはお間違え無きよう。