• ベストアンサー

数学orアルゴリズムが得意の方（線分と線分の交点判別）

Ｃ言語のアルゴリズムを勉強中です。 線分Ａ（A(x1,y1),B(x2,y2))と線分Ｂ（C(x3,y3),D(x4,x4))が交差するかどうかを判別し、交差するのであればその交点Ｐ(X,Y)を求める。 また、その交点がどちらか一方の線分上にあるかどうかも判別したいのです。 一番効率よくやるにはどのようにすればよいでしょうか。 例えば １、三角形の符号付き面積を使って交差するかどうかと各点が線分上にあるかどうかを判別し、その後交点を求める ２、とり合えず交点を求めてその交点が各線分内(上)にあるかどうかを判別 他にもたくさんありそうですがとにかく出来るだけ計算回数を減らしたいのです。（さっき求めた～～を～～するといったかんじで） 出来れば流れ全体を書いていただきたいのですが書き込むのが大変だと思うのでせめて使う判別式だけでも教えてください。 これが出来たら、 多角形と多角形の交点判別のアルゴリズムにも挑戦しようと思っています。 数学の得意な方、アルゴリズムを考えるのが好きな方 よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • hogehoge2
  • ベストアンサー率100% (1/1)
回答No.6

No.4,5のhogehoge2です。何度もすみません。 間違っていましたので、訂正いたします。 次の部分を ---------------------------------------- (2) 　det==0のとき(3)へ 　その他(else)のとき(6)へ (3) 　y1==y2のとき(4)へ 　その他のとき(5)へ ---------------------------------------- 次のようにご訂正ください。 ---------------------------------------- (2) 　det==0のとき(3)'へ 　その他(else)のとき(6)へ (3)' 　(x3-x1)*(y4-y1)-(y3-y1)*(x4-x1)==0のとき(3)へ 　その他のとき　線分ＡＢ、ＣＤは共有点をもたない。 関数の終り (3) 　x1==x2のとき(4)へ 　その他のとき(5)へ ---------------------------------------- 以上

kiku_kiku
質問者

お礼

回答ありがとうございます。 なんとかなりました…（たぶん） 何度も回答していただき感謝してします。

その他の回答 (5)

  • hogehoge2
  • ベストアンサー率100% (1/1)
回答No.5

No.4のhogehoge2です。間違っていましたので、訂正いたします。 A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4) ただし、x1≠x2 or y1≠y2,x3≠x4 or y3≠y4とする。 以下は、共有点を持つか、持たないかを判別する関数を想定したものです。 (1) 　det=(x2-x1)*(y3-y4)-(y2-y1)*(x3-x4) 　とする。 (2) 　det==0のとき(3)へ 　その他(else)のとき(6)へ (3) 　y1==y2のとき(4)へ 　その他のとき(5)へ (4) 　(y3-y1)*(y4-y1)<=0 || (y3-y2)*(y4-y2)<=0 || (y1-y3)*(y2-y3)<=0 || (y1-y4)*(y2-y4)<=0のとき 　線分ＡＢ、ＣＤは共有点をもつ。（無数または一つ） 　その他のとき　線分ＡＢ、ＣＤは共有点をもたない。 関数の終り (5) 　(x3-x1)*(x4-x1)<=0 || (x3-x2)*(x4-x2)<=0 || (x1-x3)*(x2-x3)<=0 || (x1-x4)*(x2-x4)<=0のとき 　線分ＡＢ、ＣＤは共有点をもつ。（無数または一つ） 　その他のとき　線分ＡＢ、ＣＤは共有点をもたない。 関数の終り (6) 　da1=y1*x2-x1*y2+x1*y3-y1*x3+y2*x3-x2*y3 　db1=y1*x2-x1*y2+x1*y4-y1*x4+y2*x4-x2*y4 　da2=y3*x4-x3*y4+y1*x3-x1*y3+x1*y4-y1*x4 　db2=y3*x4-x3*y4+y2*x3-x2*y3+x2*y4-y2*x4 　 　d1=da1*db1 　d2=da2*db2 とするとき (7) 　d1<=0 && d2<=0 のとき　線分ＡＢ、ＣＤは交点をもつ。 　その他(else)のとき 線分ＡＢ、ＣＤは共有点をもたない。 関数の終り 線分ＡＢ、ＣＤが交点をもつときは 交点の座標は２元連立方程式で解くだけです。 以上

  • hogehoge2
  • ベストアンサー率100% (1/1)
回答No.4

お役に立つかわかりませんが。 (1) 　da1=y1*x2-x1*y2+x1*y3-y1*x3+y2*x3-x2*y3 　db1=y1*x2-x1*y2+x1*y4-y1*x4+y2*x4-x2*y4 　da2=y3*x4-x3*y4+y1*x3-x1*y3+x1*y4-y1*x4 　db2=y3*x4-x3*y4+y2*x3-x2*y3+x2*y4-y2*x4 　 　d1=da1*db1 　d2=da2*db2 とするとき (2) 　d1<=0 and d2<=0 のとき　線分ＡＢ、ＣＤは共有点を持ちます。 　その他(else)のとき 線分ＡＢ、ＣＤは共有点を持ちません。 　共有点の判定はこれでできます。 上の共有点を持つ場合の処理ですが (3) 　(x2-x1)*(y3-y4)-(y2-y1)*(x3-x4)=0 　のとき　無数の共有点を持ちます。 (3)' 　(x2-x1)*(y3-y4)-(y2-y1)*(x3-x4)≠0 　のとき　ただ１つの交点を持ちます。 　交点の座標は２元連立方程式で解くだけです。 以上

  • g_dori
  • ベストアンサー率47% (330/699)
回答No.3

あらら、失礼しました。 私がやるとしたら、こんな感じでしょうか。 １．四角形ａ｛x1,x2,y1,y2｝と四角形ｂ｛x3,x4,y3,y4｝の当たり判定を求める ２．(x1,y1)を零点として全部の座標を修正（オーバーフローをこれで防ぎます） ３．あとは適当（笑） １の四角形の当たり判定は、乗算２回よりも軽く済むはずですので、ないよりはマシだと思います。いきなり計算に入ると非常に重いです。 ２は正確性を求めて。。。 ←ゲームで導入しようとして挫折した経験者でした（笑）

  • g_dori
  • ベストアンサー率47% (330/699)
回答No.2

今更申し訳ないのですが。。。 どのようなプログラムなのか、それからはじめた方が良いんじゃないでしょうか？ 多分ゲームか何かじゃないかと推察しますが、高速処理を追及するソフトでの単純な当たり判定をご希望でしたら、お考えのアルゴリズムは使いませんよ。 多角形同士の当たり判定や、傾きのある直線同士の当たり判定は重すぎる上に、値によっては正確なあたり判定が行えないので、まず使いません。（ちょっと大きな値を使うと、double型でも計算時にオーバーフローします） 交点を求めると言うことは、x1～4、y1～4、X、Yは全て浮動小数演算にならざるを得ないと思いますが、高速処理を追及するなら、そのあたりから既に無駄じゃないでしょうか。 整数しか使わないか、１未満の小数しか使わないプログラムだと言う事ならまだわかりますが、そうでないならそこの点から改善された方が、全体的なスピードアップになると思います。 そして、当たり判定は四角形のみで行う・・と。 正確な当たり判定のアルゴリズムよりも、正確でなくてもそれを誤魔化すアルゴリズムを考えた方が無難じゃないでしょうか。 ひとつの物体に対して四角形の当たり判定をいくつか用意すれば、それなりに当たっているように見えますよ。 最近の３Ｄゲームも全部そうやっているはずですので。。。 勘違いならゴメンなさい！

kiku_kiku
質問者

お礼

回答ありがとうございます。 ゲームではないのですが高速処理を追及するソフトです。(正確にはできるだけ…） 一応、断りを入れておきますが、課題や卒論等の類ではありません。 仕事の関係であったらいいな。と思って学生のころの知識でつくっているソフトです。 最悪、1000角形の２乗回演算することになるので少しでも早いほうがと思い、このような質問をさせていただきました。

  • hinebot
  • ベストアンサー率37% (1123/2963)
回答No.1

交差するかどうかなら、傾きを比べれるのが一番簡単でしょう。 ABの傾き (y2-y1)/(x2-x1) CDの傾き (y4-y3)/(x4-x3) これが、一致しなければ必ずどこかで交差します。 （傾きが一致　⇒　ABとCDは平行　です） ただし、x2-x1 = 0 or x4-x3=0 のときだけ注意が必要です。 x2-x1=0(つまりx1=x2)かつx4-x3=0(つまりx3=x4)ならば、ABとCDは平行 それ以外は交差します。 結論ですが、 (y2-y1)(x4-x3)と、(y4-y3)(x2-x1)　を計算して両者を比較し、 一致すれば交差しない（平行）、不一致ならば交差します 次に、実際に交点を計算しますが、x2-x1=0 or x4-x3=0 でない限り計算するのはｘ座標だけで構いません。 交点の座標を仮にP(xp,yp)とします。 x1＜x2　として、 x1≦xp≦x2　であるかどうかを調べます。 x1≦xp≦x2であれば、交点は線分AB上にあります。 同様に x3＜x4として x3≦xp≦x4であれば、交点は線分CD上にあります。 （x2-x1=0 or x4-x3=0 のときはx座標の変わりにｙ座標を計算してください。） 簡単にまとめると <1>(x2-x1),(x4-x3),(y2-y1),(y4-y3)の４つの値を計算する <2> <1>から　(y2-y1)(x4-x3)と、(y4-y3)(x2-x1)　を計算 <3>　２つの値が一致するか判定（交差の判定） <4> 交差する場合、交点のx座標（またはy座標）を計算する 　　ここで、x座標にするかy座標にするかは、x2-x1,x4-x3 が０かどうかで判定する。 <5> 交点のx座標（またはy座標）がでたら、AとBの座標との大小を比較する 　　同様に、CとDの座標との大小を比較する（交点が線分上にあるかを判定） こんな感じかな。

kiku_kiku
質問者

お礼

回答ありがとうございます。 やはり 交点があるかどうかをチェックしてから交点を求めるより 交点を求めてから線分上にあるかどうかをチェックしたほうが効率がいいのですね。 仮に多角形同士の交点に応用する場合等、交点があるかどうかすらきわどい場合が多い場合でもこの流れの方が効率が良いのでしょうか？ それとも場合によっては変えたほうが良いのでしょうか？

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ２つの線分に垂直な線分の交点

    ２次元平面に点P(x0,y0)、点A(x1,y1)、点B(x2,y2)があり、 点Aを通る線分PAに垂直な線分と 点Bを通る線分PBに垂直な線分の交点の 求め方を教えて下さい。 垂直ベクトルを求め、任意に座標を決めて 連立方程式を解くやり方だと上手くいかない時が あります。シンプルに求める方法がありましたら 教えて下さい。

  • 直線と線分の交差判定について高速なアルゴリズム

    タイトルの通りなのですが、 まさにその部分をプログラムで作っている最中です。 直線 : ax+by+c=0　で言うところの a,b,c のパラメータと 線分の2端点 ( x1 , y1 ) , ( x2 , y2 )　がわかっています。 その情報を使って今は 　( ax1 + by1 + c ) * ( ax2 + by2 +c ) < 0 のときに交差している。 という風に処理しているんですが、 どうにもこの部分の処理で時間がかかっているみたいで、 なんとか高速化したいんですが、直線と線分の交差判定について触れてあるサイトが少なかったり、 今使っているアルゴリズムのサイトだったりしか見かけないので、どうにもこうにもなりません。 もしこれが最速のアルゴリズムならしかたないんですが、もし皆さんご存知でしたらお力添えをお願いします。

  • 線分の交点の保持

    いつもお世話になってます。 ２つ以上の線分が２次元上にあって、線分が交差した場合それぞれの交点を保ちながらも移動し、交点で回転しながら他の線分とも衝突判定を行う、というアルゴリズムを考えているのですがなかなかうまくいかず悩んでいます。 最終的にはたくさんの線分がくっついて、くねくねしながら移動するようなイメージです。 速度を同じにして、交点を軸に回転させてみたのですが、３本目の線分が交差したときうまくいかなくなってしまいました・・。 ぜひ皆さんの力を貸してください。よろしくお願いします。

  • 線分同士の交点の判定

    線分の交差判定についてネットで調べていたら、以下のような処理で できると書かれていたページがあったのですが、どうしても理解する事が できません。 もしできれば、解説を頂いてもいいでしょうか。 よろしくお願いします。 //２次元での線分と線分の交差判定と交点 BOOL CheckCrossLine(CONST D3DXVECTOR2* pvA1, 　　　　　　　　　　CONST D3DXVECTOR2* pvA2, 　　　　　　　　　　CONST D3DXVECTOR2* pvB1, 　　　　　　　　　　CONST D3DXVECTOR2* pvB2, 　　　　　　　　　　D3DXVECTOR2* pvOut) { D3DXVECTOR2 v1 = *pvA1 - *pvB1; D3DXVECTOR2 vA = *pvA2 - *pvA1; D3DXVECTOR2 vB = *pvB2 - *pvB1; if (*pvA1 != *pvA2) ; else return FALSE;//線分が点のときは交差していないとする if (*pvB1 != *pvB2) ; else return FALSE;//線分が点のときは交差していないとする FLOAT fDeno = vA.x * vB.y - vA.y * vB.x;//外積の長さ //分母が０で、平行なときは if (fDeno != 0.0f) ; else return FALSE;//交差していないことにする FLOAT t = (v1.y * vB.x - v1.x * vB.y) / fDeno; FLOAT s = (v1.y * vA.x - v1.x * vA.y) / fDeno; if (t < 0.0f || t > 1.0f || s < 0.0f || s > 1.0f) return FALSE;//交差していない else { //交点を返す pvOut->x = vA.x * t + pvA1->x; pvOut->y = vA.y * t + pvA1->y; return TRUE;//交差 }

  • 交差する２線分の交点座標の求め方

    ２つの線分が交差する場に交点の座標を求めようと思っています。 アドバイスを頂けないでしょうか？ 入力値：（aX1, aY1）（aX2, aY2） 　　　　（bX1, bY1）（bX2, bY2） 出力値：（X, Y） よろしくお願いします。

  • 数学（ベクトルの交点について求める問題）

    三次元空間中にある重ならない二点Ａ（x1,y1,z1）とＢ（x2.y2,z2）があって、Ａを通り、方向ベクトルV1=(a1,b1,c1)である直線Ｙ1とＢを通り、方向ベクトルＶ2＝（a2,b2,c2）である直線Ｙ2が,とある一点Ｃ（x,y,z）で交わる。Ａ,B,V1,V2が分かっているとき、点Ｃを求めなさい。という問題についてですが、 以下のような考え方（説明は下手ですが）で合っているのでしょうか？ ベクトル方程式より xについて x1+ｔa1＝x2+ｕa2 yについて y1+ｔb1＝y2+ｕb2 zについて z1+tc1＝z2+uc2 という考え方です。 間違っていれば指摘して頂ければ幸いです。 また、ここから交点Cについてどのように求めればよいのでしょうか？

  • 数学の得意な方教えてください

    解答をみても分からない問題があります 問題 図のように、関数ｙ＝ｘｘ(xの2乗です)、ｙ＝axxのグラフがある。 点(３、０)を通りｙ軸に平行な直線と、これらのグラフ、 ｘ軸との交点をA、B、Cとする。 また、Aを通りｘ軸に平行な直線がｙ＝axxのグラフと交わる点を Dとし、Dからx軸に垂線DEをひく。 △ABOの面積を、aを使って表しなさい。 答え→2分の２７－2分の２７a 解説が点Bの座標は(３、９a)だから…と書いてあるのですが なぜ９aなのですか？ 教えてください。

  • 数学の得意な方、助けて下さい。

    現在中３です。この度、高校に無事合格し、宿題が提示されました。 その問題につき、次の2題の解説をお願いします。 2直線y=mx…(1)とy=-1/m+2…(2)がある（mは0ではない） 解説が欲しいのは、この(4)です。 (4)2直線とy軸で囲まれた部分を、y軸の周りに１回転してできる立体の体積の最大値を求めよ。 一応、私の考えを、 2直線の交点Hとすると、最大値は、∠HAB＝∠HBA＝45°のときである。 すなわち、Hの座標は、（1,1） 立体の体積は、1×1×π×1×1/3×2＝2π/3でしょうか。 念のため、(1)～(3)も入れておきます。 (1)直線(1)はmの値に関わらず点Aを必ず通り、直線(2)はmの値に関わらず点Bを必ず通る。2点A,Bを座標を示せ。 答 Ａ（0,0） B（0,2） (2)m-2のとき、2直線(1)と(2)のなす角を求めよ。 答 90° (3)mが0以外の色んな値をとるとき、2直線(1)と(2)の交点Pはどのような曲線上にあるか説明せよ。 答 ABを直径とする円周上で点A,B以外 もう一問は、 y=axの2乗（a＞0）(1)とy=bx+c(2)について、-1≦x≦3におけるyの変域が等しくなるようにb,cをaを用いて表せ。 一応、私の考えを a＞0より、 (1)は、x＝0のとき，最小値y=0。x＝3のとき，最大値y=9a このとき、(2)は、 x＝-1のとき，最小値y=0になり、b=c x＝3のとき，最大値y=3b+c 9a=3b+cとb=cより，b=c=9a/4　でしょうか。

  • 数学について

    曲線C:x^(2)/a-y^(2)/b=1上の点P(x1,y1)におけるこの曲線の接線をlとする。直線lと曲線Cの2つの曲線Cの2つの漸近線との交点をそれぞれA,Bとし、原点をOとする。また、線分OPを直径とする円と曲線Cの2つの漸近線とのO以外の交点をそれぞれQ,Rとする。ただし、a,bは正の定数とする。 ・直線lの方程式を求めよ。 ・点P(x1.y1)は線分ABの中点であることを示せ。 ・三角形OABの面積は点P(x1.y1)の位置によらず一定であることを示せ。 ・2つの線分PQ,PRの長さをそれぞれd,d'とするとき、積dd'は点P(x1.y1)の位置によらず一定であることを示せ。 について教えて下さい。 全部に答えなくても結構です。 よろしくお願いです。m(__)m

  • ２直線の交点の軌跡は、判別式を用いて求められますか

    mが実数全体を動くとき、次の２直線の交点Pはどんな図形を動くか。 (1)　mx - y = 0 　　　(2) x + my - m - 2 = 0 という問題について、解説ではmを消去する方針で、(1)からm = y / x　を導き、(2)に代入しています。 ですが、たとえばyを消去する方針で、(1)からy = mxを導いて(2)に代入して x + m^2x - m - 2 = 0 とし、これをmについてまとめて、xm^2 - m + x -2 = 0とした場合、 この式は(1)と(2)を同時に満たす式となり、判別式D = 0となるとき１つの交点をもつ、というように解くことはできないのでしょうか？ ちなみに、これを解くとD=0より4x^2 - 8x - 1 = 0となり、解答（x-1)^2 + (y-1/2)^2 = 5/4とは全く異なってしまうので、間違った解き方だということはわかるのですが、なぜこの解き方では解答に辿りつけないのかがわかりません。 判別式をここで持ち出すこと自体、おかしいのでしょうか？ 変な質問ですが、よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する