Bounding Triangle

bounding-triangle.png

ある図形を包括する三角形。bounding boxにちなんでbounding triangleと呼びます。

点群を包括する三角形の作り方

この巨大三角形の座標は、何通りあります

  1. 点群の範囲を[-My:My],[-Mx,Mx]とすると(3Mx,0),(0,3My),(-3Mx,-3My)にする方法
  2. 点群の右上端に1点、点群の下の水平線の右無限大遠くに1点、点群の上の水平線の左無限大遠くに1点とる方法
  3. 点群の凸包を計算して、凸包の辺を三角形の辺として使う方法[2]

2で出来る三角形は無限大の値を持つ頂点を使うので、仮想的な三角形になります。2の欠点は三角形と点の内外判定で値がオーバーフローになってしまうことです。
3の方法はめんどくさそうだな。。

1.点群の範囲を[-My:My],[-Mx,Mx]とすると(3Mx,0),(0,3My),(-3Mx,-3My)にして作る方法

    /*
    * すべての点を包括するような初期大三角形を作る
    * @ref http://www.cs.uu.nl/geobook/interpolation.pdf p199
    */
    tri makeBoundingTriangle(const vector<glm::vec3>& _points) {
        //p199
        //We will add two extra points p-1,p-2 that,
        //together with the highest point p0 of P,
 
        //点の範囲を求める
        glm::vec3 minval = glm::vec3(numeric_limits<float>::max(), numeric_limits<float>::max(), 0);
        glm::vec3 maxval = glm::vec3(-numeric_limits<float>::max(), -numeric_limits<float>::max(), 0);
        for (int i = 0; i < _points.size(); i++) {
            minval = glm::min(minval, _points[i]);
            maxval = glm::max(maxval, _points[i]);
        }
        glm::vec3 half_range = (maxval - minval) / 2.0f;
        //大きいほうの辺に合わせて正方形にする
        float h = half_range.x;
        float v = half_range.y;
        half_range = glm::vec3(max(h,v), max(h, v),0.0);
        //点群の中心の位置を求める そこを原点とする
        glm::vec3 origin = (maxval + minval) / 2.0f;
        //点群の範囲を[-My:My], [-Mx, Mx]とすると (3Mx, 0), (0, 3My), (-3Mx, -3My)にする方法
        glm::vec3 a = glm::vec3( 3.0*half_range.x,                 0, 0) + origin;
        glm::vec3 b = glm::vec3(                0,  3.0*half_range.y, 0) + origin;
        glm::vec3 c = glm::vec3(-3.0*half_range.x, -3.0*half_range.y, 0) + origin;
        return tri(a, b, c);
    }

このbouding triangleの欠点…点群が凸包にならない時がある

このように
bug1.png
なぜかというと、bounding triangleを取り除く前を見てみましょう。こうなってます
bug0.png
外接円をチェック
circle.png
たしかに、どちらの三角形も外接円に他の点が含まれていないので正当な辺といえます。
このデータの点群位置データtwin_null_data.txt
こういう欠点があるのでbounding triangleは、ドロネー三角形分割したい三角形を破壊しないように、もっと十分に大きく、とんがってないといけません。
点群によって出来る外接円の中に決してbounding triangleの頂点がはいらないように、bounding triangleの頂点はとおくーーにする必要があるのです。
もしうまくいかなかったら、3倍から5倍と、、bounding triangleを大きくしていくと解決します。

bounding-volume

サポートサイト Wikidot.com bounding-volume