Without inner grid points given, the algorithm of VORONOI
(Algorithm 6.4) performs a
so-called boundary-boundary triangulation. Depending on the
peculiarities of the geometry, a comparatively small number of
additional boundary points is inserted to make the geometry
reproducible by Delaunay triangulation
without inner grid points
.
Figures 6.34 to 6.37 show examples of boundary-boundary triangulations. The given geometries are triangulated without adding inner grid points. A typical application of such functionality is the decomposition of a complex geometry into triangular faces.
Figure 6.34: The geometry of the VISTA logo
From the geometry in Figure 6.34 (the VISTA logo), VORONOI creates a triangulation of the grid point cloud which in this case contains only original boundary points and refined boundary points. The result of these steps (Boundary Refinement and Triangulation in Algorithm 6.4) is shown in Figure 6.35.
Figure 6.35: Delaunay triangulation of the VISTA logo
before the grid segmentation step
Then VORONOI forms a subset of all triangles which lie on a segment of the geometry, all other triangles are removed (step Segmentation in Algorithm 6.4). The final geometry-conforming triangulation is shown in Figure 6.36.
Figure 6.36: Final boundary-boundary triangulation of the
VISTA logo
The geometry shown in Figure 6.37 (a simplified map of Austria with the exception of Vienna) is multiply connected. Again, a triangulation has been performed by VORONOI without adding inner grid points. The CPU time required by VORONOI for the solution of this problem on a PC 486 (DX2, 66Mhz) (running Linux 1.0) is 1.2 seconds.
Figure 6.37: Boundary-boundary triangulation of Austria
without Vienna