30.1.2 三角測量における点の特定
N 次元空間内の特定の点が、この N 次元空間内の点の集合の Delaunay 分割内にあるかどうか、また、ある場合はどの N 単体にその点が含まれるか、分割内のどの点が目的の点に最も近いかを識別する必要があることがよくあります。関数と はtsearch三角dsearch測量でこの機能を実行し、 と は N 次元分割でこの機能を実行しtsearchnますdsearchn。
ベクトルpで表される特定の点 が N 単体の単体の 1 つに含まれるかどうかを識別するには、その点の直交座標を N 単体に関するパラメトリック形式で記述します。このパラメトリック形式は、点の重心座標と呼ばれます。N 単体を定義する点がN + 1 個のベクトルで与えられる場合、点pを定義する重心座標は次のように与えられます。 t(i,:)
p =ベータ* t
ここで、ベータにはN + 1個の値が含まれており、これらをベクトルとして点pの重心座標として表します。ベータの値の一意な解を保証するために、次の追加の基準があります。
合計 (ベータ) == 1
が課せられており、したがって上記は次のように記述できる。
p - t (end, 
= beta (1:end-1) * ( t (1:end-1,
- 1 ( N , 1) * t (終わり、:)
ベータを解くと、次のように書ける。
ベータ(1:end-1) = ( p - t (end, ) /
( t (1:end-1, :) - 1 ( N、1) * t (end, :)) beta (end) = sum ( beta (1:end-1))
これは点pの直交座標を重心座標betaに変換する式である。重心座標の重要な性質は、N単体のすべての点について、
0 <=ベータ( i ) <= 1
tsearchしたがって、およびでのテストでは、tsearchn基本的に、各点を N 単体の各単体の重心座標で表現し、 betaの値をテストするだけで済みます。 これは、 で使用される実装とまったく同じです tsearchn。 tsearchは 2 次元に最適化されており、重心座標は明示的に形成されません。
: idx = t検索 (x, y, t, xi, yi)
囲んでいる Delaunay 凸包を検索します。
の場合、 点 を含むtのインデックスを検索します。凸包の外側の点の場合、idxは NaN になります。 t = delaunay (x, y)(xi, yi)
プログラミング ノート: アルゴリズムはO( M * N ) で、 N 個の三角形内のM個の点を見つけます 。通常、見つける点が 1 つの連続したパス内にある場合、パフォーマンスははるかに高速になります。最初に、点が前の点が見つかった領域に対してチェックされ、連続したパスに沿った点の検索が高速化されます。
参照: delaunay、delaunayn。
: idx = tsearchn (x, t, xi)
: tsearchn [idx, p] = (x, t, xi)
指定された点を囲む単体を見つけます。
tsearchnは通常、 とともに使用されますdelaunayn。 単体のセットを返し、次にxiの各点を含むtの行インデックスを返します。凸包の外側の点の場合、idxは NaN になります。 t = delaunayn (x)ttsearchn
要求された場合、囲む単体の tsearchn重心座標 pも返します。
参照: delaunay、delaunayn、tsearch。
の使用例は、tsearch単純な三角測量で見ることができます。
x = [-1; -1; 1; 1];
y = [-1; 1; -1; 1];
トリ= [1, 2, 3; 2、3、4];
triで定義される2つの三角形から成ります。点がどの三角形に入るかは次のようにして識別できます。
tsearch ( x、y、tri、 -0.5、 -0.5)
⇒ 1
tsearch ( x , y , tri , 0.5, 0.5)
⇒ 2
そして、点が三角形の1つに含まれていないことを確認できます。
tsearch ( x , y , tri , 2, 2)
⇒ 非数
はdsearch、dsearchnテッセレーション内で目的の点に最も近い点を検索します。目的の点は、必ずしもテッセレーション内にある必要はなく、また、テッセレーション内にある場合でも、返される点は、目的の点が見つかる N 単体の頂点の 1 つである必要はありません。
: idx = dsearch (x, y, tri, xi, yi)
: idx = dsearch (x, y, tri, xi, yi, s)
要素内の最も近い点のインデックスidxを返します。 x, y[xi(:), yi(:)]
変数s は互換性のために受け入れられますが、無視されます。
参照: dsearchn、tsearch。
: idx = dsearchn (x, tri, xi)
: idx = dsearchn (x, tri, xi, outval)
: idx = dsearchn (x, xi)
: dsearchn [idx, d] = (…)
要素 xiに最も近いx内の点のインデックスidxを返します。
outvalが指定された場合、単体triの 1 つに含まれないxiの値はoutvalに設定されます。通常、triは から返されます。 delaunayn (x)
オプションの出力dには、クエリ ポイントxiと最も近い単体ポイントx間の距離の列ベクトルが含まれます。
参照: dsearch、tsearch。
上記のx、y、tridsearchの値を使用した の使用例は次のとおりです。
dsearch ( x , y , tri , -2, -2)
⇒ 1
テッセレーションの外側にあるポイントにフラグを付けたい場合は、次dsearchnのように使用できます。
dsearchn ([ x , y ], tri , [-2, -2], NaN)
⇒ 非数
dsearchn ([ x , y ], tri , [-0.5, -0.5], NaN)
⇒ 1
ここで、テッセレーションの外側の点には というフラグが付けられますNaN。