図形クラス３「距離」

２つの図形の距離

図形クラス、図形クラス２でいくつかの図形クラスを作ってきたので、２つの図形の距離の出し方やそのプログラムについて考えましょう。

２つ点の距離

点\((X_1,Y_1)\)と点\((X_2,Y_2)\)の距離は、下の式で計算できます。（たぶん、中学生の数学で習いますよね。）
\[
L=\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2}
\]

これをTypeScriptでプログラムすると下のコードのようになります。

/**
 * 点(x1,y1)と点(x2,y2)の距離を計算する。
 * @param x1 
 * @param y1 
 * @param x2 
 * @param y2 
 */
export function Distance(x1: number, y1: number, x2: number, y2: number) {
    let dx = x2 - x1;
    let dy = y2 - y1;
    return Math.sqrt(dx * dx + dy * dy);
}

IPoint

(x2,y2)をIPointにすると、下コードになります。

 * 点(x,y)と点pの距離を計算する。
 * @param x 
 * @param y 
 * @param p 
 * @returns 
 */
export function DistanceToPoint(x: number, y: number, p: IPoint) {
    return Distance(x, y, p.X, p.Y);
}

Point

IPointを継承するすべてのクラスはこの関数の引数にすることができます。例えば下のコードのようにk記述することができ、(30,0)とP1の距離を計算できます。distanceは50と計算されます。

let P1 = new Point(0,40);
let distance = DistanceToPoint(30,0,P1);

CircleとRectangle

CircleとRectangleもIPointを継承しているのでこの関数の引数にすることができます。

しかしCircleとRectangleが継承しているIPointは図形の中心点を表しています。そのため、中心点との距離が算出されます。下のコードでは、distanceは50になります。

let C1 = new Circle(0,0,50); // 点(0,0)を中心とする半径50の円
let P1 = new Point(-50,0);   // 点(-50,0)
let distance = Distance(C1,P1);
// 距離は50と計算される。

点と円周の距離

前述のコードのC1とP1の場合「点P1は円C1の円周上の点である」という関係があるので、この点と円の距離は0（＝点が円に接触している）と計算されて欲しいです。

上記のような、点(X,Y)と円（C:Circle）の円周との距離を計算するための関数は下のコードのようになります。

/**
 * 点(x,y)と円cの円周の距離を計算する。
 * @param x 
 * @param y 
 * @param c 
 * @returns 
 */
export function DistanceToCircle(x: number, y: number, c: Circle) {
    let tmp = Distance(x, y, c.X, c.Y);
    return tmp - c.Radius;
}

　まず点と円の中心の距離をDistance()を使って計算します。その距離から円の半径を引くと円周と点との距離になります。

これは点が円の内部にあるか否かの判定にも使うことができます。距離が０より小さければ、点は円の内部にあります。距離が０ならば、点は円周上に存在します。

円周とその他の図形の距離

同様に円周とその他の図形の距離は、

1. 円の中心点とその他の図形の距離を算出する。
2. その距離から、半径を引く。

という手順を踏むことで算出することができます。例えば２つの円C1とC2のお互いの円周の距離を算出する場合は、下のようなコードで計算できます。

export function DistanceCircleToCircle(c1: Circle, c2: Circle) {
    let tmp = DistancePointToCircle(c1.X,c1.Y,c2);
    return tmp - c1.Radius;
}

上は考え方を示すためのコードです。実際に使うコードはおそらく下のようになります。

/**
 * 円c1とc2の円周の距離を計算する
 * @param c1 
 * @param c2 
 * @returns 
 */
export function DistanceCircleToCircle(c1: Circle, c2: Circle) {
    let tmp = Distance(c1.X, c1.Y, c2.X, c2.Y);
    return tmp - c1.Radius - c2.Radius;
}

点と直線の距離

端を持たない直線であるStraightLineと点との距離について考えます。

StraightLineは直線方程式の一般形 \(ax+by+c=0\) の情報を保持しています。

点P\((P_x,P_y)\)と直線\(ax+by+c=0\) の距離は、次の式で求めることができます。

\[
\frac{\vert aP_x + bP_y +c \vert}{\sqrt{a^2+b^2}}
\]

式の詳しい説明や証明は、数学関係のもっと詳しいページを参照してください。これは中学か高校の数学に出題される問題であるらしく、検索すればたくさんのページが見つかるはずです。

上記の式が正しいとして、それをコードにすると下のようになります。

/**
 * 点(x,y)と直線slineの距離を計算する
 * @param x 
 * @param y 
 * @param sline 
 * @returns 
 */
export function DistanceToStraigtLine(x: number, y: number, sline: StraightLine) {
    let a = sline.A;
    let b = sline.B;
    let c = sline.C;
    let tmp = Math.sqrt(a * a + b * b);
    if (tmp == 0) {
        throw new RangeError("直線の情報が正しくセットされていないため、演算ができません");
    }
    return Math.abs(a * x + b * y + c) / tmp;
}

点と線分の距離

線分（端のある直線）であるLineと点との距離はもう少し複雑になります。それは点Pと直線の位置関係によって、距離を測る点が変わるからです。

直線と同じになるケース

最初に簡単なケースについて説明します。上図では点Pと線分L1があります。そして線分L1上に点P’があります。PとP’を結ぶ点線とL1は垂直に交わっています。

点PとL1がこのような位置に関係のあるときは、２つの距離は「点とStraightLine」の距離と同じように計算することができます。そして距離はQとQ'を結ぶ線分の長さと一致します。

let p = new Point(10,0);
let l1 = new Line(-20,-20,20,20);
let sline = new StraightLine();
sline.SetLine(l1.X1, l1.Y1, l1.X2, l1.Y2);
let distance = DistanceToStraigtLine(p.X, p.Y, sline);

直線と異なるケース

次に、直線と同じにならないケースについて説明します。

上図では点Qと線分L2があります。そして線分L2の延長線上に点Q’があります。QとQ’を結ぶ点線とL2を延長した線は垂直に交わっています。

このケースもPとL1のときと同じ計算をすると、算出される距離はQとQ’を結ぶ線分の長さと一致します。しかしQ'はL２の線上にはないので、これをQとL2の距離とするのは適切ではありません。それは、仮にQとQ'が同じになったとき、距離が０と計算されてしまうからです。まったく接していない点と線分の距離を０としてしまうと、例えば図形の衝突や重なりなどの判定などが正しく行えません。

このケースでは、L2の線分の端((L2.X1,L2.Y1)または(L2.X2,L2.Y2)のどちらか）とQの長さがQとL2の距離になります。それが０になったとき、QとL2は接触しています。

最終的な計算方法

前述した２つのケースの違いを判定し、それぞれのケースの計算方法を用いて距離を算出する必要があります。それでは２つのケースの違いは何で、どうやって判定すればよいでしょうか？

それぞれの違いは線分に対する点の位置です。下の図を使って説明します。

１つ目のケースは、Pから線分に向かって垂線をおろし、線分と交わります。そして垂線の長さ（上図のPとP'の距離）が点と線分の距離です。
２つ目のケースはQから垂線を落としても線分と交わりません。（線分の延長線上の点Q’で交わります。）このときはQとAの距離が点と線分の距離です。
上図では第３のケースとしてRも追加しました。Rも垂線を下ろしても線分と交わりません。このときはRとBの距離が点と線分の距離です。

上図の点P, Q, Rを判定するには、正射影ベクトルを使うと良いでしょう。正射影ベクトルについての詳細は数学関係のもっと詳しいページを参照してください。「正射影ベクトル」で検索すれば見つかるはずです。

上図の線分の両端点A, Bに対して、\(\vec{AP}\)から\(\vec{AB}\)対する正射影ベクトル\(\vec{AP'}\)は、
\[
\vec{AP'}=k\vec{AB}\\
ただし、k=\frac{\vec{AB} \cdot \vec{AP}}{\vert \vec{AB} \vert^2}\\
\]
と定義できます。そして点Pが上図のような位置関係にあるなら、 \(0≦k≦1\) になります。

同様にQに対して、
\[
\vec{AQ'}=l\vec{AB}\\
ただし、l=\frac{\vec{AB} \cdot \vec{AQ}}{\vert \vec{AB} \vert^2}\\
\]
と定義すると、 \(l<0\) になります。

Rも同様に計算すると、係数が1より大きくなります。つまり、正射影ベクトルの計算を行い、その係数に応じてケースを分けます。そしてケースごとに距離を算出します。

以上のことを踏まえて、点と線分の距離を算出するコードは下のようになります。

/**
 * 点(x,y)と線分lineの距離を計算する
 * @param x 
 * @param y 
 * @param line 
 * @returns 
 */
export function DistanceToLine(x: number, y: number, line: Line) {
    // lineの(X1,Y1) -> （X2,Y2） へのベクトルをV0とする
    let V0X = line.X2 - line.X1;
    let V0Y = line.Y2 - line.Y1;

    // V0の長さの二乗をLL0とする。
    let LL0 = V0X * V0X + V0Y * V0Y;
    // もし、LL0が0なら、lineは線分ではなく点になるので、(x,y)と(X1,Y1)の距離を返す。
    if (LL0 == 0) {
        return Distance(x, y, line.X1, line.Y1);
    }

    // lineの(X1,Y1) -> (x,y) へのベクトルをV1とする
    let V1X = x - line.X1;
    let V1Y = y - line.Y1;

    // V1からV0への正射影ベクトルを作るための係数kを計算する。
    let k = (V0X * V1X + V0Y * V1Y) / LL0;

    if (k < 0) {
        // (x,y) と(X1,Y1)の距離を返す。
        return Distance(x, y, line.X1, line.Y1);
    }
    else if (k > 1) {
        // (x,y)) と(X2,Y2)の距離を返す。
        return Distance(x, y, line.X2, line.Y2);
    }
    else {
        // V0のk倍したものがからV0への正射影ベクトルである。
        // このとき、V1と正射影ベクトルを繋げると直角三角形になるので、
        // 三平方の定理により、距離を算出できる。
        // つまり、
        //      V1の長さの二乗 ＝ 正射ベクトルの長さの二乗 ＋ 求める距離の二乗
        //      求める距離の二乗 ＝ V1の長さの二乗 － 正射ベクトルの長さの二乗
        // となる。

        // V1の長さの二乗をLL1とする
        let LL1 = V1X * V1X + V1Y * V1Y;
        // 正射ベクトルの長さの二乗は k^2 * LL0
        return Math.sqrt(LL1 - k * k * LL0);
    }
}

ほとんどの部分はすでに説明済みですが、関数の最後の \(0≦k≦1\) の時の処理を少し説明します。

この節の最初に説明したように、図のPとP'の距離が求める点と線分の距離になります。そして、点AとPとP'は直角三角形になり、三平方の定理から次の式が成り立ちます。
\[AP'^2+PP'^2=AP^2\\\]

APはコード中では「V1のベクトル」であり、AP’は正射影ベクトルになるので、コード中では「V0のベクトル」をk倍したものになります。そのため、

\begin{split}
AP'^2+PP'^2&=AP^2\\
(正射影ベクトルの長さ)^2 + (求める距離)^2&=(V1の長さ)^2\\
k^2 LL0 + (求める距離)^2&=LL1\\
(求める距離)^2&=LL1-k^2 LL0\\
(求める距離)&=\sqrt{LL1-k^2 LL0}
\end{split}

という式が導き出されます。

点と長方形

RectangleはX軸に平行な辺と垂直な辺を持った長方形です。このRectangleと点との距離について考えます。

距離の定義

最初に点と長方形と距離を定義しましょう。

外側の点

点が長方形の外にある時は、外周となる４つの辺の中で最も近い辺との距離を「点と長方形の距離」とします。

例えば、上の図で考えると点Pは長方形の上辺との距離が最も近いので、Pと上辺の距離が求める距離です。

それでは、点Qの場合はどうなるでしょうか？点Qと距離が最も近いのは上辺と左辺です。そして２つの辺が交わる左上の頂点とQの距離が求める距離です。同様に点Rの場合は、右上の頂点とRとの距離が求める距離になります。

内側の点

円周と点の距離の説明で、「距離が０より小さければ、点は円の内部にあります。」としたので、長方形の場合も内側にある時も０より小さい値と定義します。

実際に算出する距離は、長方形の４つの辺全てとの距離を算出し、もっとも小さいもの（をマイナスにした値）を点と長方形の距離とします。上図では点Pが長方形の４つの辺の中では下辺に最も近いので、PのY座標と下辺のY座標の差から距離を算出します。

辺上の点

長方形の何れかの辺と重なる点と長方形の距離は０です。

ただし、これは内側の点と同じように計算すれば、算出できます。

計算方法

X座標を考えないとき

計算方法を考えるために、現実にはありえない長方形を使って、問題を考えてみましょう。

上図の長方形は上辺と下辺の座標は有限の値ですが、左辺の座標は－∞、右辺の座標は＋∞になっていると考えてください。

このとき点が長方形の外側にあるか内側にあるかを判定する処理は、点のY座標と上辺、下辺のY座標だけで判定でき、X座標を考慮する必要がなくなります。

このとき、上辺より上にある点Pは外側の点で距離は下のようになります。

Pと長方形の距離＝上辺のY座標 - PのY座標 

なお、Rectangleなどの図形はCANVASでの描画処理に使う事を目的としているため、Y軸は下向きが正方向です。「上にある」＝「Y座標は小さい」となります。

下辺より下にある点Qも外側の点で距離は下のようになります。

Qと長方形の距離＝QのY座標 - 下辺のY座標

上辺と下辺の間にある点Rは内側の点です。距離は下のようになります。

上辺との距離 = 上辺のY座標 - RのY座標
下辺との距離 = RのY座標 - 下辺のY座標
Rと長方形の距離 = MAX(上辺との距離,下辺との距離)

Rが上辺と下辺の間にあるため、上の式の上辺との距離と下辺との距離は必ず負の値になります。そして各辺に近づくほど０に近づきます。つまり、上辺との距離と下辺との距離のうち大きい方が点Ｒと長方形の距離となります。

そしてこの式は、PやQの距離を算出する時にも使うことができます。例えばPのときは、

上辺との距離 = 上辺のY座標 - PのY座標 > 0
下辺との距離 = PのY座標 - 下辺のY座標 < 0
Pと長方形の距離 = MAX(上辺との距離,下辺との距離) = 上辺との距離

となります。Qのときも同じように計算して最終的に距離2が出てきます。

つまり、左右の辺を考えないなら、引き算とMAX()を使った３行の式だけで距離を算出できます。

Y座標を考えないとき

同様に、左辺と右辺のX座標が有限で、上辺の座標は－∞、下辺辺の座標は＋∞になっている長方形を使って考えると、

左辺との距離 = 左辺のX座標 - 点のX座標
右辺との距離 = 点のX座標 - 右辺のX座標
点と長方形の距離 = MAX(左辺との距離,右辺との距離)

となります。

２つのケースを合わせる

上述の２つのケースを重ね合わせてみましょう。

上辺との距離 = 上辺のY座標 - RのY座標
下辺との距離 = RのY座標 - 下辺のY座標
左辺との距離 = 左辺のX座標 - 点のX座標
右辺との距離 = 点のX座標 - 右辺のX座標
dy = MAX(上辺との距離,下辺との距離)
dx = MAX(左辺との距離,右辺との距離)

(1)dy<0かつdx<0ならば、点は長方形の内側にあります。その距離はdyとdxの大きい方です。

(2)dy<0かつdx>0ならば、点のY座標は上辺と下辺の間にあり、X座標は左辺と右辺の外側になるので、点は長方形の外側にあります。その距離はdxです。

(3)dy>0かつdx<0のときも同様に外側にありますが、距離はdyになります。

(4)dy>0かつdx>0のときは、下の図のようになります。点のY座標は上辺と下辺の外側にあり、X座標は左辺と右辺の外側になるので、点は長方形の外側にあります。距離は\(\sqrt{dx^2+dy^2}\)になります。

以上４つのケースに分けて考えましたが、１～３番目のケースは、下のようにすることができます。

点と長方形の距離 = MAX(dx,dy)

最終的な計算方法

以上を踏まえて、最終的な点と長方形の距離を算出するコードは下のようになります。

/**
 * 点(x,y)と長方形rectの距離を計算する
 * @param x 
 * @param y 
 * @param rect 
 */
export function DistanceToRectangle(x: number, y: number, rect: Rectangle) {
    // rectの上辺(Top)と基点としたときの点と長方形の距離
    // yt>0なら、点は外側にある
    let yt = rect.Top - y;
    // rectの下辺(Bottom)と基点としたときの点と長方形の距離
    // yb>0なら、点は外側にある
    let yb = y - rect.Bottom;
    // rectの左辺(Left)と基点としたときの点と長方形の距離
    // xl>0なら、点は外側にある
    let xl = rect.Left - x;
    // rectの右辺(Right)と基点としたときの点と長方形の距離
    // xr>0なら、点は外側にある
    let xr = x - rect.Right;

    // y座標だけで判断したときの、点と長方形の距離
    let dy = Math.max(yt, yb);
    // x座標だけで判断したときの、点と長方形の距離
    let dx = Math.max(xl, xr);

    if (dy > 0 && dx > 0) {
        // 点がX座標/Y座標の両方で判断して、外側にあるとき
        return Math.sqrt(dx * dx + dy * dy);
    }
    else {
        // 点がX座標/Y座標のどちらかあるいは両方で、内側にあるとき
        return Math.max(dx, dy);
    }
}