円と円の交点
円と円の衝突は非常にシンプルで簡単なのですが、円と円の交点を求めようとすると突如難易度が上がります。
ここではそんな円と円の交点の求め方についてまとめていきます。
円と円の交点の考え方
円の中心をそれぞれ$C_{1}, C_{2}$、円の交点をそれぞれ $P, P'$、線分 $C_{1}C_{2}$ と 線分 ${PP'}$ の交点を $H$ とします。
この時、$\angle C_{1}HP$ は90度になります。
$C_{1}$ から $C_{2}$ に向かうベクトル $\vec{C_{1}C_{2}}$ を正規化したベクトルを $\vec{n_{1}}$ とします。
$\vec{n_{1}}$ を 左に90度回転させてできるベクトル (方向的に$H$ から $P$ に向かう)を $\vec{n_{2}}$ とします。
交点 $P$ の位置は、$C_{1}$ に $\vec{n_{1}}$ を伸ばしたベクトルを足して $H$ まで行き
さらに $H$ から $\vec{n_{2}}$ を伸ばしたベクトルを足すことでたどり着くことができます。
$P'$ にたどり着くには、$H$ から $\vec{n_{2}}$ を逆方向に伸ばせばたどりつけます。
様々な計算が必要になりますが、これが円と円の交点を求める大まかな流れとなります。
円と円の交点の求め方
円の中心をそれぞれ$C_{1}, C_{2}$、円の半径をそれぞれ $r_{1}, r_{2}$、円の交点をそれぞれ $P, P'$、線分$C_{1}C_{2}$ と 線分 $PP'$ の交点を $H$とします。
辺$C_{1}H$ の長さを求める編
まず辺$C_{1}H$ の長さ(青線の部分)を求めることから始めます。
$\triangle C_{1}C_{2}P$ の各辺 $C_{1}C_{2}, C_{1}P, C_{2}P$ の長さをそれぞれ、$a, b, c$ とおきます。
この時、三角形の三辺 $a, b, c$ の長さは全てわかっているという事実があります。
$a$ は $\vec{C_{1}C_{2}}$ の長さですし、$b$ と $c$ はそれぞれ 円の半径です。
$a = |\vec{C_{1}C_{2}}|$
$b = r_{1}$
$c = r_{2}$
三角形には素敵な性質が沢山ありますが、3辺全ての長さが分かっていると余弦定理が使えます。
とりあえず、$\angle PC_{1}C_{2}$ の角度を $\theta$ とおき、$cos(\theta)$ の値を求めてみたいと思います。
$cos(\theta)$ は余弦定理より、以下の計算で求める事ができます。
$cos(\theta) = \frac{a^2 + b^2 - c^2}{2ab}$
$cos(\theta)$ を手に入れたことによって、不思議な事に、辺 $C_{1}H$ の長さを求めることができるようになります。
辺 $C_{1}H$ の長さを $r_{c}$ とおくと、$r_{c}$ は $b$ と $cos(\theta)$ の値を掛け算するだけで求める事ができてしまいます。
$r_{c} = b \cdot cos(\theta)$
なぜこれで、$r_{c}$ が求まるのかの補足
$\triangle C_{1}HP$ に着目します。
$cos(\theta)$ は$\frac{底辺}{斜辺}$ なので、図から $\frac{r_{c}}{b}$ となります。
$b \cdot cos(\theta)$ は以下のように置き換えられます。
$b \cdot \frac{r_{c}}{b} = r_{c}$
長い計算でしたが、これで目的だった 辺 $C_{1}H$ の長さ($r_{c}$)がわかりました！
辺 $HP$ の長さを求める編
続いて求めたいのが、辺 $HP$ の長さとなります。(辺 $HP$ の長さを $r_{s}$ とおきます)
$\triangle PC_{1}H$ に注目すると、$\triangle PC_{1}H$ は直角三角形であり、2辺の長さはもうわかっています。
そして直角三角形の2辺の長さがわかっている時、三平方の定理を使って残りの辺の長さを求める事ができます。
直角三角形の底辺を $r_{c}$、斜辺は円の半径なので $r_{1}$ とすると、三平方の定理により
$r_{s} = \sqrt{r_{1}^2 - r_{c}^2}$
これで$r_{s}$ が求まりました。
$\vec{n_{1}}$と$\vec{n_{2}}$ を求める編
続いて、図の中にある$\vec{n_{1}}$と$\vec{n_{2}}$を求めて生きたいと思います。
$\vec{n_{1}}$ は $C_{1}$ から $C_{2}$ に向かうベクトル $\vec{C_{1}C_{2}}$ を求めて正規化する事で手に入ります。
$\vec{n_{1}} = \vec{C_{1}C_{2}}$ を正規化
$\vec{C_{1}C_{2}} = C_{2} - C_{1} $
そして、$\vec{n_{2}}$ は $\vec{n_{1}}$ を左に90度回転させる事で得られそうです。
ベクトルの回転でベクトルを回転させる方法を説明していますが、90度回転させる場合はもっと簡単な方法があります。
ベクトルの$xy$ 成分を入れ替えて、$x$成分に -1 を掛けると、左に90度回転したベクトルが得られます
$ \vec{n_{1}} = (x, y) $ とすると
$ \vec{n_{2}} = (-y, x) $
これで $\vec{n_{1}}$と$\vec{n_{2}}$ が求まりました。
交点 $P, P'$ を求める編
ここまできてようやく、交点 $P, P'$ を求める材料がそろいました。
交点 $P$ は $C_{1}$ の位置に $\vec{n_1} $ を $r_{c}$ 倍したベクトルを足し、更に $\vec{n_2} $ を $r_{s}$ 倍したベクトルを足した位置になります。
交点 $P'$ は $C_{1}$ の位置に $\vec{n_1} $ を $r_{c}$ 倍したベクトルを足し、更に $\vec{n_2} $ を $-r_{s}$ 倍したベクトルを足した位置になります。
$P = C_{1} + r_{c}\vec{n_{1}} + r_{s}\vec{n_{2}}$
$P' = C_{1} + r_{c}\vec{n_{1}} - r_{s}\vec{n_{2}}$
長い長い旅路を経て、ようやく円と円の交点を求める事ができました。
交点を求める計算はこれで終わりになります、しかし衝突判定的にはまだ考慮するべきことが残っています。
円同士が衝突していない場合は、そもそも交点が存在しませんし、円がぴったりと接している場合は交点が1になります。
以下では円同士が交点を持たない時、交点が1つの時の判定について記載していきます。
交点を持たないとき
2つの円が交点を持たないケースが２パターンあります。
１つは円が接触していないとき、もう一つは一方の円の中に円が内包されている時です。
それぞれについて判定方法を見ていきます。
接触していない場合
図を見るからに明らかですが、円は接触しておらず交点も存在しません。
円と円が接触しているかどうかの判定については、円と円の衝突に方法を記載していますのでそちらをご覧ください。
内包している場合
円が一方の円の中に内包されているかどうかは、2つの円の距離と半径の差を比較します。(差はマイナスになることがあるので絶対値で比較します)
円の距離 < 半径の差の絶対値であれば円は一方の円に内包された状態になります。
円の中心をそれぞれ$C_{1}, C_{2}$、半径を $r_{1}, r_{2}$ としたとき
$|\vec{C_{1}C_{2}}| < |r_{1} - r_{2}| $ であれば、円は内包関係にある。
プログラム的な話
プログラムでは、円の交点を求める前に、円同士が接触しているか、もしくは内包されているかどうかを調べます。
接触していない、もしくは円が内包関係にある場合、交点は存在しないのでそこで処理を終えます。
交点が１つのとき
円がぴったりと接している時、交点は1つに定まります。(実際には小数点誤差でなかなかぴったりにはなりませんが)
そして円が接しているケースは円の外側で接している(外接)と円の内側で接している(内接)の２通りがあります。
外接している時の接点
円が外接しているのは、$\vec{C_{1}C_{2}}$ の長さが、円の半径の和と一致する時です。
$ |\vec{C_{1}C_{2}}| = r_{1} + r_{2} $ であれば２つの円は外接している。
円の接点 $P$ は $C_{1}$ に $\vec{C_{1}C_{2}}$ を正規化したベクトル($\vec{n}$とする)を、$r_{1}$ 倍したベクトルを足せば求まります。
$P = C_{1} + r_{1}\vec{n}$
内接している時の接点
円が内接しているのは、$\vec{C_{1}C_{2}}$ の長さが、円の半径の差と一致する時です。(差はマイナスになることがあるため絶対値で比較します)
$ |\vec{C_{1}C_{2}}| = |r_{1} - r_{2}| $ であれば２つの円は内接している。
内包している場合の円の接点は少しややこしい問題があります。
$C1$ の円の方が大きい場合、接点 $P$ は$\vec{C_{1}C_{2}}$を正規化したベクトル($\vec{n}$とする)を $r_{1}$ 倍して、$C_{1}$ に足せば求まります。(外接の時と同じ)
しかし、$C1$ の円の方が小さい場合、接点 $P$ は$\vec{C_{1}C_{2}}$を正規化したベクトル($\vec{n}$とする)を $-r_{1}$ 倍して、$C_{1}$ に足さなければいけません。
このように、円の大小関係によって$\vec{n}$ を $r_{1}$ 倍するのか、 $-r_{1}$ 倍するのか、微妙に違いが発生します。
$C1$ の円の方が大きい時、接点 $P$ は
$P = C_{1} + r_{1}\vec{n}$
$C1$ の円の方が小さい時、接点 $P$ は
$P = C_{1} - r_{1}\vec{n}$
長くなりましたが、これにて円と円の交点の説明は終わりです。
サンプルコード
/**
* 直線と円の衝突
* @param circle1 円１
* @param circle2 円２
*/
export function intercect(circle1:Circle, circle2:Circle)
{
// 衝突判定の結果オブジェクト
const result:IIntercectResult = {
hit: false,
pos: [],
}
// 円1の中心をC1、円2の中心をC2、交点の1つをPとする。
const C1 = circle1.p;
const C2 = circle2.p;
// C1からC2に向かうベクトルを vC1C2と定義する
const vC1C2 = Vector2.sub(C2, C1);
// 辺C1C2の長さを a とする
const a = vC1C2.magnitude;
// a が 2円の半径の和より大きければ当たっていない
const sumR = circle1.r + circle2.r;
if (sumR < a) return result;
// ここに来たらとりあえず当たっている
result.hit = true;
// 円と円の交点を求めていく
// 円が内包されている時は接点は存在しない
// 円が内包されている場合、a は 2円の半径の差より小さい
const subR = Math.abs(circle1.r - circle2.r);
if (a < subR) {
return result;
}
// 円が外接しているとき、a と 2つの円の半径の和は等しく、接点は１つだけになる。
if (a === sumR) {
// vC1C2 を正規化したベクトルを n とする
const n = vC1C2.normalize;
// 接点P は C1 に n を 円の半径の長さ分伸ばしたベクトルを足せばいい
const P = Vector2.add(circle1.p, n.times(circle1.r));
result.pos.push(P);
return result;
}
// また内接しているとき、a と ２つの円の半径の差は等しく、接点は１つだけになる。
if (a === subR)
{
// vC1C2 を正規化したベクトルを n とする
const n = vC1C2.normalize;
// C1の方が大きいかどうか
const isLarge = (circle1.r > circle2.r);
// 接点をPとすると
// C1の方が大きい場合、P は C1 + r1・n
// C1の方が小さい場合、P は C1 - r1・n
const P = Vector2.add(circle1.p, n.times(isLarge? circle1.r:-circle1.r));
result.pos.push(P);
return result;
}
// 三角形C1C2Pの三辺は全て既知である。
// 辺C1Pの長さをb、辺C2Pの長さをcとする
const b = circle1.r;
const c = circle2.r;
// 角C1 の cosθ は余弦定理により
const cos = (a**2 + b**2 - c**2) / (2 * a * b);
// PからC1C2に垂線を落とした時に当たる位置を H とし、C1Hの長さを rc とすると rc は b * cos
const rc = b * cos;
// 辺HPの長さを rs とすると rs は三平方の定理から rs = √b^2 - t^2
const rs = Math.sqrt(b**2 - rc**2);
// vC1C2の正規化したベクトルを n1とする
const n1 = vC1C2.normalize;
// n1を左に90度回転させたベクトルを n2とする
const n2 = new Vector2(-n1.y, n1.x);
// 交点であるPの座標は C1 + tn1 + sn2 となり
// もう一つの交点C'は C1 + tn1 - sn2 となる
const tn1 = n1.times(rc);
const sn2 = n2.times(rs);
result.pos.push(circle1.p.clone().add(tn1).add(sn2));
result.pos.push(circle1.p.clone().add(tn1).sub(sn2));
return result;
}