ハーフエッジ データ構造
- ポリゴンメッシュなどを扱うときに使われるデータ構造にハーフエッジデータ構造というものがある(こちら)
- グラフ構造だが、その特性に合わせて、エッジ中心に構成する
- すべてのエッジは二つの面に帰属することに注意する
- 構造
- エッジがn/2本あるとき、これを方向に注意してE={e1,e2,...,en}のように２倍のアイテムとして扱う。これをハーフエッジと呼ぶ
- 個々のハーフエッジには方向の違う自身があるので、それを自分の逆エッジとして登録する
- 個々のハーフエッジの始点ノードを登録する。終点ノードを登録する
- 個々のハーフエッジを含む１つの面を登録する(あるエッジに対して、二つのハーフエッジを作ると、エッジを含む二つの面はそれぞれ異なるハーフエッジと紐づく)
- 個々のハーフエッジの始点ノードについて、当該ハーフエッジの時計周りで隣にあたるハーフエッジ(始点ノードを共有している)を「(時計回り)隣接ハーフエッジ」として登録する
- (反時計回りの隣接ハーフエッジも登録することもある。冗長情報である)
