Civil Engineering Reference
In-Depth Information
7.3.3 Simultaneous insertion within zones
Similar to a single-processor insertion, the initial triangulation is a rectangular bounding
box of two triangles large enough to contain all the points. Point insertion in each zone
will be handled by one single processor in a completely independent manner. All the points
within each zone (say, zone I, I = 1,N
p
) will be first processed by inserting points in those
cells belonging to the zone under consideration. This will generate all the Delaunay triangles
within the zones; however, Delaunay triangles cutting the zonal boundary are missing, as
shown in Figure 7.5. The second step is to construct all the Delaunay triangles at the bound-
ary between zones. To do so, boundary cells are added around the zone, which are the cells
contained in two columns on the right and on the left and in two rows on the top and on the
bottom of the zone, as shown in Figure 7.6. Boundary triangles are defined as those triangles
supported on vertices from the current zone I and vertex or vertices from neighbouring
zone(s), as shown in Figure 7.6. This simple definition is a topological one, which works on
zones of any geometry and no matter how they are partitioned, i.e. it is also applicable to
Quadtree/Octree and kd-tree partitions.
By the lemma of Delaunay, if all the boundary triangles are Delaunay, the triangles within
the zone will also be Delaunay. Hence, the next step is to ensure that all the boundary tri-
angles are Delaunay. Compute the circumcircles of all the boundary triangles, and check
if any circle crosses the boundary of the augmented zone with a layer of cells added to the
boundary of the original zone I. In case a circle cut across the vertical boundary of the rect-
angular zone on the right, a column of cells will be added to the right of the region. Not all
the points in this column have to be inserted, and only those that fall into one of the circum-
circles cutting the vertical boundary need to be considered. This operation can be applied to
the boundary edge of the zone on the left and the boundary edges at the bottom and at the
top wherever necessary until all the circumcircles of the boundary triangles are bounded by
the ever-expanding zone of additional columns and rows of cells. As cells contain a roughly
equal number of points, the process converges fairly rapidly and evenly on all the zonal
boundary edges in one or two layers of cells, as shown in Figure 7.6. After adding one layer
of cells around the middle zone I, almost no circumcircles of boundary triangles cut across
Delaunay triangles
created in a zone
Figure 7.5
Points inserted within a zone.
