目次ページ 前ページ 次ページ
12. 積み木モデルでの面の干渉
12.3 面を周回する辺構造の調整
12.3.6 ツリー構造に組み上げる手順の説明
辺ループの種類は、面の外周を周回する辺ループと穴を周回するループがあります。ここではその区別なしに内と外の入れ子関係を調べてツリー構造に構成する手順（アルゴリズム）を説明します。辺ループ作業用セルは、チェーン状にリンクしてITABLに構成してあります。最初、一つの辺ループセルをツリー構造の仮の親(図12.8のJFLC単独)と決めてから処理を始めます。
(1) 判定に使う未処理の辺ループセル(IFLC)を一つ取り出します。IFLCの初期状態は、親も子も持っていません。既にツリー構造判定済みのセルグループから順に、検査用セル(JFLC)を取り出します。このセルは、既に別のセルと親や子の関係を持っている場合があります。親を持つ場合の検査は、親セルの検査のときに重複しますので、飛ばしてツリー構造内の次のセルに移ります。図12.8は、JFLCが親であって、複数の子セルが繋がっているツリー関係を表しています。このツリーを順にたどって、IFLCがどの位置(A0,A1,A2,A3)に入るかを調べます。
(2) 二つの辺ループ(IFLC,JFLC)間の入れ子関係を判定します（これは、二つ上の段落に紹介したMA74を呼んで行わせます）。入れ子関係は、図12.6に示したコードIXで通知されます。IFLCとJFLCが独立であれば、別のJFLCを取り出して(1)から検査を再開します。
(3) IFLCの中にJFLCが入っているとき、IFLCは、図12.8のA0の位置になりますので、親(IFLC)と子(JFLC)の関係を構築します（この処理名はLMPARです）。そして、次の新しいセルを取り出す(1)に戻って検査処理を再開します。
(4) 逆に、JFLCの中にIFLCが入っている場合は、暫定的に、IFLCが図12.8のA1の位置に居るとします。JFLCが子のセルを持たなければ、親(JFLC)と子(IFLC)の関係を構築し、次の新しいセル(IFLC)を取り出して(1)から検査処理を再開します。
(5) JFLCが子セルを持つ場合は、少し検査に手間がかかります。JFLCが複数の子セル(JSON)を持っていても、ポインタが指す子セル(JSON)は長男のセル(JSON0)です。次男以降が居る場合には長男セルの兄弟リンクを調べなければなりませんので、差し当たり次男セル(JSON1)のポインタを控えておきます。IFLCの挿入予定位置は、A1からA2の位置に移します。ここで；
(6) 子のセル(JSON)とIFLCの入れ子関係を調べます。もしJSONとIFLCが独立であれば、JSONをそれまでのJSON1と差し替えて、(5)に戻ります。すべての子セルとの関係が独立であれば、IFLCはJFLCの末っ子として親(JFLC)と子(IFLC)の関係を構築します。そして、次の新しいセル(IFLC)を取り出して(1)から検査処理を再開します。
(7) IFLCの中にJSONが入っているときは、JSONを親セルJFLCから切り離し(処理名LDPAR)、改めて親(IFLC)と子(JSON)の関係をLMPARで構築します。LDPARの処理をすると、JFLCの子セルの数が変わりますので、(5)に戻って、JSON0,JSON1のポインタを調べ直して処理を繰り返します。このとき、JFLCの末っ子にIFLCが入ったことに留意します。