Civil Engineering Reference
In-Depth Information
Table 2.6
Pointer array
P
for an irregular grid of 40 points
i
1
2
3
4
5
6
7
8
9
10
P
i
10
15
18
22
25
30
35
39
44
50
P
10+i
{7
16
27
30
32}
{13
21
37}
{5
17
P
20+i
36
38}
{12
25
26}
{17
15
22
24
34}
P
30+i
{3
10
23
35
40}
{2
6
19
33}
{4
P
40+i
8
11
20
31}
{9
14
18
28
29
39}
rectangular domain into zones along the horizontal and vertical directions. However, as shown
in this example, the points in each cell are much more evenly distributed: six points in cell 9;
five points in cells 1, 5, 6 and 8; four points in cells 3 and 7; and three points in cells 2 and 4.
Analogous to regular grid construction, the points assigned to cell k are given by {P
m
, m =
P
k
+ 1, P
k+1
}. Given a point
p
(x,y), the containing cell k is given exactly by the same formulas
as in the point-allocation procedure: k = (I
y
− 1)N
x
+ I
x
, where x lies between grid lines I
x
and I
x
+ 1, and y lies between grid lines I
y
and I
y
+ 1.
An irregular grid over three dimensions can be constructed following the same procedure
as a 2D irregular grid, except that points have to be sorted along the x-, y- and z-directions.
Let I
i
, J
i
and K
i
be, respectively, the ranking of the points along the x-, y- and z-directions;
then the cell k to which point i belongs is given by
k = (I
z
- 1)N
xy
+ (I
y
- 1)N
x
+ I
x
,
where
I
x
= I
i
/N
1
+ 1, if (I
x
> N
x
) I
x
= N
x
,
I
y
= J
i
/N
2
+ 1, if (I
y
> N
y
) I
y
= N
y
,
I
z
= K
i
/N
3
+ 1, if (I
z
> N
z
) I
z
= N
z
In summary, irregular grids can effectively deal with moderately non-uniformly distrib-
uted points; however, as compared to regular grids, additional effort in the sorting of points
is required.
2.7.6 Quadtree
To cope with the highly uneven distribution of points, cells can be refined locally until there
are only a few points in each cell. Such a partition of space in 2D was named by Finkel
and Bentley (1974) as Quadtree. The Quadtree partition of space has tremendous applica-
tions in computer graphics and MG (Bentley 1975; Bentley and Ottmann 1979). Efficient
image and video coding scheme by means of the Quadtree was proposed by Sullivan and
Baker (1994) to reduce the cost of image communication and storage. A Quadtree-based
adaptive mesh refinement scheme using material force and residual error estimates was pre-
sented by Tabarraei and Sukumar (2005, 2007), and in modelling of discontinuous field
by Tabarraei and Sukumar (2008). To construct a Quadtree subdivision for a set of N
points on a 2D plane, first, a bounding rectangle containing all the points has to be defined
