tkenichi の日記

毒舌皮肉系恥さらし日記

組み合わせ三角形ポリゴンの判定アルゴリズム(1)

f:id:tkenichi:20150403115856j:plain

2次元の有限単体的複体を考える。頂点集合を自然数で番号付けして、三角形の集合と考えると、相異なる3つの自然数の組の集合と考えることができる。

 S = \{ (i_0,i_1,i_2) \in \mathbf{Z}^3 | i_0 \neq i_1, i_1 \neq i_2, i_2 \neq i_0 \}

四角形の頂点を 0,1,2,3 とすると、三角形分割して単体的複体とみなすと  \{ (0,1,2),(0,2,3) \} である。

次の条件を判定するできるだけ高速なアルゴリズムを考えたい。

  1. 単体的複体が多様体かどうか(すべての頂点の周りの位相が円板と同相であること、角錐の頂点同士がつながっているような構造がないこと)
  2. 向きづけ可能かどうか(向きづけられているかではない。メビウスの輪のような表裏がつけられないようなことがないこと)

最初の条件についての単純なアルゴリズムな例としては、各頂点においてそれを含む三角形の部分集合を考えて、その境界集合(1次元の単体的複体、すなわち線分の集合)を求め、その連結成分の個数が1であることを調べればよい。

2つ目の条件についての単純なアルゴリズムの例としては、隣り合っている三角形の境界の辺に三角形が異なる向きかどうかでマークをつけ、単体的複体上の一周する経路でマークのが付いた辺を横切るのが必ず偶数回かどうかを確かめればよい。

もっと高速に判定するアルゴリズム(とその実装)を探してみよう。