デローニー三角形分割

delaunaytriangulation.png

概要

入力  点の集合P
出力  三角形の集合$\tau$

最終的に出来る三角形や辺の数

  • n….点の数
  • k…点群の凸包上にある点の数とする
三角形 2n-2-k
3n-3-k

Step1.すべての点を包括する巨大な三角形で初期化

点群Pが三角形$p_{-1}p_{-2}p_{-3}$に含まれるように$p_{-1}p_{-2}p_{-3}$を選ぶ。
つまり、すべての点を包括するような巨大な三角形を作る。->作り方bounding-triangle

  1. ただ一つの三角形$p_{-1}p_{-2}p_{-3}$からなる三角形分割として$\tau$を初期化する。
  2. 点群Pのランダム順列$p_{1}p_{2}p_{3}.....p_{n}$を求める。

点の個数分繰り返す作業

  1. for(int r=0;r<n;r++)1
    1. do(pr$\tau$に挿入する) 挿入するとは?2
    2. prを含む三角形$p_{i}p_{j}p_{k} \in \tau$を求める
    3. if(prが三角形$p_{i}p_{j}p_{k}$の内部にある)3
      1. then pr$p_{i}p_{j}p_{k}$の3頂点の辺を結ぶことによって$p_{i}p_{j}p_{k}$を3つの三角形に分割する
        1. LegalizeEdge($p_{r} \overline{p_{i}p_{j}} \tau$);
        2. LegalizeEdge($p_{r} \overline{p_{j}p_{k}} \tau$);
        3. LegalizeEdge($p_{r} \overline{p_{k}p_{i}} \tau$);
    4. else(pr$p_{i}p_{j}p_{k}$の辺、たとえば$\overline{p_{i}p_{j}}$上にある)4
      1. prrからpkへの辺を加え、さらに$\overline{p_{i}p_{j}}$に接するもう一つの三角形の第3の頂点plとprを辺で結ぶことによって、$\overline{p_{i}p_{j}}$に接するこれら2つの三角形を4つの三角形に分割する
      2. LeganizeEdge($p_{r} \overline{p_{i}p_{l}} \tau$);
      3. LeganizeEdge($p_{r} \overline{p_{l}p_{j}} \tau$);
      4. LeganizeEdge($p_{r} \overline{p_{j}p_{k}} \tau$);
      5. LeganizeEdge($p_{r} \overline{p_{k}p_{i}} \tau$);
この時点でこんなかんじになります
delaunay-pre.png

仕上げ…巨大三角形に接続する点を取り除く

3点$p_{-1}p_{-2}p_{-3}$と、これらに接続する辺をすべて$\tau$から取り除く。

  1. return $\tau$

delaunay triangle

サポートサイト Wikidot.com delaunaytriangle