Int. J. Rock Mech. Min. Sci. & Geomech. Abstr. Vol. 24, No. 6, pp.

p. 331-338, 1987 0148-9062 87 $3.00+0.00

Printed in Great Britain. All rights reserved Copyright ~ 1987 Pergamon Journals Lid

Geometrical Identification of Three-

dimensional Rock Block Systems Using
Topological Techniques
D. LINt
C. FAIRHURSTI-
A. M. STARFIELDI-
This paper describes a new approach to the problem of defining geometrically
polyhedral rock blocks created by the intersection of planar discontinuities in
a rock mass. The approach represents an extension of the combinatorial
topology concepts to solid geometry, which, when implemented com-
putationally, results in a procedure for the systematic identification of the
spatial arrangement of rock blocks.
The principle of simplicial homology is reviewed and a specific application
of block geometry analysis is presented. Various formulae are shown to be
necessary in the derivation of the block identification algorithm. The simplicity
of the procedure makes it very attractive.

INTRODUCTION believed to be the first to consider convex or concave,

finite or infinite blocks. In the terminology of homology
The stability of excavations in jointed rock masses is
often determined by the mechanical interactions between theory, these blocks are regarded as oriented complexes.
blocks formed by the intersections between the systems The procedure can deal, in principle, with any collection
of joints. This is especially the case when the joint of discontinuity planes, although the implementation we
spacing is an appreciable fraction of the excavation describe handles only the cases of the random ellipse or
dimension. random rectangle with distributed orientations and
Recent work in the static and kinematic analysis of the radii. The simplest and most pragmatic approach is to
stability of such discrete rock systems has been directed assume the discontinuities to be circular planes. (Circles,
to the development of task level computational lan- of course, are a subset of ellipses.)
guages. These languages incorporate a system of geo- Three dimensional identification of classes of poly-
metrical logic for the detection of polyhedral rock blocks hedra is encountered in a variety of problems such as
created by intersecting discontinuities. To date, however, geostatistical analysis, spacing planning, and computer
the polyhedral rock blocks have usually been limited to vision, in addition to block theory and discrete mod-
those defined by the intersection of half spaces, i.e. elling. The pattern recognition techniques for identifying
discontinuities of infinite extent. 3-D geometrical structure are also required in structural
Geometrical treatment of irregular convex polyhedra geology and analysis of microstructure in fracture me-
has been discussed by Preparata and Shamos [1]. Also chanics. In a more realistic sense, based on patch
the Poisson field of infinite random planes has been techniques, the methods discussed here are applicable
studied a great deal by Miles [2] and Barlett [3]. Also, also to the domain of automatic networks generation in
Hudson and Priest [4, 5] and Baecher [6] have obtained three-dimensional finite element, boundary element, and
some useful results of stereological analyses based on other numerical methods.
geometrical probability.
The paper presents a procedure for the analysis of the SIMPLICIAL HOMOLOGY
more realistic case when the discontinuities are of limited
extent. With the procedure presented here it is possible In order to discuss geometrical reasoning problems, it
to detect a polyhedral block formed by the discon- • is useful first to outline some basic concepts and tech-
tinuities, and then to define and collect the correspond- niques in simplicial homology theory [7, 8]. Although the
ing geometric data. The algorithm described here is topological invariance of the simplicial homology group
is quite a deep theorem, the computation of these
oriented geometric complexes (polyhedra) in the given
t Department of Civil and Mineral Engineering, University of space is accomplished by an almost mechanical pro-
Minnesota, Minneapolis, M N 55455-0220, U.S.A. cedure. The collection of all types of polyhedra is vast,
331
332 LIN et aL: T O P O L O G Y O F ROCK BLOCKS

i 1

Fig. 1. Polyhedra which are homomorphic to the sphere SZ(x ~ + y 2 + z,2 = 1). Euler number V - E + F is 2.

and it is desirable at the outset to introduce a system of The purely topological classification of surfaces based
classification for polyhedra. on the Euler number is of limited use unless the poly-
The simplest group of polyhedra to consider are the hedral surfaces can be defined with respect to their actual
regular or perhaps convex, polyhedra, which satisfy the configuration in space. To overcome this difficulty, it is
Euler polyhedron formula published in 1752. useful to introduce, from homology theory, the concepts
of oriented complexes, chains, cycles, boundaries and
v-E+F=2 (1)
homology groups. These can be used in the design of the
where Y, E, F are the numbers of vertices, edges and geometry detection algorithm. Consider the simplexes of
faces, respectively. Examples of such polyhedra are dimension n (n ~< 3) in Fig. 6. A finite collection of
shown in Figs 1-3. simplexes of K in 3-D space is defined as a simplicial
Two surfaces are said to be homeomorphic or topo- complex if each proper or improper side of a simplex in
logically equivalent if they can be made to conform with K is a simplex in K, and the intersection of each pair of
each other by a continuous deformation. (For more simplexes in K is a common side of this simplex pair. A
detail see [7].) Thus, by the application of a homeo- complex K, when regarded as a topological space, is
morphism, the sphere S 2 is equivalent to the polyhedra called a polyhedron and written IK[.
shown in Fig. 1. The Euler number 2 does not belong to
a particular class of polyhedra; it really belongs to the
sphere S ~. The polyhedron shown in Fig. 3 has an
entirely different form. It is homeomorphic to a torus T
(with N = 1 genus) and its Euler number is 0. The Euler
number can be written in the form,
V-E+F=2-2.N. (2)
If a collection of polyhedra is not connected then it
breaks up as a union of connected pieces, and a com-
ponent is a maximally connected subset of its space. If Fig. 3. Polyhedron which is homeomorphic to a torus, Euler number
the entire object has M components, C enclosed cavities is 0.
and a torus with genus N the following formulae can be
used in the algorithm to test the polyhedra being formed
K+C
M-N+C= Y. (3)
Iml

Any closed surface of polyhedra is homeomorphic

either to the sphere S: (Fig. 4), or an orientable surface
of genus N (Fig. 5). These two surfaces are not homeo-
morphie to each other.
Fig. 4. Sphere S 2.

o,,

1 2 ..... N

Fig. 2. Polyhedron with a cavity. Euler number is 4. Fig. 5. Torus T.

 LINet al.: TOPOLOGY OF ROCK BLOCKS 333

z z Z
C

a
ab ~ d ,_
x/ ,/ II

x
,/
x
Y
1-simplex (a b) 2-simplex (a b c) 3-simplex (a b c d)

Fig. 6. Simplexesin three dimension.

The complex in Fig. 7 contains four 3-simplexes, i.e. plex. Indeed, one simple method of orienting an arbi-
sl:(aoala2as), s2:(aoa2a3as), s3:(aoa3a4as), and trary complex is to list all of its vertices in some order
s4 :(aoa4at as) which fit together to make a pyramid with and require that its simplexes be oriented in a sense
a base. The concept of orientation is relatively simple on specified by the order in which their vertices appear in
the line and in the plane because it is an intuitive concept the list. We shall discuss this type of data structure in the
based on visual inspection of the figures. It is obvious, next section.
for example, that the l-simplex (a~ as) (one-dimensional Now, we will define Cp(K) to be the free abelian group
simplex) has two orientations one positive and one generated by the oriented p-simplexes (p ~< 3). An ele-
negative orientation. For the 2-simplex (a~a~a~), there ment of this group is called a p-dimensional chain or
are two orientations counterclockwise and clockwise. simply a p-chain, in K. A p-chain can be considered as
Now, let a~: (a~ . . . . , ai~), i = O, 1 . . . . , n, be the n + 1 a linear combination c = E~(nisi (i = 1 , . . . , m), where
point in the n-dimensional space R ~. The vector a i - ao, the ni are integers and the sum is over all oriented
i = 1 , . . . , n, are linearly independent. The simplex with p-simplexes si in K. However, from the algebraic point
vertices a~, i = 0, 1. . . . , n has two orientations; one ori- of view, chains E'~nis~ are the group structure of Cp(K)
entation is the class of even permutations of and appear to be far removed from the original geo-
(a0, a t . . . . . a~), and the other is the class of odd per- metrical conception of a 1-chain as a string, or a 2-chain
mutations. The two orientations of a simplex can be as a polygon.
readily characterized by a determinant as follows. Let K be an oriented complex and let Z~'nis i be a
p-chain in Cp(K). The boundary OE~n~s~ of Y~'n~sg is the
( - 1)~A(a0am... a,) > 0 (positive)
(4) (p - 1)-dimensional chain in Cp_ t(g), as defined by the
( - 1)~A(a0a~... a~) < 0 (negative) following equation
where
c~ n,si = ~ n,c~si (6)
ao~ ao2...ao~ I \l / l

A(a0ai...a,)= au al2...at~ 1 (5) where the 3s,.is a (p - 1)-chain in K consisting of the sum
of the ( p - 1)-faces of s:, each with the orientation it
ant an2...ann 1
inherits from s~, that is, 3sg = Y.~(-1)J (a0... d j . . . a,).
The form (a0... d j . . . ap) is the shorthand notation for
A complex in which each simplex has been provided the oriented ( p - 1)-simplex obtained by deleting the
with some fixed orientations is called an oriented com- vertex aj. Therefore operator 3 determines a homeo-
morphism
d :Cp(K) ~ Cp_~ (K). (7)
In general, it seems clear that any p-chain that is a
a1
a3 boundary of a (p + 1)-chain is a p-cycle cp. The set of
p-cycles in a complex for which dcp = 0, denoted by
Z p ( K ) , is precisely the kernel of the homeomorphism
operator ~ and, of course, is a subset of C;(K).
Observe that the four 3-simplexes in Fig. 7, have been
oriented such that each one is positively oriented in 3-D.
• By definition c~(E~s~)= E~c~si.
II a5
dsl = (ala2as) - (aoa2as) + (aoalas) - (aoala2)
ds2 = (a2a3as) - (aoa3as) + (aoa2as) - (a0a2a3)
(8)
~3s3 = (a3a4as) - (aoa4as) + (aoa3as) - (aoa3a4)
Fig. 7. Example of a complex with four 3-simplexes. 3s4 = (a4atas) - (aoal as) + (aoa4as) - (aoa4al).
334 LIN et al.: TOPOLOGYOF ROCK BLOCKS

Then lar, the computation of Ho(K) is useful for the detection

algorithm. All of the vertices of K which are connected
t3(sl + s, + s3 + s4) by 1-chains are in the same equivalence class module
= Ost + Os2 + Os3 + Os4 = (a~a2as) - (aoala2) Bo(K), so Ho(K) is a finitely generated abelian group
with one generator and is therefore cyclic. Thus we have
+ (a2a3as) - (aoa2a~)+ (a3a4as) - (aoaaa4) Ho(K) .~ Z (group of integer). If two 0-cycles a and b are
+ (a4atas) - (aoa4al). (9) homologous they can be connected by 1-chains, that is,
there are edges leading from a to b. Thus we have the
We observe that if two plane faces have a common following result: Ho(K) is a free abelian group whose
edge, then this edge inherits opposite orientations from rank is the number of components of IKI.
each of the two faces. We next compute 00s= by com- Geometrically, the 2-simplexes in K fit together to
puting the boundary of the chains in the first equation form a closed surface of polyhedra. From a topological
in (8) point of view, these surfaces have no edges. The
dos, = (a2as) -- (a, as) + (a, a2) 2-boundaries in B2(K) have oriented l-boundaries, each
of which belongs to two 2-boundaries. These common
- - (a2as) + (aoas) -- (aoa2)
one-dimensional sides have opposite orientations in the
+ (al as) - - ( a o a s ) + ( a o a l ) two faces to which they belong, and they cancel each
other. Thus the topological boundary of the surfaces
- (ala2) + (aoa2) -- (a0a,) -- 0. (10)
formed by simplexes is empty; the algebraic boundary of
Similar calculation shows that a chain is the zero chain.

00 s~ = 0. (11)
ALGORITHM FOR C=(K) AND Bt(K) IN PLANE
We define homeomorphisms on these chain groups,
and in doing so our approach will always be the same. The natural approach to solving a three-dimensional
The composition O0, i.e. problem is to attempt to generalize the method used for
the corresponding two-dimensional problem. The first
Cp+,(K) ~)cp(r) e)C,_t(X) (12) task is the construction of a double directed chain list as
our initial data structure for Ct (K), from which we can
is the trivial homeomorphism. This result is the basis on readily obtain information about the incident either on
which we will construct our discussion of topological a vertex or on the edges. Two vertices, a and b, are said
polyhedra in the context of a finitely generated abelian to be double directed if there is a directed path from a
group. to b and a directed path from b to a. The first step
The set of all such cycles that are the boundary of required is to obtain all intersections between surface
(p + 1)-chains, denoted Bp(K), is precisely the image of elements. In many cases spatial separation techniques
the homeomorphism operator, and is thus a subset of are useful for reducing the number of pairs of faces
Cp(K). From equation (11), the trivial homeomorphism which need to be considered. Also, once a pair of faces
shows us that any p-boundary is a p-cycle, that is, is obtained, an initial check may be made to determine
Bp(K) ~ Zp(K) c Cp(K) for any p. The group Hp(K) is whether their bounding boxes intersect before the actual
called the simplicial homology group of K is and defined intersection is performed. Thus, the intersection may be
by Hp(K)=Zp(K)/B,(K). In general, the objects of found following the procedure shown below:
primary concern in our geometrical detection method
Procedure--Intersection of faces
are the 2-cycles that are 2-boundaries, that is, B2(K);
since the 2-boundaries of K are just those 2-cycles that Input: f = {fl ,f2, .-. ,f,}.
bound the interior region of the polyhedron. In particu- Output: A set of intersections {auk}.

Z
Z

Y
/
Fig. 8. Disk face and intersection of two disk faces.
 L I N e t al.: TOPOLOGY OF ROCK BLOCKS 335

begin group B~(K) is generated by taking the single edge paths

for i = 1 to n given in counterclockwise order and eliminating any
for j = 1 to n portion of the form pp- ~i.e. where a path out and back
begin along an edge returns to its starting point (Fig. 9).
Intersect the planes of the facets f and fj, obtain a
Procedure--Construction of B~(K)
line L,j.
Intersect L U with facets f and fj, obtaining line Input: A doubly directed chain list DDCL
segment lij. Output: A singly directed cycle list SDCL
for k = 1 to n while D D C L ¢ ~b
begin step 1. Start on an edge in the field V~ and V2 facing
Intersect lij with f~, obtain a point set {a~jk} away from the terminus of the edge; mark
end the edge.
end step 2. Perform a leftmost traversal; find the new
end edge; mark the edge; traverse from the new
The results of a typical disk face intersection is origin of the new edge.
depicted in Fig. 8. step 3. If the terminus of the new turns to the
After performing all facet intersections along the line, origin (pp-~= 1), delete both the old edge
the results is a collection of vertices (a~ . . . . . a,). Next and the new one.
the following procedure may be used to reorder the step 4. If the traversal succeeds, it provides a se-
sequence of vertices according to their co-ordinates quence of the edges (a 1-cycle), which
(pa~ . . . . . pa,) projected into a suitable axis. bound an undivided polygonal region.
step 5. Test the area of the newly generated poly-
Procedure--Reordering of sequence of vertices gon in the field A: if the area is positive
Input sequence (a I . . . . . a,) and (pal,... ,pa,) mark the chain in either field Ft or F2.
Output the reordered sequence (at . . . . , a,) Indicating the number of the interior
begin polygon.
for i = l to n - 1 step 6. If the area is negative then mark in the field
forj=i+l ton Ft or F2, indicating the number for the
if (pai> paj) then boundary of the exterior component.
begin step 7. If both the fields Ft and F2 are marked then
aux = pai cancel the chain in the list.
pai= paj As an example, a fragment of a graph and the
paj = aux corresponding fragment of the D D C L and the SDCL are
end shown in Figs t0 and 11.
end The leftmost traversal in a plane is simply the concat-
enation of a finite number of moves and leftmost turns.
The edge nodes of a double directed chain list are
The procedure identifies all cycles which bound un-
important. Each edge is represented twice. An edge node divided polygons by exhaustive application of the left-
consists of two information fields Vl and V2. The field
most traversal routine. However, it also takes advantage
V~ contains the name of the vertex which is the origin of
of the fact that each edge may be traversed only twice
the edge, whereas V2 contains the terminus; in this
altogether, once in each direction. In the traversal pro-
manner, the edge receives a conventional orientation.
cess, it can abort all redundant traversals as soon as an
Henceforth, all chains in C~(K) are assumed to be
edge is found which has already been traversed in the
oriented. The leftmost traversal technique allows us to
opposite direction.
detect the boundaries of any undivided polygon which is
initially on our left by traversing the boundary of the
ALGORITHM FOR B2(K) IN SPACE
polygon in a counterclockwise direction. The application
of leftmost traversal leads us to the following procedure, In the last section, we discussed the method of bound-
which we use to detect the B~(K) that is exactly the set ary construction for the planar case. It was seen that,
of boundaries of the polygonal region of the plane. This with the appropriate starting edge and direction, the

q•f-1 Fig. 9. Eliminationof portions of the form pp-~ = 1.

336 LIN et al.: TOPOLOGY OF ROCK BLOCKS

V7 V2 Ft 7-?
I ,:s.~ a2 1 @
2 a2 a3 2 @
3 a,= a5 ,4 0
4 a5 a6 3 S

/F2a~9' "F~F.,
i~a
. ,., 5~a~o
15 5
6
7
a6
a4
a8
a7
a8
a9
6
4
1
0
0
3

16 a 9............................
a2 1 2

Fig. 10. Illustration of the Doubly Directed Chain List DDCL.

leftmost traversal routine could be used to find the The angles between normal nf and the direction from F
boundary of a planar graph. We then extended this to Gi (i = 1. . . . ,4) determines which surface is the fight
procedure to get B2(K) which would partition the space choice. From the diagram, we see that faces F and G~
into its undivided polyhedral region. A similar approach bound a convex region and _g and G3 bound a concave
is used for the three dimensional case. The concept of one. The largest angle between nf(normal to F) and the
traversing an edge in a given direction is replaced with auxiliary lines which link two faces in the circle indicates
the concept of walking around the boundary of a face the most likely path to be taken.
in a given dir~tion. This direction is conveniently In the procedure for the planar case, we marked edges
represented by the direction of the right-handed normal in each direction that were "leftmost traversed". In
to the face generated by the boundary walk. Consider space, we need to mark those faces that were "innermost
the face F in Fig. 12. Suppose that F has an inward traversed". Since we know that our partition will admit
pointing surface normal nf The potentially adjoining only one traversal of each face in each direction and that
faces along the edge would have outward pointing the algebraic boundary of the chains is the zero chain,
surface normals ng~, ng2, ng3 and ng4. We wish to we can use these marks to abort redundant traversals.
determine which of the adjoining faces along the edge is Also, the oriented volume approach, analogous to the
also part of the boundary. We may determine the oriented area used in the last section for the planar case,
innermost adjoining face computationally as follows. can be used to distinguish interior from exterior regions.

V1 V2 F1 A
1 a~ a2 1 5.9
2 a2 a9 1 5.9
3 a9 a8 1 5.9
4 a8 a~ 1 5.9
a3 5 a2 a3 2 1.8
6 a3 ,39 2 1.8

"~6~ ..-.>al 0 7 a9 a2 2 1.8

all
a7 2i a 7............................
al~ 6 1.7

Fig. 11. Illustration of the Singly Directed Chain List SDCL.

ngsG3

F
~ G3

G~ G2
nf G2

G~ ngl
Fig. 12. Neighbouring faces of F along an edge and the innermost traversal.
 LIN et al.: TOPOLOGY OF ROCK BLOCKS 337

We will use the global connectivity properties of poly- a

hedra to detect all undivided convex, concave, finite or
infinite blocks and to obtain geometric information.
The following procedure is a straightforward method
for detecting the B 2 ( K ) which form the closed surfaces
of polyhedra from B~ (K) in the planar case, eliminating
redundancy in a mechanical manner.

Procedure--Construction o f B,.(K)
Input: A singly directed cycle list SDCL for B~(K). b
Output: A singly directed cycle list SDCL for B:(K). Fig. 13. Two unconnectedcubes, i.e. in two components.
A field C for components.
while SDCL # ~b
a
begin
Start on an edge in a cycle in list SDCL for B t (K).
Mark edges in the field M.
While field B u or field B2 are not marked
begin
step 1. Perform an innermost traversal; find
the same edge with opposite orien-
tation in the new cycle. Mark edges
in the new cycle in the field M once.
step 2. If the innermost traversal could not
find the new cycle, delete the cycle in
the list. b
step 3. Start on the edge in the cycle which Fig. 14. Two connected cubes, i.e. in one component.
has already been marked once. Re-
turn to step 1 until all edges are
marked twice. face connectivity are always guaranteed within a com-
ponent. In the meantime, face connectivity should be
step 4. Calculate the area for the traversed
checked between components.
cycles (faces) and the barycentric
co-ordinates and the volume of the
polyhedron which is formed by the CONCLUSION
traversed cycles.
We have exhibited a new framework for detection of
step 5. If the volume of the polyhedron is
positive then mark each cycle in the spatial geometries based on topological concepts and
techniques. By the use of chain, cycle and boundary
field Bj or B2, indicating the number
of the block. homeomorphism we have developed a generic way of
step 6. If the volume is negative, mark the defining operations for computing rock block bound-
field B~ or B2, indicating the number aries. We believe this new framework offers an im-
of the exterior boundary. portant tool for geometric detection and eliminates a
step 7. Reverse all the orientations of cycles bottleneck in geostatistics and system analysis.
which have been traversed. Acknowledgements--The work in this paper was supported in part by
end the National ScienceFoundation under Grant CEE-8120700-02and in
If both of the fields B~ and B 2 are marked, then part by Institutional Account in the Department of Civil and Mineral
Engineering, University of Minnesota under Grant 0953-1737.
cancel the cycle in the list. Record any one vertex The first author thanks Dr Gen-hua Shi of the University of
ar from each component in the field C. California, Berkeleyfor valuable suggestions that resulted in a better
end understanding and presentation of the concepts in this paper.

The field C recorded a collection {at) consisting of one

- Received 26 January 1987; revised 4 July 1987.
vertex from each of the subcomplexes K z . . . . . K q of K
such that two vertices a and b of K can be connected by
a 1-chain in K if a and b belong to the same subcomplex REFERENCES
K', 1 ~< r ~< q, of K. Figure 13 shows two cubes which are 1. Preparata F. and Shamos M. I. Computational Geometry: An
not 1-chain connected and Fig. 14 is a component Introduction, 390 pp, Springer-Verlag,New York (1985).
resulting from connectivity. From the previous section 2. Miles R. E. The random division of space. Adv. Appl. Probl.,
Suppl., pp. 243-266 (1972).
we know the rank of H o ( K ) is the number of com- 3. Bartlett M. S. The Statistical Analysis of Spatial Pattern, 90 pp.
ponents. If {a,} is a set consisting of one vertex from Chapman & Hall, London (1975).
each component of IK] then the homology classes of the 4. Hudson J. A. and Priest S. D. Discontinuities and rock mass
geometry. Int. J. Rock Mech. Min. Sci. & Geomech. Abstr. 16,
chain a, form a basis for H o ( K ) . Edge connectivity and 339-362 (1979).
R,M,M.$. 24/6..--13
338 LIN et al.: TOPOLOGY OF ROCK BLOCKS

5. Hudson J. A. and Priest S. D. Discontinuity frequency in rock 7. Munkres J. R. Topology: A Firs: Course. 413 pp. Prentice-Hail,
masses, lnt, J. Rock Mech. Min. Sci.& Geomech. Abstr. 20, 73-89 Englewood Cliff, N. J. (1975).
(1983). 8. Munkres J. R. Elements of Algebraic Topology, ,*54 pp.
6. Bacchcr G. B. Statistical analysis of rock mass fracturing. Mathl Benjamin/Cummings, Menlo Park, Calif. (1984).
Geol. 15(2), 329--348 (1983).