図12.6 面を周回する辺ループの入れ子関係
 一つの面についての辺ループが複数あるとき、ループの辺同士が交差することはありません。しかし、辺ループが離れて独立しているか、入れ子式になっているかを区別する必要があります。図12.6は、二つの辺ループについての入れ子関係を模式的に示したものです。まず、辺ループを囲う外枠について、予備的な判定ができます。枠同士が離れているとき、また、部分的に交差しているときも、ループは独立しています。枠同士が入れ子になっているとき、必ずしもループも入れ子関係にあるとは限りません。その判定のときに、作業用セルに保存した頂点セルの座標値を使います。二つの枠の中、内側の枠に属する辺ループの頂点と、外側に枠の寸法のさらに外側に任意の一点を決め、それを結ぶ線分を仮に決めます。この線分と、外側辺ループの辺との交点の数を数えます。偶数であれば、二つの辺ループは独立です。奇数の場合は、入れ子になっていると判定します。図12.6は平面図形として描いてありますが、実際には三次元の平面上に載っている辺ループですので、なるべく実形が大きく得られる座標平面上の二次元座標で交点を求めます。なお、同じようなアルゴリズムは、第8.3節で「領域の内外の関係を調べる」説明のところで使っています（この処理名をMA74としてあります）。
2008.12 橋梁＆都市PROJECT |