Page 114 - The Combined Finite-Discrete Element Method

SORTING CONTACT DETECTION ALGORITHM 97

The following formula is used in sorting arrays:
discrete element i is before discrete element j if (3.41)
int int
x i < x j
or if
int int int int
x i = x j and y i < y j

Step 3: Binary search of sorted arrays for contact: after the sorting process, array D
acquires a spatial dimension. Discrete elements closer to the beginning of array D are
positioned closer to the first column of cells, while the discrete elements closer to the end
of array D are positioned closer to the last column of cells. Finding any particular cell
(i, j) involves searching the arrays.
To detect contacts for particular discrete elements, it is enough to search for cells
neighbouring the cell to which a particular element is mapped. Once the neighbouring
cells are identified, a contact check is performed between the particular discrete element
and all the discrete elements from neighbouring cells and the central cell.
Detection of contacts is done by looping over discrete elements:

Loop over discrete elements (k=1; k≤N;k++)
{ Integerise current coordinates of the discrete element
and identify the cell onto which it is mapped (central cell)

int x k − x min
i = x k = 1 + Int (3.42)
d

int y k − y min
j = y k = 1 + Int
d
Use binary search to search the sorting arrays to find
the central and neighbouring cells
check for contact against discrete elements in these cells
}
Once the central cell (i, j) for a particular discrete element k is identified, the neighbour-
ing cells are simply: (i − 1,j − 1), (i, j − 1), (i + 1,j − 1) and (i − 1,j). All discrete
elements mapped onto these cells have to be found by searching arrays X, Y and D.This
can be done using the binary search.
The first stage of the search process for a particular cells is shown in Figure 3.25. The
arrays are searched for cell (5,7). Thus, in Figure 3.25, arrays X, Y and D are divided
into two arrays of equal (or near equal) size. The part that does not contain the cell that
is being searched for is rejected.
The remaining parts of arrays X, Y and D (non-shaded area in Figure 3.26) are further
divided into two equal parts, as shown in Figure 3.26. Again, the part that does not contain
cell (5,7) is rejected.
Further subdivision (shown in Figure 3.27) finally identifies the cell that is being
searched for, i.e. cell (5,7). It is evident from array D that this cell contains the discrete
element identified as discrete element number 4.