Delaunayウォークポイントの外側の三角形

Question

私は、覚えている確率的散歩を使用して2d冗談三角測量を実装しています。私が理解できないことは、前の三角形のいずれにもない点が挿入された場合に起こることです。

triangle τ = α; 
triangle ψ = τ; // the previous triangle is initialized as τ 
boolean found = false; 
while not found do 
found = true; 
int k = random int(3); // k ∈ {0, 1, 2} 
for i = k to k + 2 do 
    point l = t(i mod 3); 
    point r = t[(i+1) mod 3]; 
    // “remembering” improvement condition 
    if ψ is not neighbor of τ trough ²lr then 
    if orientation2D(l, r, q) < 0 then 
    ψ = τ; 
    τ = neighbor of τ trough ²lr; 
    found = false; 
    break; // terminates the for cycle 
    end 
    end 
end 
end 
return τ; 

私の推測では、τトラフ²lrの隣人がいないと外側にあります。それが接続するポイントを見つける方法は別の問題です。私はlとrが2つのポイントであると仮定しますが、もっと多くのことができます。

Answer 1

私の推測は正しいと思われました。エッジを越えなければならないが、三角形を見つけることができない場合、それは外側にある。接続するポイントは、l、rと、そのポイントを結ぶことなくポイントに接続できる隣人とそのポイントの隣人です。