Civil Engineering Reference
In-Depth Information
Determine cell k to which point Pi
i
= (x
i
, y
i
, z
i
) belongs:
I
x
= [(x
i
- x
min
)/d
x
] + 1,
I
y
= [(y
i
- y
min
)/d
y
] + 1,
I
z
= [(z
i
- z
min
)/d
z
] + 1,
[.] = Integral part
k = (I
z
- 1)N
xy
+ (I
y
- 1)N
x
+ I
x
where N
xy
= N
x
N
y
.
Points in the cells, or the regular grid of point set
P
, can be fully specified by a single array
A
, such that points assigned to cell k are given by {A
m
, m = A
k
+ 1, A
k+1
}. Whether it is a
2D grid or a 3D grid, by means of the pointer approach, the memory required for the grid
construction is always a linear array
A
of size equal to N + N
c
+ 1.
8.3.3.2 Point insertion by regular grid
The given set of points are partitioned into N
c
= N
x
N
y
N
z
cells, which are inserted cell by cell
in a contiguous manner to reduce the searching time in locating the BASE tetrahedron, as
shown in Figure 8.29, for the insertion of a layer of cells. Given a set of N points, the number
of cells is approximately given by
N
n
N
c
⊕
wherenis the average numberof pointsin
a cell.
There is no theoretical optimal value for n; however, from practical experience, the per-
formance of a regular grid is not very sensitive to n, which can produce satisfactory results
with values ranging from 15 to 30 for various point distributions. The memory requirement
for the construction of a regular grid is relatively low, and all that is needed is an integer
array of size given by
Memory required by regular grid = number of cells + number of points = N
c
+ N
8.3.3.3 Multi-grid as a repeated application of the regular grid
Applying regular grid to non-uniform point distribution, the number of points within a cell
can have a large variation. In some cells, there are more than 1000 points, whereas in other
cells, not even a single point is present. Similar to 2D point insertion, for evenly distributed
point sets, the threshold for the application of regular grid is very low at about 100 points,
i.e. the CPU time will be reduced for the insertion of any reasonable point distributions more
than 100 points by applying a regular grid compared to a direct insertion point by point
in one zone. In view of the very low threshold of about 100 points for regular insertion,
efficiency of point insertion can be significantly enhanced by applying the regular grid in
a recursive manner to cells containing, say, more than 200 points. The searching time for
the location of the BASE tetrahedron can be tightly controlled such that there are about 10
points in each cell that is further divided. However, the number of conflicting tetrahedra
for each point inserted is still governed by the non-uniform distribution characterised with
excessive connections by elongated tetrahedra.
Presence of elongated tetrahedra is an intrinsic feature of highly non-uniform point distri-
butions, which poses a significant difficulty over uniform point distributions. For the same
number of points, much more CPU time will be needed for the triangulation of severe non-
uniformly distributed point sets compared to a uniform distribution or a mildly non-uniform
