Civil Engineering Reference
In-Depth Information
v. If ellipse Ci
j
intersecting with Ci
i
is on the left-hand side of Ci
m
C
m+1
, j = m + p, with p ≥ 2.
On the other hand, if ellipse C
j
is on the right-hand side, j = m − q, with q ≥ 1.
vi. Updating the supporting line segment Ci
m
C
m+1
for the construction of Ci
i
, such that C
i
is now generated from {C
m+p
, C
m-q
}. It is noted that either p or q will be updated within
each cycle of the pushing-out operation. Go to step (i).
After the pushing-out operation, an n-polygon Ci
m
- C
m+1
… C
m+p
- C
i
- C
m-q
… } can be
defined as shown in Figure 4.51c. The problem now under consideration is the triangulation
of a simple n-polygon, which can be easily done by dividing the narrow-shaped polygon
into triangles of the best possible quality. As for the generation front, it could be updated by
including two new segments C
m-q
C
i
and C
i
C
m+p
, and, at the same time, segments from C
m-q
to C
m
, C
m
C
m+1
and from C
m+1
to C
m+p
have to be deleted from the generation front.
The consequence of the push-out operation is that triangles of slightly larger size are
constructed at the concave sites; however, this is not a frequent operation, and the concave
parts are, in general, pretty shallow that the inserted ellipse is only pushed up by one or two
segments as we always search for the segment nearest to the origin to avoid serious concave
parts being formed at the generation front.
There are two ways to control the termination of the packing of ellipses by the ADF
approach. The first way is to check the number of ellipses packed, and the second way is
based on the area of the mesh generated. If the number of ellipse is more than a given num-
ber or if the shortest distance to the origin is larger than a specified value, the procedure
terminates. At this stage, the final generation front can be taken as the boundary of the
triangular mesh generated.
4.3.2 Efficiency and complexity
There are three main operations in the ellipse-packing process. The first operation is to
determine the ellipse insertion site nearest to the origin. The second operation is to deter-
mine the location, size and orientation of the ellipse to be packed at the insertion site. The
third operation is to check whether there are any intersections between the inserted ellipse
and the existing ellipses on the generation front.
As the distance of the ellipses from the origin are stored when they are created, the search-
ing for the nearest ellipse is only a simple comparison. The computation cost grows with
the number of ellipses on the generation front. However, the number of ellipses on the front
increases rather slowly as ellipses are deleted and added to the front. From the examples in
Section 4.3.3, we can see that the number of ellipses on the front is quite small compared
to the number of ellipses in the pack, and the ellipses on the front are always closely packed
together to form a circular ring structure. Upon further investigation into the searching
process, we found that the searching time could be much reduced by restricting the distance
check to a few ellipses near the current insertion site. In the present implementation, only
five ellipses to the left and five ellipses to the right of the current insertion site are checked
to locate the nearest point from the origin for the next insertion. The meshes generated are
virtually the same compared to the scheme in which all the ellipses on the front are tested
for the absolute minimum distance point.
The time of iteration to determine the position, the size and the orientation of the insert-
ing ellipse is controlled by two major factors. The first factor is the initial position of the
ellipse where iteration starts, and the second is the precision adopted for the convergence.
A scheme has been proposed in Section 4.3.1.5 to estimate the initial position of the ellipse
to be inserted. Following this simple procedure, the number of iterations has been greatly
reduced, and the average number of iterations for various metric fields tested in the examples
