satoh

知っているようで知らないデジタル図形処理 ~任意形状図形の選択から交点・接点・接線計算まで、方程式では解けないノウハウを紹介

   

画面に描いた直線をマウスで選択してみよう

はじめに

HTML5のCANVASを使ってWEBでも自由に線を引いたり円を描いたりできるようになりました。WEBでもCADが作れる時代です。
実際に作ろうとすると、図形の作成、編集(削除・移動・サイズ変更など)などの機能が必要になります。
作図するのは割と簡単で、直線であればマウスで最初にクリックしたところが始点、2度目にクリックしたところが終点として描画するだけです。
面倒なのは編集です。編集を行うためにはすでに描いた要素(直線・円・円弧・自由曲線など)を「選択」する必要があります。
そこでしばらくは「図形の選択」について書いていこうと思います。
第一回は直線の選択です。

直線を選択する

「選択する」というのはマウスでクリックされた座標が描画された直線の上にある、ということになります。
直線の方程式はご存じの通り、
    y = ax + b
です。aが傾き、bがy切片ですね。
ここで計算するための数式は書きませんが、数学的に「選択」したかどうかを求めようとすると、以下のことを考えなければなりません。
・マウスクリックした座標から描画されている直線へ垂線をおろす
・その垂線と直線の交点を求める
・マウスクリックした座標とその交点との距離を求める
・距離が0であればマウスクリックした座標は描画した直線の上にある
なんか大変ですね。しかし考慮すべきことはもっとたくさんあります。
・描画した直線は開始終了のある線分であるため、開始点-終了点の範囲にある座標だけが対象となる
・デジタル処理のためマウスクリック座標は理論上の直線上座標にない場合が殆ど
こう考えると「ある程度幅を持たせた線分」つまり「矩形の中にマウスクリック座標があるか」を調べないとならないことがわかります。

矩形内ヒット-1
上図の点線で記した矩形内にマウスクリックの座標があれば「選択」したことになります。
もう少し考慮するのならば直線の両端点にも選択エリアの巾を持たせるべきでしょう。
直線の選択領域(両端点考慮)両端点を中心とする円の範囲を追加しました。この領域が、直線(線分)から等距離にあることがわかると思います。
この距離が、
・直線を選択しようとするマウスクリック点との誤差
以上になるようにします。
実際にプログラムを組む時はこの距離を変更できるようにして、使用感で判断しながら最適な値にすることになります。

矩形内にマウスクリック座標があるか調べる

さて、前章で直線を選択する、ということは結局「矩形内にマウスクリック座標があるかどうか調べる」ということがわかりました。
しかしこうなると数学的に解くのはもっとやっかいになります。
傾いた矩形の領域内判定、と考えるととても面倒なので考え方を変えてみましょう。
傾いていない矩形領域に指定した座標点が存在するかどうか、という問題は簡単に解けます。いまここで座標点を、
    P(px, py)
直線の座標を、
    L(x1, y1, x2, y2)
矩形を
    R(sx, sy, dx, dy)
とします。
    sx : 開始点X座標
    sy : 開始点Y座標
    dx : 矩形の巾
    dy : 矩形の高さ
です。
こうすると数値計算は不要となって値の大小判断だけで判定ができます。
例えばCで記述してみると、
    if (px >= sx && px <= sx + dx && py >= sy && py <= sy + dy) {
        printf(“指定座標は矩形内に存在するn”) ;
    } else {
        printf(“指定座標は矩形内に存在しないn”) ;
    }
こんな感じです。
ここでもう一つ考えを進めて、マウスクリック点が原点、すなわち、(0,0)だったらどうでしょう?
    if (sx > 0 || sy > 0 || sx + dx < 0 || sy + dy <= 0) {
        printf(“指定座標は矩形内に存在しないn”) ;
    } else {
        printf(“指定座標は矩形内に存在するn”) ;
    }
前記のコードとそう変わりはありませんが、もうマウスクリック点P(x,y)の考慮はなくなります。非常に簡単な判断となるわけです。
では問題を戻して実際のことを考えてみます。
「傾いた矩形の領域内判定」を、「矩形内に原点(0,0)が存在するか」に変えてみましょう。
以下の図を参照してください。
矩形内領域判定(移動と回転)
ちょっとだけ図形処理っぽい計算が必要ですが、上図の①②を行えば、前述の判定でマウスクリック点が矩形内にあるか…つまり直線を選択したかどうかがわかるわけです。

①マウスクリック点を原点に平行移動する

マウスクリック点 P(px, py) を原点に移動する、つまり、px = 0, py = 0 にするわけなので、直線 L(x1, y1, x2, y2) の各座標から P(px, py) を引けばいいことがわかります。
平行移動後の直線を、
    L'(xm1, ym1, xm2, ym2)
とします。
    xm1 = x1 – px;
    ym1 = y1 – py;
    xm2 = x2 – px;
    ym2 = y2 – py;
これで平行移動は終わりました。

②傾きを0にする

ちょっとだけ数学ですが、三角関数を使って回転角度を求めます。
とはいっても具体的な角度がわかる必要はありません。座標を回転させるためには角度に対するsin,cosがわかれば計算できます。
いま、この直線の傾き角度を
    angle
それに対するsin,cosを、
    sn = sin(angle)
    cs = cos(angle)
とします。直線の長さを、
    length
とします。
直線の長さは、直角三角形の斜辺ですから
    _dx = xm2 – xm1;
    _dy = ym2 – ym1;
    length= sqrt(_dx * _dx + _dy * _dy);
で求められます(※ここで、_dx^2 … としないのは、Cの場合べき乗には計算コストがかかるためです)。
回転角度に対するsin,cosは、
    cs = _dx / length;
    sn = _dy / length;
です。ここまでできればあとは平行移動後の直線の座標を回転するだけです。回転するときに注意するのは「傾きを0にする」つまり傾き角度だけマイナスに回転することです。回転後の直線を、
    L”(xr1, yr1, xr2, yr2)
とすれば、
    xr1 = xm1 * cs + ym1 * sn;
    yr1 = -xm1 * sn + ym1 * cs;
    xr2 = xm2 * cs + ym2 * sn;
    yr2 = -xm2 * sn + ym2 * cs;
これで傾き0の直線に変換されました。
領域内判定のための巾をもたせて矩形 R(sx, sy, dx, dy) にしてみます。
巾を、
    h
とします。矩形 R(sx, sy, dx, dy) は、
    sx = xr1;
    sy = yr1;
    dx = xr2 – xr1;
    dy = h;
直線の傾きは0、すなわち水平線になったはずなので、yr1 == yr2 です。

直線の端点部分の判定を考慮する

これで、前章で示した、
    if (sx > 0 || sy > 0 || sx + dx < 0 || sy + dy <= 0) {
        printf(“指定座標は矩形内に存在しないn”) ;
    } else {
        printf(“指定座標は矩形内に存在するn”) ;
    }
で判定が可能になりました。
あとは両端点の円で余裕を持たせた領域の判定を追加すれば完璧になります。
円の中にマウスクリック座標があるかどうかの判定は簡単で、円の中心座標からマウスクリック点までの距離が円の半径以下かどうか、ということになります。
いま、マウスクリック点は原点(0,0)になっていますから、直線の端点の原点からの距離が、判定巾 h の半分となります。
    l1 = (xr1 – h / 2) * (xr1 – h / 2) + (yr1 – h / 2) * (yr1 – h / 2);
    l2 = (xr2 – h / 2) * (xr2 – h / 2) + (yr2 – h / 2) * (yr2 – h / 2);
これが各端点の距離の2乗です。√(sqrt)で開く必要はありません。円の半径の方も2乗してしまえばよいからです。
    rr = (h / 2) * (h / 2);
sqrtは計算コストがかかるため、2乗のまま比較します。
    if (l1 <= rr) {
        printf(“指定座標は矩形内に存在するn”) ;
    } else {
        printf(“指定座標は矩形内に存在しないn”) ;
    }
これをもう一方の端点の距離、r2に対しても行えば終わりです。

終わりに

後半、プログラムの記述ばかりになってしまいましたが、もう決まり事なので一度作ってしまえばどこでも応用がききます。
ほかにも全く違うアプローチで外積を使うこともできますが、それは次回以降に紹介します。

 - C, ヒットテスト