平面上の3点を通過する円（三角形の外接円とも言える）が、内に原点を含むかどうかを判定する方法を整理しておきます。この判定は例えばドロネー三角形分割（Delaunay Triangulation）において重要な役割を果たします。「反転変換」を使うことによりこの判定式が非常にスッキリと理解できることが分かったので、その感動を忘れない内に備忘録として記事化しておきます。（およびご教示くださった方への報告の意味もあります）
命題
平面上の3点 $a=(a_x, a_y), b=(b_x, b_y), c=(c_x, c_y)$ を通過する円が、内に原点を含む条件は次式で与えられる。
\det\left(\begin{array}{ccc}
1 & a_x & a_y \\
1 & b_x & b_y \\
1 & c_x & c_y
\end{array}\right)\cdot\det\left(\begin{array}{ccc}
||a||^2 & a_x & a_y \\
||b||^2 & b_x & b_y \\
||c||^2 & c_x & c_y
\end{array}\right) > 0
きっかけとか経緯とか
発端は下記のツイートです。自分が過去に書いたコードにこの判定式が書かれていたのですが、自分で意味が分からなくなって解きなおしました。（過去の自分はこの式を自分で導出したのか、どこかから写したのか、今となっては忘れてしまいました…）
自分で書いたソースコードの意味が本気で分からなくなって、今解き直した。三角形の外接円に与えられた点が含まれるか判定する処理。式が簡潔すぎて魔法のように思えた。昔の俺天才か。（ちゃんとドキュメントに残しておかないとダメだこれ）
— てらだ (@u_1roh) July 24, 2019
しかし、コツコツと地道に計算すれば確かにこの式が得られたのですが、腑に落ちる感じがありませんでした。
この式はとてもシンプルで対称性があり、美しく、どこか意味ありげです。もっと図形的な直観でこの式を捉えることは出来ないのかなぁとモヤモヤしていたところ、答えを教えていただきました。
こんなのどうです？ pic.twitter.com/wrsKc5Hn03
— Kenji Hiranabe (@hiranabe) July 27, 2019
@hiranabe さんが「反転変換」という答えを教えてくれました。大変ありがとうございました。これが自分の中でブレークスルーとなって、この式がスッキリと腑に落ちるようになりました。とても心地よい体験だったので、ここに整理しておきます。
まずは泥臭い導出から
本記事の目的は「反転変換」というものを使って冒頭の判定式をスッキリと理解することですが、まずは反転変換を使わずに泥臭く計算して導出しておきます。（先が気になる人は読み飛ばしても大丈夫です。）
まず前提として、「3点 $a, b, c$ は反時計回りに並んでいる」という条件を仮定します。これは次のように定式化できます。
\begin{array}{cc}
& \det(b - a, c -a) > 0 \\
\Leftrightarrow & \det(a, b) + \det(b, c) + \det(c, a) >0 \\
\Leftrightarrow & \det\left(\begin{array}{ccc}
1 & a_x & a_y \\
1 & b_x & b_y \\
1 & c_x & c_y \\
\end{array}\right) > 0 \\
\Leftrightarrow & \det(a, b, c) > 0
\end{array}
ただし、最後の式では次の記法を導入しました。この記法は便利なので今後も使います。
\det(p, q, r) := \det\left(\begin{array}{ccc}
1 & p_x & p_y \\
1 & q_x & q_y \\
1 & r_x & r_y \\
\end{array}\right), \quad p, q, r\in R^2
次に外接円の中心座標（外心）$q$ を求めます。これは辺$ab$の垂直二等分線と辺$ac$の垂直二等分線の交点として与えられます。すなわち：
- $p$ を辺$ab$に正射影すると辺$ab$の中点となる
- $p$ を辺$ac$に正射影すると辺$ac$の中点となる
これを式で表すと、
(\frac{b - a}{||b - a||}, q - a) = \frac{1}{2}||b - a|| \\
(\frac{c - a}{||c - a||}, q - a) = \frac{1}{2}||c - a|| \\
ここで行列 $A$ を次のようにおいて
A = \left(\begin{array}{c}(b - a)^t \\ (c - a)^t\end{array}\right)
整理すると次の連立方程式が得られます。
Aq = \frac{1}{2}\left(\begin{array}{c} ||b||^2-||a||^2 \\ ||c||^2-||a||^2 \end{array}\right)
$A$ の逆行列を求めましょう。まず行列式は次式で与えられます。
$$
\det A = \det(b - a, c - a) = \det(a, b) + \det(b, c) + \det(c, a) = \det(a, b, c)
$$
したがって逆行列は次式となります。
A^{-1} =\frac{1}{\det(a, b, c)}\left(\begin{array}{cc}
c_y - a_y & -b_y + a_y \\
-c_x + a_x & b_x - a_x
\end{array}\right)
ここで90度回転を表す行列を次のように定義すれば、
R_{90} =\left(\begin{array}{cc}
0 & -1 \\
1 & 0
\end{array}\right)
逆行列は次のように整理できます。
A^{-1} = \frac{1}{\det(a, b, c)}R_{90}\left(a-c\quad b-a\right)
これを用いて外心を解くと、次式が得られます。
q = \frac{1}{2\det(a, b, c)}R_{90}\left\{
(||b||^2 - ||c||^2)a + (||c||^2 - ||a||^2)b + (||a||^2 - ||b||^2)c
\right\}
いよいよ、外接円に原点が含まれる条件を求めましょう。これは $||q||$ が外接円半径よりも小さいという条件で与えられます。すなわち：
||q||^2 < ||q - a||^2 \\
\Leftrightarrow 2(q, a) < ||a||^2
ここで、$\forall u, v\in R^2$ に対して
(R_{90}u, v) = \det(u, v)
が成り立つことに注意すると、左辺は次のように計算できます。
2(q, a) =\frac{1}{\det(a,b,c)}\left\{
(||c||^2-||a||^2)\det(b, a) + (||a||^2-||b||^2)\det(c, a)
\right\}
$\det(a,b,c)>0$ を仮定しているから、次のように不等号の向きを変えずに分母を払うことが出来ます。
\begin{array}{cc}
& (||c||^2-||a||^2)\det(b, a) + (||a||^2-||b||^2)\det(c, a) <
||a||^2(\det(a, b) + \det(b, c) + \det(c, a)) \\
\Leftrightarrow &
||a||^2\det(b, c) + ||b||^2\det(c, a) + ||c||^2\det(a, b) > 0 \\
\Leftrightarrow &
\det\left(\begin{array}{ccc}
||a||^2 & a_x & a_y \\
||b||^2 & b_x & b_y \\
||c||^2 & c_x & c_y
\end{array}\right) > 0
\end{array}
目的の式が得られました。
ただこれだと、「頑張って計算したら出た」というだけで、どこか腑に落ちない感じがしませんか。そこで反転変換です。
反転変換とは
反転変換というものについて簡単に紹介していきます。次のような変換を反転変換といいます。
$$
x' = \frac{x}{||x||^2}
$$
この変換では $||x||||x'||=1$ が成り立ちます。
これがどういう変換かをざっくり言葉で説明すると、「単位円 $||x||=1$ の内側の世界と外側の世界をぐるんと反転させて入れ替える」感じです。
- 単位円上の点はこの変換の前後で動きません（つまり不動点）。
- 単位円の内側の点は外側に写ります。
- 単位円の外側の点は内側に写ります。
- 原点に漸近する点列を写すと無限遠に向かって発散します。
- 逆に無限遠に向かっていく点列を写すと原点に収束します。
例えばこのへん https://mathtrain.jp/hanten とかに説明があります。他にもググればたくさん記事が見つかります。
円の反転変換
反転変換は、円を円に写すという特徴があります。ただし原点を通る円は直線に写ります。このことを導出して確かめておきます。
まず、中心座標 $q$、半径 $r$ の円は次式で表されます。
$$ ||x - q||^2 = r^2 $$
これに反転変換を施し、$x$ を $x/||x||^2$ に置換します。（本当は $x=x'/||x'||^2$ とするべきですが、真面目に書くと式がダッシュだらけになって見づらいので横着しています。）
\begin{array}{ll}
& \left|\left|\frac{x}{||x||^2} - q\right|\right|^2 = r^2 \\
\Leftrightarrow & ||x - ||x||^2q||^2 = r^2||x||^4 \\
\Leftrightarrow & ||x||^2 -2(x, q)||x||^2 + ||x||^4||q||^2 = r^2||x||^4 \\
\Leftrightarrow & 1 - 2(x, q) + ||x||^2||q||^2 = r^2||x||^2 \\
\Leftrightarrow & (||q||^2 - r^2)||x||^2 - 2(x, q) + 1 = 0
\end{array}
ここで $r=||q||$ と $r\neq||q||$ の場合分けが必要になります。これはつまり、元の円が原点を通過するケースとそうでないケースの場合分けになります。
円が原点を通過する場合
$r=||q||$ を代入すると次式が得られます。
$$ 2(x, q) = 1 $$
これは直線の式です。つまり、原点を通過する円を反転変換すると直線に写ることが確かめられました。
円が原点を通過しない場合
$||q||^2-r^2$で両辺を割って整理すると次式が得られます。
\begin{array}{ll}
& ||x||^2 - 2\frac{(x, q)}{||q||^2 - r^2} + \frac{1}{||q||^2-r^2} = 0 \\
\Leftrightarrow & \left|\left|x - \frac{q}{||q||^2-r^2}\right|\right|^2 = \left(\frac{r}{||q||^2-r^2}\right)^2 \\
\end{array}
これは中心位置 $q/(||q||^2-r^2)$、半径 $r/(||q||^2-r^2)$ の円を表す式です。つまり、（原点を通過しない）円を反転変換すると円に写ることが確かめられました。
原点を含む円は、原点を含む円に写る
元の円 $||x-q||=r$ が原点を含む条件は $||q||<r$ です。同様に反転変換後の円が原点を含む条件を考えると、
\begin{array}{cc}
& \left|\left|\frac{q}{||q||^2-r^2}\right|\right| < \frac{r}{||q||^2-r^2} \\
\Leftrightarrow & ||q|| < r
\end{array}
が得られるので、円が原点を含むかどうかは反転変換の前後で変わらない、ということが分かります。
以上の関係はn次元で成り立つ
上記の導出では平面上の円を変換すると説明しましたが、実は導出過程の式はベクトルが2次元であることに依存していません。つまりこの反転変換の性質はn次元空間に拡張できて、n次元空間におけるn次元球面は反転変換によって球面に写る（ただし原点を通る球面はn次元超平面に写る）、と一般化出来ます。（ただしこの一般化は以下では使いません）
反転変換で判定式を理解する
ではいよいよ、反転変換を使って冒頭の判定式を解きほぐしていきます。ここでの目的は厳密な証明を与えることではなく、図形的な直観を働かせて判定式が「腑に落ちる」ことを目標とします。
まず3点 $a, b, c$ を次のように反転変換します。
$$ a'=\frac{a}{||a||^2},\quad b'=\frac{b}{||b||^2},\quad c'=\frac{c}{||c||^2} $$
ここで簡便のために次の表記を導入します。
\det(p, q, r) := \det\left(\begin{array}{ccc}
1 & p_x & p_y \\
1 & q_x & q_y \\
1 & r_x & r_y
\end{array}\right), \quad p, q, r\in R^2
すると外接円が原点を含む条件式は次のように書けます。
\det(a, b, c)\cdot\det(a', b', c')>0
つまり外接円が原点を含む条件は、「反転変換の前後で行列式の符号が等しいこと」と言い換えられます。
以上を踏まえて、図を用いて視覚的にこの式の意味を読み解いてみましょう。
図で理解する
下図を見てください。
- 緑の円は単位円です。この円は反転変換で動かない不動点です。
- 青の円は原点を通過する円です。
- 青の円を反転変換すると、赤い直線が得られます。
青い円から任意に3点 $a, b, c$ を取り、それらを反転変換するとすべて赤い直線上に写ります。つまり、反転変換後の点を $a', b', c'$ とすると次式が成り立ちます。（$b'-a'$ と $c'-a'$ が一次従属になることから）
$$ \det(a', b', c') = 0 $$
外接円が原点をちょうど通過するケースでこの行列式がゼロになるのですから、外接円が原点を含むかどうかはこの行列式の符号で判定できそうです。でも現段階では、符号がどちらになるのか判断つきません。
試しに青い円を少し拡大してみます（下図）。青い円が原点を含むようになりました。これを反転変換すると赤い円になります。赤い円も原点を含んでいます。これは、前節で示した反転変換の性質「原点を含む円は原点を含む円に写る」に合致していることに注目してください。
逆に青い円を縮小すると下図が得られます。「原点を含まない円は原点を含まない円に写る」ことが視覚的に分かります。
しかし、これだけではまだ符号の問題は解決しません。円周を回る向きの考察が必要です。
青い円の上を反時計回りに辿ったときに、反転変換後の点（赤い円上の点）がどういう向きに回るかを考えてみてください。上の2つの図で考えると、次のことに気づきます。
- 円が原点を含む場合、青い円と赤い円は同じ向きに回る
- 円が原点を含まない場合、青い円と赤い円は逆向きに回る
次のように言い換えた方が反転変換の直観的イメージに近いかもしれません。
- 円が原点を含む場合、反転変換しても円は裏返らない。
- 円が原点を含まない場合、反転変換で円は裏返る。
以上で必要な材料が出揃いました。
結論
円周上に3点 $a, b, c$ を取ったときに、これが時計回りか反時計回りかを判定するには、行列式 $\det(a, b, c)$ の符号を調べれば良いのでした。つまり、この符号が反転変換の前後で変わらないとき、円が反転変換で裏返らない、すなわち原点を含むと結論されます。
以上により、外接円が原点を含む条件は次式となります。
\det(a, b, c)\cdot\det(a', b', c')>0