外接円内の点かどうかを調べる

はじめに

ドロネー法などでは外接円内にある点が含まれるかどうかの判定を行います。外接円内に点が含まれるかどうかの判定は最終的には行列式を用いた美しい公式 (参考：点が三角形外接円内側か判定したい - Thoth Children http://www.thothchildren.com/chapter/5bdedb4341f88f267247fdd6) で判定できるがその証明をここで行います。
前提として、以下の図のような状況を考えます.

外接円の中心と半径の求め方

外接円の中心は三角形の頂点との距離がすべて等しくなるような点であるから、

OP^2 = PA^2 \\
OP^2 = PB^2

となります。したがって、

x_p ^2 + y_p^2 = (x_1 - x_p)^2 + (y_1 - y_p)^2\\
x_p ^2 + y_p^2 = (x_1 - y_p)^2 + (y_2 - y_p)^2

これを整理すると$x_p,y_p$の二乗の項が消えて、

2x_1 x_p + 2y_1 y_p = x_1^2 + y_1^2\\
2x_2 x_p + 2y_2 y_p = x_2^2 + y_2^2

行列であらわしてこれを解くと、

\begin{align}
2\begin{pmatrix}
 x_1 & y_1 \\
 x_2 & y_2
\end{pmatrix}
\begin{pmatrix}
 x_p \\
 y_p
\end{pmatrix}
&=
\begin{pmatrix}
x_1^2 + y_1^2\\
x_2^2 + y_2^2
\end{pmatrix}\\
\begin{pmatrix}
 x_p \\
 y_p
\end{pmatrix}
&=
\frac{1}{2} \begin{pmatrix}
 x_1 & y_1 \\
 x_2 & y_2
\end{pmatrix}^{-1}
\begin{pmatrix}
x_1^2 + y_1^2\\
x_2^2 + y_2^2
\end{pmatrix}\\

&=
\frac{1}{2} 
\frac{1}{x_1 y_2 - y_1 x_2}
\begin{pmatrix}
 y_2 & -y_1 \\
 -x_2 & x_1
\end{pmatrix}
\begin{pmatrix}
x_1^2 + y_1^2\\
x_2^2 + y_2^2
\end{pmatrix}
\end{align}

ところで、三角形の面積は$S=\frac{1}{2} (x_1y_2 - y_1x_2)$でしたよね。
これを踏まえたうえで、外接円の半径$r$はどうなるかというと

\begin{align}
r^2 &=
\begin{pmatrix}
 x_p &
 y_p
\end{pmatrix}
\begin{pmatrix}
 x_p \\
 y_p
\end{pmatrix}\\
&=\frac{1}{16S^2}
\begin{pmatrix}
x_1^2 + y_1^2 &
x_2^2 + y_2^2
\end{pmatrix}
\begin{pmatrix}
 y_2 & -y_1 \\
 -x_2 & x_1
\end{pmatrix}^T
\begin{pmatrix}
 y_2 & -y_1 \\
 -x_2 & x_1
\end{pmatrix}
\begin{pmatrix}
x_1^2 + y_1^2\\
x_2^2 + y_2^2
\end{pmatrix}\\
&=\frac{1}{16S^2}
\begin{pmatrix}
x_1^2 + y_1^2 &
x_2^2 + y_2^2
\end{pmatrix}
\begin{pmatrix}
 y_2 & -x_2 \\
 -y_1 & x_1
\end{pmatrix}
\begin{pmatrix}
 y_2 & -y_1 \\
 -x_2 & x_1
\end{pmatrix}
\begin{pmatrix}
x_1^2 + y_1^2\\
x_2^2 + y_2^2
\end{pmatrix}\\
&=\frac{1}{16S^2}
\begin{pmatrix}
x_1^2 + y_1^2 &
x_2^2 + y_2^2
\end{pmatrix}
\begin{pmatrix}
 x_2^2 + y_2^2 & -x_1x_2 - y_1 y_2 \\
 -x_1x_2 - y_1 y_2 & x_1^2 + y_1^2
\end{pmatrix}
\begin{pmatrix}
x_1^2 + y_1^2\\
x_2^2 + y_2^2
\end{pmatrix}\\
\end{align}

ここで、$a^2 = OA^2 = x_1^2 + y_1^2$ , $b^2 = OB^2 = x_2^2 + y_2^2$,更に、$S=\frac{1}{2} (x_1y_2 - y_1x_2)$とおいて式を簡潔にしましょう。

\begin{align}
r^2 
&= \frac{1}{16S^2}
\begin{pmatrix}
a^2 & b^2
\end{pmatrix}
\begin{pmatrix}
 b^2 & -x_1x_2 - y_1 y_2 \\
 -x_1x_2 - y_1 y_2 & a^2
\end{pmatrix}
\begin{pmatrix}
a^2\\
b^2
\end{pmatrix}\\
&= \frac{1}{16S^2}a^2 b^2 \{(x_1-x_2)^2 + (y_1 - y_2)^2\}
\end{align}

ところで最後の項は辺$AB$の長さの二乗を表しています。
よって、辺$AB$の長さを$c$とするならば、

r^2 = \frac{1}{16S^2}a^2b^2c^2

外接円内の点かどうかを判定する

これまでに出してきた結論をもとに外接円内の点$(x,y)$が満たすべき条件を考えると、

(x-x_p)^2 + (y-y_p)^2 < r^2 \\
\Leftrightarrow
x^2 - 2x_p x + y^2 -2y_p y < 0\\

ここで、

\begin{pmatrix}
 x_p \\
 y_p
\end{pmatrix}= 
\frac{1}{2}
\frac{1}{x_1 y_2 - y_1 x_2}
\begin{pmatrix}
 y_2 & -y_1 \\
 -x_2 & x_1
\end{pmatrix}
\begin{pmatrix}
a^2\\
b^2
\end{pmatrix}

より、不等式の両辺に$x_1 y_2 - y_1 x_2$をかけると、$x_1 y_2 - y_1 x_2$が正の場合、つまり点$O$,点$A$,点$B$が反時計回りに配置されている場合、

(x_1 y_2 - y_1 x_2) (x^2 + y^2)  - 
x \begin{pmatrix}
 y_2 & -y_1
\end{pmatrix}
\begin{pmatrix}
a^2\\
b^2
\end{pmatrix}
- y
\begin{pmatrix}
 -x_2 & x_1
\end{pmatrix}
\begin{pmatrix}
a^2\\
b^2
\end{pmatrix} < 0

行列式を用いた書き換えを行うと、

(x^2 + y^2)  
\begin{vmatrix}
x_1 & y_1 \\
x_2 & y_2
\end{vmatrix}


-x
\begin{vmatrix}
a^2 & b^2 \\
y_1 & y_2
\end{vmatrix}

+ y
\begin{vmatrix}
a^2 & b^2 \\
x_1 & x_2
\end{vmatrix} < 0

これらはまとめて３×３の行列として表すことができる。ついでに$a,b$を展開しておくと、

\begin{vmatrix}
x^2 + y^2 & x & y \\
x_1^2 + y_1^2 & x_1 & y_1 \\
x_2^2 + y_2^2 & x_2 & y_2
\end{vmatrix}
 < 0

これを満たすような点$(x,y)$は外接円の内点に収まる.
ただし、これは点$O$,点$A$,点$B$が反時計回りに配置されていることが前提である。