2006年11月02日
カテゴリ： カテゴリ未分類
Real-Time Collision Detection という本を読んでいます。
http://www.realtimecollisiondetection.net/
12.2.3 Testing Connectedness
接続性のテスト。接続情報を用いて面の表の中にあるすべての面がある辺によって別の面に接続しているかどうかを決定する問題について考えてみます。
どの接続要素が三角形の一部の要素なのか知るために label フィールドを各三角形のデータ構造に要素の番号を保持するために追加されています。開始時にはどの要素の一部としてもラベル付けされてはおらず、すべての三角形を巡回しマーク付けされていない三角形に遭遇するたびに要素の番号を1つずつ増やしこの要素の番号でタグ付けしていきます。
こうしてすべての要素を接続し終わると再帰的に最初の要素番号のついている三角形をすべて巡回してマークしていきます。
ここまでの例が本文ではソースコード込みの例で示されています。再帰の処理が深すぎると問題になるでしょうから明示的にスタックをとるような処理が良さそうですね。
http://www.realtimecollisiondetection.net/
12.2.3 Testing Connectedness
接続性のテスト。接続情報を用いて面の表の中にあるすべての面がある辺によって別の面に接続しているかどうかを決定する問題について考えてみます。
どの接続要素が三角形の一部の要素なのか知るために label フィールドを各三角形のデータ構造に要素の番号を保持するために追加されています。開始時にはどの要素の一部としてもラベル付けされてはおらず、すべての三角形を巡回しマーク付けされていない三角形に遭遇するたびに要素の番号を1つずつ増やしこの要素の番号でタグ付けしていきます。
こうしてすべての要素を接続し終わると再帰的に最初の要素番号のついている三角形をすべて巡回してマークしていきます。
ここまでの例が本文ではソースコード込みの例で示されています。再帰の処理が深すぎると問題になるでしょうから明示的にスタックをとるような処理が良さそうですね。
お気に入りの記事を「いいね！」で応援しよう
【毎日開催】
15記事にいいね！で1ポイント
PR
キーワードサーチ
▼キーワード検索
大鳥居.
人生ゲーム
コメント新着
© Rakuten Group, Inc.
