Page 102 - The Combined Finite-Discrete Element Method

BINARY TREE BASED CONTACT DETECTION ALGORITHM 85

Level 5 9 7 5 3

Level 4
Level 3

Level 2

Level 1 Root

Figure 3.12 Singly connected list showing discrete elements mapped onto the cell at level 5.

Integer array E 9 7 5 3

−1 −1 −1 −1 3 −1 5 −1 7 −1 −1 −1
1 2 3 4 5 6 7 8 9 10 N−1 N
Figure 3.13 Singly connected list.

Thus, for instance, if discrete element number 1 is to be added onto the list, one simply sets

E[1] = HEAD; i.e. 9
(3.21)
HEAD = 1
Thus, the new list becomes as shown in Figure 3.14.
It is worth mentioning that HEADs are stored at the leaf node level of the binary
tree, i.e. they are an integral part of the binary tree. Each leaf node has one HEAD,
represented by one integer number, which is the first discrete element in the list. It is also
worth noting that in C and/or C++ implementations, very often pointers are used instead
of integer numbers. These usually make the code run faster, save memory space, but may
also lead to implementation errors (bugs) difficult to detect.

Integer array E
1 9 7 5 3

9 −1 −1 −1 3 −1 5 −1 7 −1 −1 −1
1 2 3 4 5 6 7 8 9 10 N−1 N

Figure 3.14 The singly connected list after addition of discrete element 1.