人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

三角錐の中に任意の対象点があるかどうか判定するにはどうすればいいでしょうか?

3次元空間上の対象点が、同じ空間上の三角錐の中に入っているか、外側にあるか判定するには
どうすればいいでしょうか?
よろしくお願いします。
さらには、複数点(20個程度)の凸包のなかにあるかどうかの判定方法も教えてください。

●質問者: nononon7
●カテゴリ:科学・統計資料
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● いつか
ベストアンサー

三角錐のすべての面に対して、
面に含まれない頂点と判定する点が、
面で区切られた空間の同じ側にあるなら、
判定する点は三角錐の中にあります。

なので
三角錐の頂点をabcd、判定する点をpとします。
abcを含む平面と線分dpが交差しない。
abdを含む平面と線分cpが交差しない。
acdを含む平面と線分bpが交差しない。
bcdを含む平面と線分apが交差しない。
上の4つがすべて真なら
ただし、点pが平面に含まれる場は交差しないとします。
点pは三角錐abcdの中にあることになります。

以下リンク先を参考にして下さい。
平面の求め方
http://www.sousakuba.com/Programming/gs_plane.html
線分と平面が交差するかの判定方法
http://www.sousakuba.com/Programming/gs_plane_line_intersect.html

>さらには、複数点(20個程度)の凸包のなかにあるかどうかの判定方法も教えてください。

判定する点を点pとします。
凸包の点すべてに真偽を付けられるようにします。
初めにすべての点を真にします。

真の頂点から任意の3点を選びます。
選んだ3点を含む平面で区切られた空間で、p点と反対側の点を偽にします。
同一頂点の組み合わせにならないように3点を選んで繰り返し処理していきます。
3点を含む平面にp点が含まれた場合、次の3点を選びます。

すべての真の頂点の組み合わせを処理した後に
真の点の数が3個 => p点は凸包の中に無い
ただし、その3点を含む平面にp点が含まれる場合は、
3点の三角形の中に有るなら、p点は凸包の中に有る。
3点の三角形の中に無いなら、p点は凸包の中に無い。
真の点の数が4個 => p点は凸包の中に有る

となります。

昔自作していた3Dのポリゴン処理プログラムを思い出しながら書いています。
書き忘れがあったらごめんなさい。


nononon7さんのコメント
ご親切なご回答誠にありがとうございます。前半部分は作って動作させる事が出来ました。 後半についても、チャレンジしてみます。動きましたら、ご報告させていただきます。 ありがとうございました。

nononon7さんのコメント
いつもお世話になっております。 凸包はなかなかうまくいきません。(点配置の条件によっては、間違えてします) 再度質問させてください。 一度偽になった点については、その後は無いものとして (真偽の)評価点及び平面用の3点の組み合わせから除外してもいいのでしょうか? それとも、面を変えるたびに再評価するのでしょうか? サンプルプログラム等はございませんでしょうか。 よろしくお願いします。

いつかさんのコメント
確認が遅れてすみません。 > (真偽の)評価点及び平面用の3点の組み合わせから除外してもいいのでしょうか? はい、そうです。 >サンプルプログラム等はございませんでしょうか。 すみません、10年以上前に勉強のために作ったものなので たぶん残っていません。 古い記憶を思い出して書いているため、何か抜けているのかもしれません。 再度確認してみます。

nononon7さんのコメント
いつか様 いつもお世話になっております。 早速のご回答ありがとうございます 誤判定してまう組み合わせをお送りします。 (グラフ画像もありますが、ファイル添付できませんでしたので、テキストだけでお送りします) ご検討よろしくお願い致します。 xyz 評価点 0.57960.56320.459 点列10.57960.56320.459 20.48690.44090.2331 30.26220.08430.5874 40.0610.76810.6608 50.87830.53930.861 判定結果 面番号 点の組み合わせ 評価点12345真の数 112345 4真5偽4 212435 3真|(5真)4 3125345が偽なので未判定|4 413425 2偽↓(5真)3 513524【真の数が3になったので外側判定】

いつかさんのコメント
すみません、 3点を含む平面にp点が含まれた場合、次の3点を選びます。 を処理していないように思います。 実際にプログラムを組んでいません 数字から頭で処理しています。 (a,b,c) は「abcの3点からなる面で判定する」を表します。 (1,2,3) 評価点が面に含まれるので処理しない (1,2,4) 評価点が面に含まれるので処理しない (1,2,5) 評価点が面に含まれるので処理しない (1,3,4) 評価点が面に含まれるので処理しない (1,3,5) 評価点が面に含まれるので処理しない (1,4,5) 評価点が面に含まれるので処理しない (2,3,4) 点5が偽になる (2,3,5) 点5が偽のため処理しない (2,4,5) 点5が偽のため処理しない (3,4,5) 点5が偽のため処理しない 点1,2,3,4が真 4点が真なので判定は”含まれる” となると思っています。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ