I'm implementing a 2d delaunay triangulation using the remembering stochastic walk. What I don't understand is what happens if a point is inserted that is not in any of the previous triangles.
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 τ;
My guess on this is, that if there is no neighbor of τ trough ²lr it is on the outside. How to find the points it connects to is another problem. I assume l and r are two of the points, but it could be more.
My guess turned out to be correct. If you have to cross the edge but can't find the triangle, it is on the outside. The points it connects to are l,r and any neighbor that can connect to the point without crossing a line and the neighbor of that point ...