点と線分の当たり判定

アバター
ナムアニクラウド
記事: 16
登録日時: 15年前
住所: 茨城県

点と線分の当たり判定

投稿記事 by ナムアニクラウド » 13年前

 いつの間にか2週間が過ぎていた。
今回は点と線分の当たり判定を紹介します。
segment1.PNG
segment1.PNG (5.6 KiB) 閲覧数: 141 回
線分AB, 点P, Q, R があり、P は AB に当たっており、Q,R は AB に当たっておりません。
このとき、何らかの方法で点P と他の点を区別する必要があります。
そこで、線分ABの端点と対象の点P,Q,Rをつなぐベクトルを考えます。これを点P,Q,Rに関するベクトルと呼びましょう。
次のようになります。
segment2.png
segment2.png (8.36 KiB) 閲覧数: 152 回
Pに関するベクトルは逆向きです。
Qに関するベクトルは並行ではありません。
Rに関するベクトルは同じ向きです。
このことから、当たっている点に関するベクトルは逆向きになることが推測できます。
2つのベクトルが逆向きになっていることはどうやって調べればよいでしょう?
ここで、前回紹介した「ベクトルの内積」を使うと、2つのベクトルが逆向きになっているかどうかが分かります。

ベクトルの内積は次のように求めるのでした。
  ab = |a||b|cosθ
いま、2つのベクトルが逆向きなら、θ = 180°です。このとき、cosθ = -1 となります。
すると、互いに逆向きのベクトル AP, BP について、次のことが言えます。
  APBP = -|AP||BP|
これを、点と線分の当たり判定の条件とします。

APBP = -|AP||BP| ⇔ 点P と線分AB は当たっている

証明はイマイチ面白くないと思ったので割愛です。

アバター
GRAM
記事: 164
登録日時: 14年前

RE: 点と線分の当たり判定

投稿記事 by GRAM » 13年前

点に大きさがないのならいっそのこと
AB = a, AP = p として

double x = p.x / a.x;
double y = p.y / a.y;

当たってるなら 0 ≦x(or y)≦1 かつ|x-y| ≦ε みたいにしたほうがシンプルかなぁ~とか思いましたがどうでしょう?

アバター
ナムアニクラウド
記事: 16
登録日時: 15年前
住所: 茨城県

Re: 点と線分の当たり判定

投稿記事 by ナムアニクラウド » 13年前

 なるほど、と思いまして、ひとまず証明もしました。確かに正しく当たり判定ができそうです。
これは確かにシンプルですね!
これなら内積を使う方法に比べて計算量も抑えられそうです。
自分もこのように実装してみたいと思います。アドバイスありがとうございました。