3次元空間上の対象点が、同じ空間上の三角錐の中に入っているか、外側にあるか判定するには
どうすればいいでしょうか?
よろしくお願いします。
さらには、複数点(20個程度)の凸包のなかにあるかどうかの判定方法も教えてください。
三角錐のすべての面に対して、
面に含まれない頂点と判定する点が、
面で区切られた空間の同じ側にあるなら、
判定する点は三角錐の中にあります。
なので
三角錐の頂点を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のポリゴン処理プログラムを思い出しながら書いています。
書き忘れがあったらごめんなさい。
いつか様
2017/06/19 19:23:23いつもお世話になっております。 早速のご回答ありがとうございます
誤判定してまう組み合わせをお送りします。
(グラフ画像もありますが、ファイル添付できませんでしたので、テキストだけでお送りします)
ご検討よろしくお願い致します。
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/20 20:11:503点を含む平面に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点が真なので判定は”含まれる”
となると思っています。