多面体の面セルは、面を周回する辺ループ（複数）ごとにアクセス用の辺セルのポインタを持つデータ構造です。したがって、辺の左右に繋がる面とウイング辺の情報とから、CFGを構成する面を数え上げることができます。元の多面体から、この構成する面セルのリンクを外し、CFGセルに繋ぎ変えるのがCFG構造への変換です。元の多面体に未だ面セルが残っていれば、これは別のCFGリンクにまとめます。多面体の干渉処理が済んだ状態で、面の接続関係が矛盾なく構成される単位はCFG構造単位で調べます。幾つかのCFGは、それぞれ独立したデータ構造になっていますので、或るCFGの面セルまたは辺セルをたどって別のCFGの面セルにアクセスすることはできません。また、個別のCFGが独立しているのか、入れ子状になっているのかも、この時点では分かりません。したがって、前節の辺ループ構造の調整と殆ど同じアルゴリズムで、CFGの入れ子関係を調べます。説明に使う図は、図12.6〜図12.8をそのまま利用できます。ただし、作業用テーブルのセル構造は少し違いがあることと、入れ子関係を調べる処理に別名のルーチンを使う、などの相違があります。これ以上の説明は、プログラミングのコーディング技法に関係し、やや専門的になりますので、省きます。多面体の干渉処理の最後は、CFG構造を標準のデータ構造に直し、不要になった頂点・辺・面セルを削除します。
2008.12 橋梁＆都市PROJECT |