Delaunay Walk点在三角形外

Question

我正在使用记忆随机游走实现 2d delaunay 三角剖分。我不明白的是，如果插入一个不在前面任何三角形中的点会发生什么。

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 是其中的两个点，但可能更多。

Answer 1

事实证明我的猜测是正确的。如果你必须穿过边缘但找不到三角形，它在外面。它连接的点是 l，r 和任何可以连接到该点而不穿过线的邻居以及该点的邻居......

Delaunay Walk点在三角形外

Delaunay Walk point outside triangles

algorithm

geometry

triangulation

delaunay