csvデータからの形の輪郭抽出

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
あさかぜ

csvデータからの形の輪郭抽出

#1

投稿記事 by あさかぜ » 10年前

初めましての投稿です。よろしくおねがいします。
用意してある膨大なcsvの3次元の点データから輪郭だけをC言語で実行して取りたいのですが、立体に行く前の練習として平面で平行四辺形などの点データなどを作成してそこから外だけをとろうと思っています。
プログラム例はこちらです。

コード:

#include <stdio.h>

FILE *fileOpen(char *,char *);
int main(void)
{
  FILE *in_fp;
  FILE *out_fp;
  int ret;
  double n[50][2];/*配列宣言*/
  double max[2] ={-999,-999};/**/
  double max1[40][2];/**/
  double min[2] ={999,999};
  double min1[40][2];
  double k[50][2];
	int i=0;
	int j=0;
	int d=0; /**/

        in_fp = fileOpen("heiko.csv","r");
        out_fp = fileOpen("heiko1-1.csv","w");

    while( ( ret = fscanf( in_fp, "%lf,%lf,",&n[d][0], &n[d][1] ) ) !=EOF  ){
	d++; /*次の行をとるためにd+1する*/
    }
	/*読み込んだd回分jを繰り返す。*/
	/*xyの最大値最小値をmax[i],min[i]に格納して、大きいとき、小さいときにmax1,min1に格納*/
 		for (j=0; j<d; j++){ 
			for (i=0; i<2; i++){ 
				if(max[i] < n[j][i]){ 
					max[i] = n[j][i];
					max1[j][0] = n[j][0];
					max1[j][1] = n[j][1];
				}
				if(min[i] > n[j][1]){
					min[i] = n[j][i];
					min1[j][0] = n[j][0];
					min1[j][1] = n[j][1];				
   	           }
            }
        }

     for (j=0; j<d; j++){ 
	                  /*yがminより小さいとき、またはyがmaxより大きいときにkに格納*/
              if(min[1] >= n[j][1] || max[1] <= n[j][1]){  
		        k[j][0] = n[j][0];
		        k[j][1] = n[j][1];
	        	fprintf(out_fp," %lf,",k[j][0]); /**/
	       	    fprintf(out_fp," %lf,",k[j][1]); /**/
               }
              if(max1[j][1] == n[j][1] && max1[j][0] == n[j][0]){  
		            if (min[1] >= n[j][1] || max[1] <= n[j][1]){
		             }
		              else {
			            k[j][0] = max1[j][0];
			            k[j][1] = max1[j][1];
	        		    fprintf(out_fp," %lf,",k[j][0]); /**/
	        		    fprintf(out_fp," %lf,",k[j][1]); /**/
		             }
	          }	
	  fprintf(out_fp,"\n"); /*次の行にデータを出力したいため改行。*/
	}
        fclose(in_fp);
        fclose(out_fp);
  return 0;
}


 FILE *fileOpen(char *p_fileName,char *p_mode)
 {
        FILE *fp;
        fp = fopen(p_fileName,p_mode);
        if(fp == NULL){
                fprintf(stderr,"ファイル[%s]を開くことができませんでした。\n",p_fileName);
                exit(1);
        }
        return fp;
 }
[thumbnail]http://gyazo.com/db3f8888650c580b411c3dadf131bc52.png[/thumbnail]画像のような入力データのcsvから外側だけをとりたいのですが実行すると次のようになってしまいます。
[thumbnail]http://gyazo.com/3dfffc9ef7d6d7a3fb323746e41d25b4.png[/thumbnail]
xyの最大値と最小値だけがわかるだけで、y=2、3、4などの時のxの最大値と最小値がわからないので、右側の点がとれてないのだと思います。
そのyが最小、最大以外でのとりかたがわからないので悩んでいます。アドバイスお願いします。
C言語については授業でちょっとやったぐらいでファイル入出力などは授業で習わずに終わったので、ネットで勉強しました。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: csvデータからの形の輪郭抽出

#2

投稿記事 by みけCAT » 10年前

おそらく、やりたいことは入力された点の凸包を求めることですね?(違ったらごめんなさい)

[search=google]凸包[/search]
[search=google]三次元凸包[/search]

自分が凸包を実装したコードはこちらです。(あまり綺麗ではないです)
0068 Enclose Pins with a Rubber Band - みけCATのAOJコード集
ただし、今回の場合(3個以上の点が一直線上にある場合)は条件の微調整が必要かもしれません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#3

投稿記事 by usao » 10年前

可能であれば,やりたいこと,というか,実際の問題の概要というか
問題の複雑さとか要求する正確さ(?)みたいなことに関する情報みたいなのを最初に出しておいた方が
良いような気がします.

・みけCATさんが触れられているように,図形形状に何らかの仮定を設けてよいのか?
 それとも入力データは完全に未知のデータとして考えなければならないのか?
・目的は点群が表現する「図形」を推定すること? or 輪郭上に存在する点群とそうではない点群とにより分けること?
・どの程度の正確さが必要なのか?みたいな事柄
 (例えば 輪郭の一部にV字型の箇所があり,Vの下側が図形内部側である場合,Vの一番下の角になってる点を輪郭だと判定するのは難しそう.
 こういう箇所を内側の点だと判定してしまうことをどの程度許容するのか… みたいな?)
・データ点群の用意の仕方について.
 点群の座標はなにかしら人工的に用意した「理想的な」座標なのか,それとも計測値にようにノイズが乗っているのか?
・輪郭上の点 と そうでない点 との存在比率みたいなのがある程度分かっているのかどうか
 (例えば3次元の点群データを用意した方法によっては
  輪郭(というか表面?)ではない点というのは「ノイズ的な存在でかなり少数であるはず」とかいう
  知見が得られている(そしてそれをどうにかして利用できる可能性がある)場合があるような気がします.)
オフトピック
…と,さんざんに羅列してみましたが,
要は,至極簡単なことをやりたいだけなのか,かなり難しいことをしようとしているのか
が質問文からはよくわからなくて, それ次第で回答も変わってくるのではないかな?と.
(「点群 表面」とかで検索してみるとわかりますが,
 そういった問題を研究課題にして論文書かれてたりとかしますし)

あさかぜ

Re: csvデータからの形の輪郭抽出

#4

投稿記事 by あさかぜ » 10年前

>みけCATさん、usaoさん
フォーラムルールを見て頑張ったつもりですが、うまく質問できてないです、すみません。
今用意している3次元データとはこのようなものです。csvのデータをそのままblenderで表示した画像です。
[thumbnail]http://gyazo.com/db88532bd3eadcac2c80a1492528f0ca.png[/thumbnail][thumbnail]http://gyazo.com/5f3bc7f8b143ebdcfa892af8e679bb08.png[/thumbnail][thumbnail]http://gyazo.com/a75cf9d9639dd270802a42a224ac7edf.png[/thumbnail]
凸包となると中の点が残ってしまう?ので外だけの点をとりたいです。
やりたいことはこの点の集まりから、立体の輪郭だけのデータを取って新しいcsvに輪郭だけの点データを出力したいのです。
usao さんが書きました:・目的は点群が表現する「図形」を推定すること? or 輪郭上に存在する点群とそうではない点群とにより分けること?・どの程度の正確さが必要なのか?みたいな事柄
3次元ソフトなどで点群を表示してどんな形をしているのかをみて、そしてその形から輪郭だけをとりたいのでこの立体の中の点群や表面の点群などとは分けたいです。
内側などに凹んでいるところはないです。できれば精確にとりたいですがちょっと点が外れているところでも許容範囲です。
usao さんが書きました:それとも入力データは完全に未知のデータとして考えなければならないのか?
今ある入力データは未知のデータではなく3項目で1万4000行ぐらいってわかっています。
平行四辺形のような整数ではなく、小数点や負など点の値はばらばらです。
usao さんが書きました:・データ点群の用意の仕方について.
人工的にではなく計測された点データをcsvで表示しています。
輪郭上の点とそうでない点については3次元ソフトで表示したぐらいで存在比率とかはわかってないです。
xは最初はプラスだがだんだんとマイナスにいっていて、yはプラスとマイナスがばらばらの値でzはプラスの値がなく、マイナスの方にいっているとかぐらいなら。
現在の平行四辺形ならx=3の時のyのデータを何個かってのはわかりますが、この3次元のデータは同じ数値はないので難しいと思います。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: csvデータからの形の輪郭抽出

#5

投稿記事 by みけCAT » 10年前

あさかぜ さんが書きました:凸包となると中の点が残ってしまう?ので外だけの点をとりたいです。
どのように考えてこのような結論を出しましたか?
凸包を使用すると、(輪郭の定義にもよりますが)むしろ必要な点を消す可能性があるはずです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#6

投稿記事 by usao » 10年前

画像を拝見してもいまいちイメージがつかめません…
(削る前の鰹節にとがったしっぽがついているような感じ?)
表面形状測定みたなことで得たデータとは違って,物体内部な箇所にも密に点が存在しているのでしょうか.

「輪郭」と「表面」という2つの単語は別の概念として用いられているように見受けますが
「表面」とは要するに表面(説明になってないな…物体と大気が接する面とでも言うか)だと思いますが
「輪郭」とは何を指しますか?(「エッジ」的な意味?)
オフトピック
欲しいのが「表面」な点群であれば,まぁ,てきとーすぎる方法はいくらか思いつかなくもないけど,
それでも点の疎密が激しいデータだと厳しい.(画像を見ると,わりと疎な箇所があるようにも見える)
まともな方法が欲しいのであれば,そういう分野の文献を当たるのが近道かも?
[追記]
>今ある入力データは未知のデータではなく
例えば,目的を達成するための何らかの方法を実装したプログラムができたとして,そのプログラムは
とりあえず今持ってる特定のデータに対してだけ 動けば(=通用すれば)それでOK,ということでしょうか.
(「未知のデータを相手にする」っていうのは,そのプログラムが,「今持っていない計測データが与えられても動く」という意味)

あさかぜ
記事: 4
登録日時: 10年前

Re: csvデータからの形の輪郭抽出

#7

投稿記事 by あさかぜ » 10年前

みけCAT さんが書きました:どのように考えてこのような結論を出しましたか?
凸包を使用すると、(輪郭の定義にもよりますが)むしろ必要な点を消す可能性があるはずです。
外側の点をとる考え方は一緒ですが、外側の点を結ぶのは違うんじゃないのかなと思いました。

あさかぜ
記事: 4
登録日時: 10年前

Re: csvデータからの形の輪郭抽出

#8

投稿記事 by あさかぜ » 10年前

説明下手な分やはりcsvなどを添付した方がはやいのでしょうか。
usao さんが書きました:表面形状測定みたなことで得たデータとは違って,物体内部な箇所にも密に点が存在しているのでしょうか.
物体の内部にも点がいっぱいあります。
usao さんが書きました:「輪郭」とは何を指しますか?(「エッジ」的な意味?)
エッジですね。
立方体をイメージした時に、面ではなく辺と頂点のことを私は輪郭と言っていました。
その辺と頂点がだいたいとれるのであれば適当でもいいんですけどね。
usao さんが書きました:例えば,目的を達成するための何らかの方法を実装したプログラムができたとして,そのプログラムは
とりあえず今持ってる特定のデータに対してだけ 動けば(=通用すれば)それでOK,ということでしょうか.
とりあえずは今持っているデータに対してだけ通用すればOKです。

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#9

投稿記事 by usao » 10年前

エッジですか.なんか難しい話になってきましたね.
なんかデータのエッジは曲線っぽいし.

とりあえず 超てきとーな 方法案(うーん,ひどい方法だ):

エッジに沿わない平面(なるべくエッジ線と直交する面,かな)でデータを切ったときの断面を考える
(実際は平面までの距離が±閾値 以内となる点群を平面に投影したようなのを考えるのかな?)と,
2次元画像上での点群みたく見えると思うので,画像処理的なアプローチができるのではないかな?とか.
3次元のデータ点群を薄くスライスして,各スライス毎に考える.
点の密度がそれなりになるように前記閾値を決めたとしたら,点描した絵みたいになるので.
その2次元像上でコーナー点に見える箇所が,3次元エッジを平面が切断した箇所に対応するのでそれを求めるような感じで.

これだと切断平面と平行に近いエッジ(に属する点は)検出できないかもしれないので,
1回前記処理を行った後で,1回目の平面とは直交する平面でもう一回行って結果を統合みたいなのをやる必要があるかなぁ
(計3回やることに?)


前処理で 内部点を除去したデータ を一旦作った方が楽かな.
最後に編集したユーザー usao on 2013年12月18日(水) 17:06 [ 編集 1 回目 ]

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#10

投稿記事 by usao » 10年前

3次元データ上で処理するなら,とりあえず内部点を除去して表面な点群だけにしたところで,

(1)各データ点の法線方向を求める : あるデータ点の法線は,その近傍に存在する点群の分布から求む
 ↓
(2)各データ点について,近傍のデータ点群の法線方向分布を見て,自身が法線方向の変化率が局所的に最も高い位置にいるかどうかを調べる.
 それには,
 (2.1)各点が,自分の近傍での方向のばらつきを求めて
 (2.2)近傍のばらつき量の極大値を保持している点を見つける.ばらつき量が検出閾値以上なら,エッジ上の点だと判定.

ただし,(2.2)の極大点の求め方次第では,あるエッジ上点の近傍には別の点が検出されなくなるから,
何かしらうまい後処理が必要かも?
オフトピック
書いといてなんだけど,なんかいまいち…
経験者求む といった感じ.

あさかぜ
記事: 4
登録日時: 10年前

Re: csvデータからの形の輪郭抽出

#11

投稿記事 by あさかぜ » 10年前

すみません、返信内容を考えてたら遅くなりました。
方法案ありがとうございます。
usao さんが書きました:エッジですか.なんか難しい話になってきましたね.
なんかデータのエッジは曲線っぽいし.
はい、曲線が入ってますね。
ブレンダ-での画像が見づらかったので、実体モデルで表示してみます。
[thumbnail]http://gyazo.com/b62a8134a65cb4ca60ad6772253b7d4e.png[/thumbnail][thumbnail]http://gyazo.com/ee8863d24d6c12bb98983a560443cbe8.png[/thumbnail][thumbnail]http://gyazo.com/6612c4778c412ef4143a4eb216aeef6f.png[/thumbnail]
雑ですが、赤色で塗っているところが私が言っているとこです。
2枚目が平行四辺形っぽかったので平行四辺形でとる練習をしていました。
すごくいい方法案だと思うのですが、私の知識不足で頭が追いついてないです。
1月5日までには簡単な物でも完成させたいのですが難しいですね。

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#12

投稿記事 by usao » 10年前

>前処理で 内部点を除去したデータ を一旦作った方が楽かな.

とりあえず現状これはできそうなのでしょうか?
これができたと仮定(すなわち表面上の点だけになっていると)して…

<役に立たないかもしれないけど,一応考えたこと>
ある点pの座標を,
その周辺の点群(当然,この集団にはpは含まれないのだけど,さらに,pに近すぎる点も含めない方が良いかな?)
の座標から推定(最も簡単には,単純に点群座標の平均を取るとか)したら
その推定結果座標と,本当のpの座標とのズレ量がどの程度になるか? ということを考えると,
pが辺や角の上にある場合の方が,それ以外の場合よりも ズレ量が大きくなるような気がする.
オフトピック
…とかいうことを
本来は実際に自分でやってみて例えばズレ量に合わせて色を変えた点群でも描画してみてから
書くべきだと思うんだけど,その労力とか時間とかのいろんな理由で実際には全くやってません.
考えたことを垂れ流しているだけです……絵に描いた餅です.許して…

あさかぜ
記事: 4
登録日時: 10年前

Re: csvデータからの形の輪郭抽出

#13

投稿記事 by あさかぜ » 10年前

usao さんが書きました:>前処理で 内部点を除去したデータ を一旦作った方が楽かな.
とりあえず現状これはできそうなのでしょうか?
これができたと仮定(すなわち表面上の点だけになっていると)して…
すみません3次元データ上では処理は行わず、C言語でのプログラム作成です。
usao さんが書きました:これだと切断平面と平行に近いエッジ(に属する点は)検出できないかもしれないので,
1回前記処理を行った後で,1回目の平面とは直交する平面でもう一回行って結果を統合みたいなのをやる必要があるかなぁ
(計3回やることに?)
X軸を基準に、Y軸を基準に、Z軸を基準にカットというかスライスをする手順での計3回ですね。
スライスについてはそのスライスする間隔をどうするのかが問題点か。
大きくスライスするのか、小さすぎるとデータが多いので時間がかかりそう。幅としては2.0~0.5ぐらいがいいのかなぁ。
スライスした後にスライスしたデータ内で内側の点なのか外側の点なのかってのを比較、(一番大きい、一番小さいとか?)して最終的に1つに結合すればできそうですね。
でもデータが1つだけだと比較ができないから1つの時はスルーするのかな。
なんとなく理解はできてきたものの正月も考えてましたがプログラムはうまく思いつかずです。。。
usao さんが書きました:考えたことを垂れ流しているだけです……絵に描いた餅です.許して…
スルーされることなく、返信をしてくれているのでありがたいですよー。
言ってたcsvデータを添付しておきます。
オフトピック
あきらめずに頑張ってはいるけどお手上げ状態ですね。。。
平行四辺形の方はなんとか作ることはできましたが。
添付ファイル
ten.csv
(282.4 KiB) ダウンロード数: 93 回
最後に編集したユーザー あさかぜ on 2014年1月05日(日) 23:41 [ 編集 1 回目 ]

たいちう
記事: 418
登録日時: 13年前

Re: csvデータからの形の輪郭抽出

#14

投稿記事 by たいちう » 10年前

> すみません3次元データ上では処理は行わず、C言語でのプログラム作成です。

usaoさんもC言語で前処理をする前提だと思いますよ。
そのプログラムをあさかぜさんは作れそうですか?という質問です。

作り方については、みけCATさんがキーワードを書いてくれています。
あさかぜさんが実際にやりたい事と比較したらメジャーなテーマなので、
参考になるHPも見つかるでしょう。

ここまでは「比較的簡単」な前処理の話です。
そこからエッジを抽出する実際の処理はずっと難しく、
書かれている条件から私が思いつくのもusaoさんの書いているような方法。
プロである私がやっても試行錯誤に相当の時間がかかると思いますし、
あさかぜさんの課題の全体像が判っていないので、
この方法では必要事項を満たせない可能性もあります。
(みけCATさんもusaoさんも仕様の確認をしていますが、
あさかぜさんの回答は十分とは言えません。)

C言語をちょっとやった位との事なので、前処理を理解して完成させるだけでも
1~2ヶ月かかるかもしれません。当然、必要な期間には個人差があるし、
どんなに時間をかけても理解できない人もいるでしょう。


結論としてアドバイスは2通り。

1. 初心者には難易度が高すぎるということで諦める。
担当教官などがいるならば、相談してみましょう。
本当にプログラムを作成する必要がありますか?
手作業で輪郭を描いては駄目ですか?

2. まずは前処理の3次元凸包を完成させる。
この前処理は不要かもしれないけど、中間目標として妥当なところでしょう。
完成させた時には、色々レベルアップしているはずなので、
次の手を検討できるようになるでしょう。
とはいうものの3次元凸包も簡単ではないので、まずは2次元凸包でしょう。
どちらにしても自分で理解しないといけませんよ。

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#15

投稿記事 by usao » 10年前

>> すみません3次元データ上では処理は行わず、C言語でのプログラム作成です。
>
>usaoさんもC言語で前処理をする前提だと思いますよ。
>そのプログラムをあさかぜさんは作れそうですか?という質問です。

まぁこの部分は,
「全工程を行うプログラムをCで書かないとだめ」という話でなければ
Cでやろうが,何かしら別の手段でやろうがどちらでもいいのですが,
要するに,扱いの難易度が
 内部点があるデータ >>> 表面点しかないデータ
なんじゃないかな?ということですね.
前もって「軽いデータ」を用意しておければ,いろんな方法を試すのにも楽でしょうし.


>(一番大きい、一番小さいとか?)
局所的に問題を2次元に落としこめたとしても,
判定方法はそんな簡単な話ではほぼうまくいかないと思います.
点の密度がそれなりに高いことが期待できるなら,
モルフォロジー→コーナー検出オペレータ とかで片付くかもしれませんが,
ある程度疎だと,それなりに悩ましい話になるかと.

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#16

投稿記事 by usao » 10年前

ところで
>凸包
の話って,表面点の選別のための処理…なんですよね? (違う?)

今回のケース(データ)では凹部があるようなので
何かしらの工夫が要りそうに思うのですが,そのあたりのことはどんな感じなのでしょうか?


>完成させた時には、色々レベルアップしているはずなので、
>次の手を検討できるようになるでしょう。

実用性(?)よりもこっちの目的がメインなのであれば
まぁそこらへんはどうでもいいのですが.

たいちう
記事: 418
登録日時: 13年前

Re: csvデータからの形の輪郭抽出

#17

投稿記事 by たいちう » 10年前

> ところで
> >凸包
> の話って,表面点の選別のための処理…なんですよね? (違う?)

きっと私への質問でしょうか。

> 実用性(?)よりもこっちの目的がメインなのであれば
> まぁそこらへんはどうでもいいのですが.

こっちの目的がメインで提案しています。
最終形を悩んでいるだけで手が止まってしまっているとしたら、
少しでも似た事をやってイメージをつかむ方が有意義ではないかと。

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#18

投稿記事 by usao » 10年前

>こっちの目的がメインで提案しています。
わかりました.

ただ,最初にやってみる事柄(凸包であれ,それ以外の何かであれ)を
現問題に対して使う予定がある という話の筋道みたいなのがあるならば
より望ましいだろうと思ったので,
>そのあたりのことはどんな感じなのでしょうか?
とか訊いてみた次第です.
オフトピック
>きっと私への質問でしょうか。
50%くらいはそうかも…?

みけCAT様も
データ分布形状が不明な時点で 凸包を挙げられていて,さらに
>凸包を使用すると、(輪郭の定義にもよりますが)むしろ必要な点を消す可能性があるはずです。
とおっしゃっているので,
形状の凹凸を問わずうまいこと使うアイデアをお持ちなのではないかな? と期待したり.

たいちう
記事: 418
登録日時: 13年前

Re: csvデータからの形の輪郭抽出

#19

投稿記事 by たいちう » 10年前

> みけCAT様も
> データ分布形状が不明な時点で 凸包を挙げられていて,さらに
> >凸包を使用すると、(輪郭の定義にもよりますが)むしろ必要な点を消す可能性があるはずです。
> とおっしゃっているので,
> 形状の凹凸を問わずうまいこと使うアイデアをお持ちなのではないかな? と期待したり.

亀レスですし、質問者さんも最近見かけませんが、、、

私としてはデータ分布形状が不明だからこそ凸包を提案しました。
この時点で凸包で駄目な場合、駄目と言ってもらえると期待しました。
近い提案をされることで、自分の問題との違いをあげることができるかも、です。

残念ながら、質問者さんがプログラミングに不慣れなせいもあり、
「輪郭」あるいは「エッジ」について、正確な仕様を聞きだすことができていません。
かなり難しい仕様なのかも。


次に形状の凹凸を問わずに表面点を取得する方法を調べてみました。
キーワードは「非凸 3次元 3角形分割」など。
難易度的には、以下のように感じています。

2次元凸包 → 3次元凸包 → 3次元非凸三角形分割 → 3次元穴あき非凸三角形分割

私に実装の経験があるのは2次元までですが、3次元凸包までは今でも多分できるかと。
今回の質問で考えてみましたが、3次元凸包を作ってから凹ませる方向で、
非凸にも対応できるかもしれないと思いました。

3次元凸包を作ってから、長い辺の近傍を調べ、少しずつ凹ませていく感じ。
単なる思いつきだし、途中で詰まる可能性も高いです。
よりよい方法がきっとあるでしょう。

参考資料
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用
私は持っていませんが、目次には3次元凸包までは書かれています。

穂影のアイズオンリー
この方は「穴あき非凸多角形の三角形分割」に取り組んでいます。
「コンピュータ・ジオメトリ」を高く評価していました。

アバター
usao
記事: 1887
登録日時: 11年前

Re: csvデータからの形の輪郭抽出

#20

投稿記事 by usao » 10年前

とりあえず今回のデータでは内部に空洞とかは無いみたいなので,

たとえば,
データ点群からランダムに2点選択し,この2点を通る無限直線からの距離が
閾値以内となる点群(=直線を軸とする円筒形領域内に存在する点群)について,
最も「端(と言えばいいのかな)」に存在する点(2点)を表面に存在する点と認定する.
(閾値=円筒半径 は隣接データ点間の距離の1~数倍程度かな)

…といったような簡単な処理を
気の済むまで繰り返せば表面だけの集合を得られるような気がしますね.
(方法論の回答としては褒められたものではないけれど,表面点群の取得は
 単なる前処理なのだから,極端な話,一晩くらい走らせておいてもいいわけで)

閉鎖

“C言語何でも質問掲示板” へ戻る