三次元のデータがある領域に含まれるかどうかの判断方法

質問

ある三次元のデータが複数あり、閉じた立体を構成しているとします。（Aとします）

そこに、あるデータaが、その立体の中にあるか、そとにあるか、という判断をしたいのですが、どうしたらよいのでしょうか？
ある立体Aは単純な立体ではないため、方程式などでは表わせません。

Aから順番に3点とって、その三角形とベクトルaが交点をもつかどうかで判断しようと思っているのですが、Aもaもデータが多すぎるため、プログラムの処理が終わりません。

何かよい方法はないでしょうか？

回答No.4

age_momo · ベストアンサー

立体Aを点群でしか表せないのですからAの形状や密度によって戦略を考える必要が
あると思います。形状が複雑でも全ての点において平面あるいは凸であるなら
近傍の点を探す戦略が有効だと思いますが、凹んでいる部分があるなら判断は複雑に
なると思います。例えば視力検査のCのように球形の中に球形の凹んだ部分が
あるならこの内側にあるaは立体Aの外側ですが完全に立体をメッシュなどで
定義してしまわないと外側という判断は出てきません。
(この『穴』が点群の密度より小さければ最早、立体Aを定義することすら無理のような気もします）

aの数が多くて時間がかかっているなら一旦Aの最小包括円(球)を定義して
(これならAの点の数が100万個程度ならほとんど時間はかかりません）
この外側にあるものは無条件に外側、それより小さいものは球の中心と点aを
結ぶ直線に対して角度が一番小さい点(∠An・O・aが最小)より点群Aの密度以上に
遠ければ外側、近ければ内側、その範囲内なら更に近傍の点群Aを探して
メッシュを形成して判断するという数段構えではどうでしょうか。
この戦略も形状がとんでもなく複雑なら誤判断が出てきそうですが。。。

いずれにせよ、Aの形状とデータ数(密度)と使えるメモリ量、色々な事情を勘案して
有効な戦術を考える必要があると思います。

お礼

ご回答、どうもありがとうございます。
おっしゃるとおり、形状がなかなか複雑でして、鋭角で凹んでる部分などがあり、困っておりました。

球のアイディアは、なるほど、たしかにそうですね。
そうするとかなり簡略化できそうです。
誤差の状況など考慮して、場合によってはやってみる価値はありそうです。

回答No.6

noname#101087

#5 です。途切れとぎれですみません。

フリーのツールを追加。
三次元グラフィックスの演習に向いているかも.. 。
---------------------------------------------
　http://www.sra.co.jp/people/nisinaka/Jun4Java/index_ja.html
>「じゅん」は，三次元グラフィックスおよびマルチメディアを扱うためのフレームワークとなる汎用クラスライブラリの名称です．

お礼

いろいろとありがとうございます。
フリーのツール、Javaのライブラリなどまであるとは知りませんでした。
以上のものを駆使して、試したいと思います。

回答No.5

noname#101087

>... ドロネー網というのですか。....
>ところで、こういうデータを処理するプログラムって、どういったものがあるのでしょうか。

(「ドロネー網」は「学界」用語のようで、「ゲー界」でいうところの「ポリゴンパッチ」でしょうか)

オンライン・ソフトなら、このあたりでしょう。
　http://www.softantenna.com/3.html#5
>マルチメディア//3D
データ互換性が懸念されますが、とりあえず調べてみてください。

回答No.3

noname#101087

三次元データAからドロネー網(三角形メッシュ?)を構成しておくのが正攻法みたいですが、三次元データAが変わるたびにやりなおしです。
三次元データAが変わらないのなら、初期投資(ドロネー網構成)の後は処理が迅速になりそうですけど...。

三次元データAはそのまま使うとして素朴な攻め方として頭に浮かぶのは、データaに最も近い四点をサーチして、データaが
その四点を頂点とする(四面体)凸包に含まれるか否かを判定する、というやりかたです。
　(1) 「最も近い四点」が一意的とは限らない。
　(2) 「最も近い四点」が同一平面上でないとは限らない。
などの障害が予想されるので、サーチ戦略が先決問題なのでしょうが... 。
(やったことがなく無責任なコメントになり、すみません)

お礼

ご回答、どうもありがとうございました。
なるほど、ドロネー網というのですか。
三次元データAは変わらないので、最初に構成するのはいいかもしれません。

ところで、こういうデータを処理するプログラムって、どういったものがあるのでしょうか。
普通に座標を計算することしかやったことないので、こういう三次元データを扱うにはどうしたら良いのでしょうか…。

回答No.2

__Kei__

立体Ａは点群で表されるということですよね。

近い点同士を結んでグラフ構造を作ることにより点群からメッシュへの変換を行い、このメッシュを簡略化することで計算時間を減らすというのはどうでしょうか？もちろん、簡略化のプロセスにより立体Ａの表面で小さなエラーが生じることになりますが。

お礼

ご回答、ありがとうございます。
やはり「メッシュ」がキーワードのようですね。
調べてみます。「近い点」という判断もなかなか難しいので、かなりの難問です…

回答No.1

noocyte

一般にはオクトツリー (八分木) を使うことになるのではないかと思います．

"オクトツリー" で検索
http://www.google.co.jp/search?q=%22%E3%82%AA%E3%82%AF%E3%83%88%E3%83%84%E3%83%AA%E3%83%BC%22&sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja

"立体の内部" "判定" "アルゴリズム" で検索
http://www.google.co.jp/search?q=%22%E7%AB%8B%E4%BD%93%E3%81%AE%E5%86%85%E9%83%A8%22+%22%E5%88%A4%E5%AE%9A%22+%22%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%22&hl=ja&rls=GGGL,GGGL:2006-34,GGGL:ja&start=10&sa=N

ソリッドモデリング等の話も参考になるかも．

形状モデリング特論 (東京大学 先端科学技術研究センター 精密機械工学専攻)
http://www.den.rcast.u-tokyo.ac.jp/~suzuki/class/modeling/index.html

お礼

ご回答、ありがとうございます。
検索するにもキーワードがわからず、困っておりました。
見てみます。