スラブ法

提供: ORWiki
ナビゲーションに移動 検索に移動

【すらぶほう (slab method)】

平面上の幾何的な対象物を効率的に処理するための技法である. 対象物の点を通る軸に垂直な直線で平面を分割したとき, それぞれの垂直な帯の部分をスラブという. スラブ内では対象物は線形順序をもち一列に並べることができて, それをデータ構造で表現しておけば, 2次元の問題を1次元の問題に帰着させて解くことができる. 計算幾何の代表的手法である平面走査法と組み合わせて線分の交差判定, 点位置決定などに用いられている.