delete_point! fails for link with concave triangular-indent

[DanielVandH]

using DelaunayTriangulation, StableRNGs
j = 96
rng = StableRNG(j)
points = rand(rng, 2, 500)
tri = triangulate(points; rng)
k = 19
rng = StableRNG(k)
i = 183
delete_point!(tri, i, rng=rng)

The resulting triangulation is not valid:

julia> get_adjacent(tri, 92, 9)
33

julia> get_adjacent(tri, 9, 92)
0

I'm not sure what a simple fix is for this. The problem region is here:

The red dots show the link (the surrounding polygon). I believe the problem is that those three red dots in the first blue triangle, which form a concave indent shown in the isolated second image, are trying to connect to each other somehow. The edge (92, 9) is the outer-most edge of that blue triangle (i.e. the one opposite the indented vertex).

One fix might be that we just need to avoid reusing the same triangulation. I'm not a fan of this, but it might help avoid this issue. In particular,

function _delete_interior_point!(tri, S, rng)
    triangulate_convex!(tri, S; rng, update_ghost_edges=false) # Works even for boundary nodes, due to the replacement we make above
    return nothing
end

should become

function _delete_interior_point!(tri::Triangulation{P,Ts,I,E,Es,BN,BNM,B,BIR}, S, rng) where {P,Ts,I,E,Es,BN,BNM,B,BIR}
    temp_tri = triangulate_convex(get_points(tri), S;
        IntegerType=I,
        EdgeType=E,
        TriangleType=triangle_type(Ts),
        EdgesType=Es,
        TrianglesType=Ts,
        representative_point_list = get_representative_point_list(tri),
        rng,
        add_ghost_triangles=false,
        add_convex_hull=false,
        compute_centers=false,
        delete_empty_features=false)
    for T in each_triangle(temp_tri)
        add_triangle!(tri, T; protect_boundary=true)
    end
    return nothing
end

This also happens on my development branch for v1.0, which has slightly improved the logic in this function. There I've implemented this fix and it works. v1.0 also uses smarter caching, so that this temporary triangulation doesn't lead to as many allocations. I'll think about this a bit more before going with this fix.