Civil Engineering Reference
In-Depth Information
Algorithm Irregular_Grid (N, I, J, P)
// N = Number of points, P = Pointer to record points in each cell
// I, J = Ranking of points in x- and y-direction
{
Set pointer array P to zero, P
i
= 0, i = 1, N
c
+ 1
Loop: i = 1,N // Determine the number of points in each cell
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
k = (I
y
- 1)N
x
+ I
x
P
k
= P
k
+ 1
End loop i
Loop: k = 1, N
c
// Compute P
k
= cumulative number of points up
// to cell k
P
k+1
= P
K+1
+ P
k
End loop k
Loop: i = 1,N // Assign points to each cell
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
k = (I
y
- 1)N
x
+ I
x
m = P
k
; P
m
= i; P
k
= m - 1
End loop i }
The memory requirement of an irregular grid is the same as that of a regular grid, i.e.
the length of pointer array
P
is given by N + N
c
+ 1. An irregular grid of the same set of 40
randomly generated points is constructed, as shown in Figure 2.46. The rectangle is divided
into three vertical strips at x
19
= x
min
, x
24
, x
29
, x
5
= x
max
, and there are exactly 13 points in
each of the first two strips (between x
19
and x
24
, x
24
and x
29
) and 14 points in the third strip
between x
29
and x
5
. Similarly, the rectangle is also divided into three horizontal strips at
y
17
= y
min
, y
34
, y
29
, y
31
= y
max
, and there are exactly 13 points in each of the first two strips
(between y
17
and y
34
, y
34
and y
29
) and 14 points in the third strip between y
29
and y
31
. The
pointer array P for the irregular grid is shown in Table 2.6. The effort and the procedure in
constructing an irregular grid are similar to those of a regular grid except that the points
have to be sorted along the x- and y-directions to determine the positions in dividing up the
y
31
7
8
9
x
19
y
29
x
29
6
4
5
x
24
y
34
1
2
3
x
5
y
17
Figure 2.46
Irregular grid of nine zones for 40 randomly generated points.