投稿者 tel | 2013年1月14日

直線と線分の当たり判定

直線と線分の交差判定

直線と線分が交差しているかどうかは、外積を使って求めることができる。

z座標を0として外積を求めるとxy平面に垂直なベクトルが計算されるので、このベクトルの向き(z座標の符号)を使う。

line_to_seg

(a-q)×dと(b-q)×dそれぞれの外積を求める。交差している場合、求めたzの符号が逆になる。

直線と線分の交点

直線の式。dが方向、qが基準点、tが媒介変数(直線なのでtの範囲は-∞<t<∞)。

line

線分の式。sが媒介変数(0<=s<=1)。

seg

直線と線分が交点pを持つとして計算するとtとsは以下の式になる。

point_s

point_t

tとsを元の式に戻すと交点pが求められる。

実際にコードにしてみたサンプル
http://jsdo.it/sapphire_al2o3/Ly9z

追記

sの導出についてコメントを頂いたので、面積の比からsを求める。

線分と直線で作られる三角形をS1(点a,p,qからなる三角系)とS2(点b,p,qからなる三角形)とすると面積比sは線分の式の媒介変数sと同じになる。(交点pが線分abのどの割合の位置にあるかを表す値なので)
三角系の面積は外積の絶対値の半分なので以下のようになる。

cross_0

ここでS1とS2で使った外積は同じ方向を向く、つまり符号が同じになるので絶対値を外してもsを求められる。S1とS2の絶対値の中の部分を展開して計算すると

cross_1

絶対値をとっぱらってsを求める式に入れると1/2とtが約分できるので

cross_2

上にあるsの式と一致する。


Responses

  1. はじめまして。参考にさせていただいています。

    function intersection関数内の、

    var det = line.d.x * dy – line.d.y * dx;
    var s = 1 / det * (-line.d.y * (line.p.x – seg.p0.x) + line.d.x * (line.p.y – seg.p0.y));

    が理解できません。

    比率を求めているようですが、なぜこのような式で比率が求めることができるのか
    わかりません。

    自分のプログラムの交点をもとめる関数は次のような感じで実装しています。しかし、理解できるなら、function intersection関数の仕様に、置き換えたいです。

    function intersection2(line, seg) {
    var v = {};
    var tpt1 = {};
    var tpt2 = {};

    v = {x:(line.d.x + line.p.x)- line.p.x , y: line.d.y };
    tpt1 = {x:seg.p0.x – line.p.x, y: seg.p0.y – line.p.y};
    tpt2 = {x:seg.p1.x – line.p.x, y: seg.p1.y – line.p.y};

        // 外積を求め、比率を算出 三角形の面積の比率
    var g1 = Math.abs(cross( v, tpt1)) / 2;
    var g2 = Math.abs(cross( v, tpt2)) / 2;
    var s = g1/(g2+g1);

    var dx = seg.p1.x – seg.p0.x,
    dy = seg.p1.y – seg.p0.y;

    return {
    x: s * dx + seg.p0.x,
    y: s * dy + seg.p0.y
    };
    }

    ヒント、参考URLなんでも結構です。教えていただけたらありがたいです。

  2. こんにちは。

    ブログでのせたのは直線と線分の方程式で連立方程式を作ってsとtを求める方法でしたが、お載せいただいた面積の比率でも同じsを求める式が導けるかと思います。

    var g1 = Math.abs(cross( v, tpt1)) / 2;
    var g2 = Math.abs(cross( v, tpt2)) / 2;
    var s = g1/(g2+g1);

    三角形の面積を求める際に、割る2するのはg1/(g2+g1)で分母と分子にかかってくるので消すことができます。またg2で外積のかける順番を反対(cross(tpt2, v))にすれば、g1とg2で符号が一致しますので絶対値を取る必要がありません。

    これをふまえて外積の式を展開して計算するとブログで載せているsの計算式と一致するかと思います。

    • ご返事ありがとうございます。感謝します。
      ブログで勉強させてもらっています。ありがとうございます。
      数学のレベルが中卒レベル(もあやしい)から、
      幾何学中心に只今勉強中でして、プログラムがあるので、
      イメージがつかみやく助かっております。

      ありがとうございました。

  3. 導出する式を追記しましたので参考になれば幸いです。


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

カテゴリー

%d人のブロガーが「いいね」をつけました。