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


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

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2017/06/11 12:47:11
  • 終了:2017/06/18 12:50:03

回答(1件)

id:gfik No.1

いつか回答回数6ベストアンサー獲得回数32017/06/13 06:47:43

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

なので
三角錐の頂点を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のポリゴン処理プログラムを思い出しながら書いています。
書き忘れがあったらごめんなさい。

他3件のコメントを見る
id:nononon7

いつか様
 いつもお世話になっております。  早速のご回答ありがとうございます
 誤判定してまう組み合わせをお送りします。
  (グラフ画像もありますが、ファイル添付できませんでしたので、テキストだけでお送りします)
 ご検討よろしくお願い致します。

    x y z
評価点     0.5796 0.5632 0.459

点列 1 0.5796 0.5632 0.459
2 0.4869 0.4409 0.2331
3 0.2622 0.0843 0.5874
4 0.061 0.7681 0.6608
5 0.8783 0.5393 0.861

判定結果
面番号  点の組み合わせ  評価点 1 2 3 4 5 真の数
1 1 2 3 4 5      4真 5偽 4
2 1 2 4 3 5      3真 |(5真) 4
3 1 2 5 3 4 5が偽なので未判定 | 4
4 1 3 4 2 5      2偽 ↓(5真) 3
5 1 3 5 2 4 【真の数が3になったので外側判定】

2017/06/19 19:23:23
id:gfik

すみません、
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点が真なので判定は”含まれる”
となると思っています。

2017/06/20 20:11:50

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません