html5のcanvasに描画した曲線をヒットテストする

昨年はWPFを使ってGUIをグリグリ動かすアプリ開発にどっぷりはまっていたので今回は久しぶりにJavaScriptをいじりたくなり表題のものをガリガリ作った。

デモはこちら
githubはこちら（デモと差は皆無）

赤い四角が始点と終点だ。オレンジの四角が制御点になる。すべてdraggableなので任意に動かしてもらいたい。線上の点は曲線を直線に分割している点だ。曲線をクリックすると緑色になる。

曲線描画 on canvas
html5のcanvas上で曲線を描画するのは至極簡単だ。context.bezierCurveToまたはcontext.quadraticCurveToを呼び出せば良い。前者は制御点が２つのcubic bezierで後者は名称そのままの制御点１つのquadratic bezierだ。今回のデモではcubic bezierのほうを使用している。

曲線ヒットテスト on canvas
しかしあたり判定になると手段が提供されていないので自前でやる必要がある。以下任意のクリックした点が曲線上に位置しているかを計算する方法である。

１、曲線上の任意の点の接線の傾きを計算し曲線上の近傍点の接線の傾きと比較する
２、１の差が許容範囲内ならば２点は直線に近いと判断する
３、１の差が許容範囲外ならば２点間は曲がっているので２点間の中央で分割し再度１の判定を再帰的に行う
４、１～３までを繰り返し曲線を点で分割する
５、４で得られた点群とクリックされた点が直線上に位置するかを計算する
６、５で直線上に存在すれば曲線がクリックされたとする
７、５で直線上に存在しないならば曲線はクリックされていないとする

上記の計算に必要なものを解説していく。

曲線上の任意の点の計算方法
Cubic bezier curveの式を使うと簡単に任意の点を取得できる。Cubic bezier curveの式は以下。

b(t) = p0*(1-t)^3 + p1*3t(1-t)^2 + p2*3(1-t)t^2 + p3*t^3

p0は始点、p3が終点、p1、p2はそれぞれ制御点の１と２だ。これに時間であるtを０～１の間で指定すると曲線上の任意の点が取得できる。

曲線上の任意の点の接線の傾きの計算方法
これもCubic bezier curveの式の導関数を使えば簡単に計算できる。式は以下。

b'(t) = 3(1-t)^2(p1-p0) + 6(1-t)t(p2-p1) + 3t^2(p3-p2)

p0～p3とtの説明は前述したものと同じだ。

上２つの式はWikipediaを見てもらったほうが分かりやすいと思う。

任意の点が２点間の線上に存在するかの計算方法
任意の点Pが線AB上に存在するならば距離AB＝距離AP+距離PBが成り立つ。

コード解説
ここから実際にいくつかコードを見ていこう。

まずは曲線上の任意の点を取得するコード。pointsは始点、制御点１、制御点２、終点の配列だ。

function b0(t) { return Math.pow(1 - t, 3); };
function b1(t) { return t * Math.pow(1 - t, 2) * 3; };
function b2(t) { return (1 - t) * Math.pow(t, 2) * 3; };
function b3(t) { return Math.pow(t, 3); };
function getPointOnBezier(points, t){
 var x = points[0].x * b0(t) + points[1].x * b1(t) + points[2].x * b2(t) + points[3].x * b3(t)
  , y = points[0].y * b0(t) + points[1].y * b1(t) + points[2].y * b2(t) + points[3].y * b3(t);
 return new Point(x, y);
};

ついで曲線上の任意の点の接線の傾きを取得するコード。ここもpointsは始点、制御点１、制御点２、終点の配列だ。

function bd0(t) { return 3 * Math.pow(1-t, 2); };
function bd1(t) { return 6 * (1-t) * t; };
function bd2(t) { return 3 * Math.pow(t, 2); };
function getSlopeOfTangentLine(points, t){
 var x = bd0(t) * (points[1].x-points[0].x) + bd1(t) * (points[2].x-points[1].x) + bd2(t) * (points[3].x-points[2].x)
  , y = bd0(t) * (points[1].y-points[0].y) + bd1(t) * (points[2].y-points[1].y) + bd2(t) * (points[3].y-points[2].y);
 return y/x;
};

曲線を直線に分割していくコード。mDiffやdDiffのしきい値をどこに設定するかで分割する大きさが変わってくるので上手いこと調整してもらいたい。

function calculateDividingPoints(){
 var points = []
  , bi = bezierInfo
  , i;
 for(i = 0.1; i <= 1.0; i += 0.1){
  divideCurveRecursively(bi, points, i-0.1, i); 
 }
 points.push(bi.points[bi.points.length-1]);
 bi.dividingPoints = points;
};
function divideCurveRecursively(bi, points, t1, t2){
 var prevD = getSlopeOfTangentLine(bi.points, t1)
  , currentD = getSlopeOfTangentLine(bi.points, t2)
  , dDiff = Math.abs(Math.abs(prevD)-Math.abs(currentD))
  , mDiff = t2-t1
  , middleT = t1 + mDiff / 2;
  
 if(mDiff > 0.05 && (sign(prevD) !== sign(currentD) || dDiff > 0.2)){
  divideCurveRecursively(bi, points, t1, middleT);
  divideCurveRecursively(bi, points, middleT, t2);
 }
 else
  points.push(getPointOnBezier(bi.points, t1));
};

任意の点が２点間の線上に存在するかをチェックするコード。これも許容値を変更することで当たり判定を厳しくしたりゆるくしたりできるので上手いこと調整してもらいたい。

function onStraightLine(pt){
 var bi = bezierInfo
  , i;
 for(i = 1; i < bi.dividingPoints.length; i ++){
  var p1 = bi.dividingPoints[i-1]
   , p2 = bi.dividingPoints[i]
   , trueDistance = calculateDistance(p1, p2)
   , testDistance1 = calculateDistance(p1, pt)
   , testDistance2 = calculateDistance(pt, p2);
  if(Math.abs(trueDistance - (testDistance1 + testDistance2)) < 0.2)
   return true;
 } 
 return false;
};

ざーっと解説してきたけれどCubic Bezierの公式さえ分かっていればさほど難しくないと思う。フレームワークから提供される曲線のあたり判定などは多量の曲線が存在する場合にボトルネックになったりもするので自前で計算できるよう公式を理解しておいても損はないだろう。処理実行の最適化などはまったく考慮していないので使用メモリだったり処理時間などを勘案して計算処理をキャッシュするなどは実際のコードベースでは行ったほうがよいと思われる。