ハーフエッジデータ構造

ナビゲーションを行う場合、マップを表現するグラフ（NavMeshなど）のトポロジー的な構造を頻繁に参照することになる。頂点に接している辺を得る、辺に接している面を得る、など。

頂点配列とそのインデックスの配列といった単純な形でグラフを格納するとこうした処理が面倒になるので、あらかじめトポロジー構造を含んだ表現にしておくと便利。 そうしたデータ構造としてハーフエッジ（half-edge）を用いたものがある。

ハーフエッジは名前の通り辺を半分にしたものと言える。

これにより頂点や面との関係が整理できる。

データ構造

下のコードのようにそれぞれのハーフエッジへpair、next、prevといった参照を持たせる。（一応C#の気分だが、実際にはメンバはpublic Vector3 position { get; private set; }のようにアクセスコントロールすべきだし、コンストラクタや操作の為のメソッドも必要だ）

class Vertex
{
    Vector3 position;
    /// この頂点を始点とするhalfedge
    Halfedge halfedge;
}

class Halfedge
{
    /// 始点
    Vertex vertex;
    /// 逆のhalfedge
    Halfedge pair;
    /// faceの辺として次に来るhalfedge
    Halfedge next;
    /// faceの辺として前にあるhalfedge
    Halfedge prev;
    /// 右側（左側）に見る面（nullになりうる）
    Face face;
}

class Face
{
    /// この面を時計回りに囲むhalfedgeの1つ
    Halfedge halfedge;
}

以下の様な条件が常に成り立つ筈なので、データを構築する際のバリデーションに使うことができる。

// Vertex v;
// HalfEdge h;
// Face f;

v.halfedge.vertex == v
h.pair.pair == h
h.next.prev == h
h.next.prev == h
f.edge.face == f

ハーフエッジデータ構造には次の自由度がある：

• ハーフエッジはfaceを時計回りに回るか反時計回り回るか
• ハーフエッジのvertexは始点か終点か

ここでは時計回り・始点にしている。これによってアルゴリズムが変わってくるので注意。

処理の例

頂点に接する辺を列挙する

Halfedge hに対してh.pair.nextで、h.vertexから見てhの左側（反時計回り）にあるhalfedgeが得られる。 最初のhに一致するまでループすると一通りの辺が得られる。

// Vertex v;

Halfedge h = v.halfedge;
do
{
    // hの処理
    h = h.pair.next;
} while (h != v.halfedge);

辺を追加する（2頂点を繋ぐ）

nextとpairの整合性が保たれるようにする。

（細い矢印は全てnextを指している。）

図で見ると簡単な気もするが、どのnext/prevの間に新しいハーフエッジを挟むのかを幾何学的に判断する必要がありやや手間が掛かる。（面だけ扱う場合は問題ないはず）