Mesh generation on planar domain - Finite Element Mesh Generation - page 105

3.5.4.8 Correction of the CORE
Inconsistency of the circle inclusion test is to be supplemented and corrected by the visibility
check or the positive volume test. As shown in Figure 3.31, an edge ba is visible to point p if
Δ( bap ) > 0. The boundary of the CORE is a valid one if all the edges on the boundary give a
positive response to the visibility test. Suppose we have an inconsistent inclusion test for the
cyclic points a , b , c , d , such that with respect to point p, triangle acd is deleted, and triangle
abc is retained, as shown in Figure 3.31. In this case, the CORE is not a connect piece since
it is separated into two parts by triangle abc . For the portion of the CORE that contains p ,
there is no problem for the visibility test on the boundary edges. However, as for the bound-
ary edges due to the removal of triangle acd , at least one of the edges will form a triangle
with a negative area, which is definitely invalid and should be corrected. The boundary
edge that forms a triangle of a negative area with point p has to be restored. To this end,
the triangle connected to this edge has to be reinstated, and the boundary edges are updated
taking into account the inclusion of this triangle.
Poorly shaped triangles can also be avoided by the visibility test if it is insisted that their
areas have to be greater than a certain threshold value. The condition that every edge on
the boundary of the CORE is visible to point p also guarantees that the CORE is a single
connected piece. The visibility check, albeit simple, is a necessary and sufficient condition
to ensure that the CORE is a star-shaped polygon with respect to the insertion point p . In
fact, other inclusion criteria can be adopted as to which triangles are to be deleted by the
insertion point p to obtain different triangulations; the closer to the empty-circle criterion,
the closer the resulting triangulation to DT. In the extreme case, upon the introduction of
point p , only one triangle, the BASE triangle that contains point p , is deleted. Of course, by
this simple rule, one is far away from the DT. Although a valid triangulation of the point
set can be obtained rapidly, the triangles so generated are flat and almost degenerated. In
summary, the visibility check ensures the validity of the triangulation, and using higher
precision arithmetic in the circle inclusion test guarantees that the resulting triangulation is
as close to a Delaunay one as possible.
In some rare occasions, an existing point is found at the interior of the CORE as shown
in Figure 3.32. As all the triangles connected to the point are removed, this point will
also be removed by the newly inserted point. A remedy to this situation is to restore a
non-Delaunay triangle connect to the point that is also visible to the inserted point but
just barely failed in the Delaunay test. The visibility test that follows will restore more
triangles if necessary to ensure the visibility of the CORE and that each triangle will have
a positive area.
Triangles restored
q
p
Figure 3.32 An existing point q is deleted by the inserted point p .