Code in the documentation is not working

using CairoMakie
using StableRNGs

points = [(0.0, 0.0), (2.0, 0.0), (1.0, 2.0)]
tri = triangulate(points)
fig, ax, sc = triplot(tri)
fig

add_point!(tri, 1.0, 0.5)
fig, ax, sc = triplot(tri)
fig

add_point!(tri, 0.0, 1.0)
fig, ax, sc = triplot(tri)
fig

delete_ghost_triangles!(tri)
add_point!(tri, 2.0, 1.5)

DelaunayTriangulation.has_ghost_triangles(tri)

add_ghost_triangles!(tri)

DelaunayTriangulation.has_ghost_triangles(tri)

get_convex_hull_vertices(tri)

convex_hull!(tri)
fig, ax, sc = triplot(tri, show_convex_hull=true)
fig

rng = StableRNG(123)
for _ in 1:1000
    new_point = 2rand(rng, 2)
    add_point!(tri, new_point)
end
fig, ax, sc = triplot(tri)
fig

vertices_to_delete = Iterators.filter(each_solid_vertex(tri)) do i
    p = get_point(tri, i)
    r2 = (getx(p) - 1.0)^2 + (gety(p) - 1.0)^2
    return r2 < 1 / 2^2
end
for i in vertices_to_delete
    delete_point!(tri, i)
end
fig, ax, sc = triplot(tri)
fig

Hi, this is in the documentation of triangulation, I want to do a delete point operation similar to the above, but im facing issues. Getting error vertex. not found. I tried to run the exact code in the docs, it also fails.

What is your error? The code you posted works fine for me. The only error is on Line 19, but if you read the docs that error is intentionally made to make a point about ghost triangles. An MWE would be best.

Taking part of it:

using CairoMakie
using StableRNGs

points = [(0.0, 0.0), (2.0, 0.0), (1.0, 2.0)]
tri = triangulate(points)
fig = Figure()
ax = Axis(fig[1, 1])

add_point!(tri, 1.0, 0.5)
delete_point!(tri, (0.0, 1.0))
add_point!(tri, 2.0, 1.5)


triplot!(ax, tri)
display(fig)```

ERROR: Graph does not contain requested vertex
Stacktrace: @line 11 delete operation

You cannot put coordinates into delete_point!. Only vertices - meaning integers, as mentioned in the docs:

Let us now demonstrate how to delete points. To do this, we use delete_point!. This function takes vertices rather than coordinates, identifying the corresponding point in points by its index

how can i get vertices closest to the points?

In my function:

    for (i, j) in enumerate(each_polygon_index(svorn))
        p = DelaunayTriangulation.get_centroid(svorn, i)
        density = get_density_value(normalized_density_values, p)
        if density != 0
            push!(points_to_add, p)
        else
            delete_point!(tri, j)
        end
    end 

Im looping through the voronoi cells and checking certain value and adding or deleting points. Is this the correct way to do?

There are very fast ways to do this, but here are some naive ways. Can probably do some nearest neighbour type methods for this too if you construct a KDTree to work with (GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor data structures (KDTree and BallTree) and algorithms for Julia.).

# If you know that your given coordinates (x, y) appear *EXACTLY* in points 
function get_vertex(tri, p) # p is the point (x, y) to find the vertex of 
    for i in DelaunayTriangulation.each_point_index(tri)
        get_point(tri, i) == p && return i
    end
    return 0 # 0 ⟹ point not found, you can error if you prefer
end

# If you only have an approximate form of the coordinates 
function get_closest_vertex(tri, p)
    x, y = getxy(p)
    i = argmin(DelaunayTriangulation.each_point_index(tri)) do v 
        x′, y′ = get_point(tri, v)
        (x - x′)^2 + (y - y′)^2 
    end
    return i
end

No. The triangulation is changing as you are doing the loop, so the density values will constantly be changing. Moreover, svorn will not be in sync with tri - you need to keep updating vorn after each update of tri. You should find the points to add / delete in a loop, then update the triangulation afterwards and then recompute your Voronoi tessellation.

1 Like