線分と円が交差する条件

線分と円(6つの値)があります
線分:(ax1,ay1)-(ax2,ay2)
円:中心(x1,y1)半径r

この6つの値から
線分が円に含まれる、或いは円と交差する条件を判定したいのですが
まるで検討がつきません。
円の式は (x - x1)^2 + (y - y1)^2 = r^2
でしょうか。(自信無し)

リアルタイムにコンピューターで計算するため
出来れば少ない計算量で計算させたいのですが。。。
宜しくお願い致します。

No.1 ベストアンサー 回答者： wataken44 回答日時： 2003/10/07 11:29

>円の式

(x - x1)^2 + (y - y1)^2 = r^2　でOKだと思います

説明のため点に名前をつけます
P(ax1,ay1) Q(ax2,ay2) R(x1,y1)
RPベクトル=p RQベクトル=q

さて、線分が円に含まれるor円と交差する条件ですが
　1.　PかQが円に含まれるとき→条件を満たす
　2.　1.以外のとき
　　2-1.RからPQに垂線RHを下ろし、その長さがr以下
　　2-2.角PQRと角QPRがともに鋭角

1.のとき、線分が円に含まれることは自明だと思います
2.の条件を満たせば線分が円と2つの交点を持つはずです

1.
　PR<=r or QR<=r

2.
2-1.
直線P1P2の式
y-ay1=(x-ax1)(ay2-ay1)/(ax2-ax1)
　注 P1をとおり傾きが(ay2-ay1)/(ax2-ax1)の直線
整理すると
Ax+By+C=0
　A=ay2-ay1
　B=ax1-ax2
　C=ay1*ax2-ax1*ay2
こうなります。

この直線とQとの距離dは
　d=abs(A*x1+B*y1+C)/sqrt(A^2+B^2)
となります。

このdを用いると求める条件は
　d<=r　(直線と円が交わるor接する)

2-2.
　PQベクトルとPRベクトルの内積>0　かつ、　
　QPベクトルとQRベクトルの内積>0
　従って、
　(q-p)・(-p)>0
　(p-q)・(-q)>0
　ベクトル表記を止めると
　(ax2-ax1)(x1-ax1)+(ay2-ay1)(y1-ay1)>0
　(ax1-ax2)(x1-ax2)+(ay1-ay2)(y1-ay2)>0

なにぶん急いで計算したので、一応検算はしてください
2次元ベクトル管理用のクラスを作ると楽かも

この回答へのお礼

ご回答ありがとうございます。
教えてくださったやり方で出来ました。

お礼日時：2003/10/07 17:37

No.3 回答者： keyguy 回答日時： 2003/10/07 16:50

問題の趣旨を間違っているときのために

交差するあるいは含まれる条件
（ａｘ１－ｘ１）＾２＋（ａｙ１－ｙ１）＾２≦ｒ＾２
または
（ａｘ２－ｘ１）＾２＋（ａｙ２－ｙ１）＾２≦ｒ＾２

この回答へのお礼

既に1さんの回答でプログラムを組んでしまいましたが
keyguyさんの計算方法でも今後参考にしたいと思います。
ご回答感謝しております。

お礼日時：2003/10/07 17:40

No.2 回答者： keyguy 回答日時： 2003/10/07 16:38

１でいいのかもしれませんが読む私の能力に難があるので分かりません。

私なりの回答を

含まれる条件
（ａｘ１－ｘ１）＾２＋（ａｙ１－ｙ１）＾２≦ｒ＾２
かつ
（ａｘ２－ｘ１）＾２＋（ａｙ２－ｙ１）＾２≦ｒ＾２

交わる条件
「（ａｘ１－ｘ１）＾２＋（ａｙ１－ｙ１）＾２≦ｒ＾２
かつ
ｒ＾２≦（ａｘ２－ｘ１）＾２＋（ａｙ２－ｙ１）＾２」
または
「ｒ＾２≦「（ａｘ１－ｘ１）＾２＋（ａｙ１－ｙ１）＾２
かつ
（ａｘ２－ｘ１）＾２＋（ａｙ２－ｙ１）＾２≦ｒ＾２」

なお×だけでなくＴも交差としました。
×だけの場合は容易く作れますね。