Triangulation Operations
Adding or Clearing Ghost Triangles
An important component to be aware of when considering dynamic updates to triangulations are the ghost triangles. As we discussed in the vertex insertion/deletion example, ghost triangles are needed when we are making updates outside of the boundary of the current triangulation.
using DelaunayTriangulation
using CairoMakie
Let us take an example triangulation.
points = [(-1.0, -1.0), (1.0, -1.0), (0.0, 1.0)]
tri = triangulate(points)
Delaunay Triangulation.
Number of vertices: 3
Number of triangles: 1
Number of edges: 3
Has boundary nodes: false
Has ghost triangles: true
Curve-bounded: false
Weighted: false
Constrained: false
fig, ax, sc = triplot(tri, show_ghost_edges = true)
fig
The ghost triangles are represented by the convex regions bounded by the blue lines. By default, triangulate
will keep these ghost triangles. If you want to remove them, you'd have to use delete_ghost_triangles!
or use delete_ghosts = true
inside triangulate
.
If you do need to query whether your triangulation already has ghost triangles, use
DelaunayTriangulation.has_ghost_triangles(tri)
true
To clear the ghost triangles, use
delete_ghost_triangles!(tri)
DelaunayTriangulation.has_ghost_triangles(tri)
false
An important note for us to make is that ghost triangles are not just there as a concept, but they are actually physically stored. Adding them back with add_ghost_triangles!
, we have:
add_ghost_triangles!(tri)
get_triangles(tri)
Set{Tuple{Int64, Int64, Int64}} with 4 elements:
(3, 2, -1)
(2, 3, 1)
(1, 3, -1)
(2, 1, -1)
See that there is not just the triangle (1, 2, 3)
, but also (3, 2, -1)
, (1, 3, -1)
, and (2, 1, -1)
(where the ghost triangles are also oriented counter-clockwise). For example,
get_adjacent(tri, 3, 2)
-1
get_adjacent(tri, 3, -1)
1
get_adjacent(tri, -1, 2)
1
get_neighbours(tri, -1)
Set{Int64} with 3 elements:
2
3
1
get_adjacent2vertex(tri, -1)
Set{Tuple{Int64, Int64}} with 3 elements:
(3, 2)
(1, 3)
(2, 1)
If we delete them, they are no longer there.
delete_ghost_triangles!(tri)
get_triangles(tri)
Set{Tuple{Int64, Int64, Int64}} with 1 element:
(2, 3, 1)
As a last note, we remark that the ghost vertices that define the vertex of these ghost triangles is still there regardless of whether the triangulation has ghost triangles. Thus, for example, the following still work
get_neighbours(tri, -1)
Set{Int64} with 3 elements:
2
3
1
get_adjacent2vertex(tri, -1)
Set{Tuple{Int64, Int64}} with 3 elements:
(3, 2)
(1, 3)
(2, 1)
get_adjacent(tri, 3, 2)
-1
You can remove them from the graph, using
DelaunayTriangulation.delete_ghost_vertices_from_graph!(tri)
Graph
Number of edges: 6
Number of vertices: 3
so that e.g. get_neighbours(tri, -1)
is then an error. This will still not remove them from the adjacent
and adjacent2vertex
maps, but it does mean for example that
collect(each_solid_vertex(tri)) == collect(each_vertex(tri))
true
Just the code
An uncommented version of this example is given below. You can view the source code for this file here.
using DelaunayTriangulation
using CairoMakie
points = [(-1.0, -1.0), (1.0, -1.0), (0.0, 1.0)]
tri = triangulate(points)
fig, ax, sc = triplot(tri, show_ghost_edges = true)
fig
DelaunayTriangulation.has_ghost_triangles(tri)
delete_ghost_triangles!(tri)
DelaunayTriangulation.has_ghost_triangles(tri)
add_ghost_triangles!(tri)
get_triangles(tri)
get_adjacent(tri, 3, 2)
get_adjacent(tri, 3, -1)
get_adjacent(tri, -1, 2)
get_neighbours(tri, -1)
get_adjacent2vertex(tri, -1)
delete_ghost_triangles!(tri)
get_triangles(tri)
get_neighbours(tri, -1)
get_adjacent2vertex(tri, -1)
get_adjacent(tri, 3, 2)
DelaunayTriangulation.delete_ghost_vertices_from_graph!(tri)
collect(each_solid_vertex(tri)) == collect(each_vertex(tri))
This page was generated using Literate.jl.