CLOSED-FORM SOLUTIONS FOR COMPUTING THE INTERSECTION BETWEEN TWO DISKS IN 3-D H. A. ALMOHAMAD* Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117. and Shokri Z. SELIM Department of Systems Engineering King Fahd University of Petroleum and Minerals Dhahran 31261, Saudi Arabia. Technical Report # 94-7 Feb. 1994 Abstract: This report presents an algorithm for computing the intersection between two circular disks in three-dimensional space. Rotation transformations and geometric properties of disks are used to simplify the intersection problem. The proposed algorithm enumerates the possible solutions of the simplified model, and uses deduction and/or induction techniques to find out the intersecting points. In all cases, closed-form solutions are obtained, and few tests are sufficient to compute the intersection, or to show that no such intersection exists. Keywords: Computational geometry, circular disks, intersection detection and computation, algebraic computation. *On Sabbatical Leave from King Fahd University of Petroleum and Minerals, Department of Systems Engineering, Dhahran 31261, Saudi Arabia. 1

I. Introduction The problems of minimum distance, and intersection detection and computation between two objects in three-dimensional space, have important applications in robotics, CAD systems, VLSI and other areas of information processing that deal with geometrical data. In particular, the intersection problem has been studied in the literature for a class of objects that can be represented by linear models. This class includes, line segments [1], rectangles [2, 3, and 4], boxes [5], planar polygons [6, 7, and 8], and convex polyhedrals [9, 10, and 11]. Other references on the intersection problem and its applications can be found in [12, 13, 14, and 15]. In this report, we are interested in solving the intersection problem between two circular disks defined in three-dimensional space with arbitrary position and orientation. The solutions to this problem depend on the representation used to describe a disk. For example, we can define a disk as a finite number of concentric circles, where each circle is defined by a finite number of points. In this case, for a given pair of disks, it might be possible to find a polynomial time algorithm for computing the intersection or the minimum distance between both disks. However, this method provides approximate solutions, depending on the number of circles and points used to define the disks. This approach may not be adequate if we are looking for exact solutions. In this work, we consider a disk as a continuous area of points (an infinite number of points). A point of the disk may be represented by polar coordinates, Cartesian coordinates, or by some other equivalent parametric representations. Unlike the previous problems, where the objects are defined by half planes, the geometry of a disk is nonlinear by nature. In general, nonlinear models can be solved using nonlinear mathematical programming methods. However, for some problems, these methods may not be suitable for real-time applications because of their computational complexity. Besides, reasoning the geometry of disks may sensibly reduce the complexity of the problem, and provides fast computational solutions. Our Approach for the intersection problem between two disks is based on using rotation transformations and geometric properties of disks. These operations produce a system of nonlinear equations that is more simple to solve than the original system. An algorithm that uses induction and/or deduction technique for solving the reduced system will be proposed. In all cases, closed-form solutions will be obtained for the intersection problem. The proposed algorithm (apparently the first in the literature) requires a small number of tests to compute the intersecting points, or to show that no such intersection exists. 2

II. Disks Intersection Formulation Let F=(X,Y,Z) be the attached coordinates frame of a circular disk K centered at the origin O and lying in the X-Y plane of F. A disk is a collection of points V which can be represented as follows: K = {V=(x,y,z)T I x = r cos(q), y = r sin(q), z = 0, 0 < r < D} (1) where D is the radius of the disk. An arbitrary 3D disk is obtained by rotating K and translating its origin with respect to a fixed coordinates frame Fo = (Xo,Yo,Zo). Let R be a 3 x 3 rotation matrix that defines the disk plane, and let P=(Px,Py,Pz)T be its origin with respect to Fo. Let W be the absolute coordinates vector of a point V on the disk, then K can be defined as follows: K ={W= R V + P IV= (x,y,z)T, x = r cos(q), y = r sin(q), z = 0, 0 < r <D} (2) Let K1 and K2 be two disks centered at P1 = (Plxly, Plz)T and P2 = (P2x, P2y,P2z)T with radius D1 and D2 respectively. Let R1 = {RIij}and R2 = {R2ij}, i, j = 1, 2, 3, be the rotation matrices that define the planes of K1 and K2 respectively. Determining the intersection between K1 and K2 is equivalent to solving the following problem: R1 V1+P1 = R2V2 + P2 (3) subject to IIVll1 D1, IIV2II1 D2, where V1 = (Vlx, Vly, 0)T, V2= (V2y, V2y, O)T, and II. II denotes the L2-norm. Problem (3) represents a quadratic system having five equations in four unknowns, namely xl, Y1, x2, and y2. In the following Lemma, we show a relationship between the locations of the optimal points Vi and V2 when the two disks have some intersection. This property is stated as follows: Lemma 1: If K1 and K2 intersect, then there exists at least one intersecting point V for which: rl=D1 or r2=D2 Proof: Assume that K1 and K2 have an intersection A, then three cases arise: A is a point A is a straight-line A is an arbitrary area It is clear in the first case that the intersecting point is on the edge of either K1 and K2, and hence either rl = D1 or r2 = D2. If the intersection is a straight-line, then the two end points of the line lie either on the edge of K1 or K2, or both. This implies that the end points have rl = D1 or r2 = D2. Case 3 implies that the two disks lie in the same plane which contains the intersection area. 3

Hence there exists at least one intersection point for which rl = D1 and r2 = D2. This completes the proof. Recall that a rotation matrix R is an orthogonal matrix satisfying R RT = RT R = I, where RT denotes the transpose of R, and I is a 3 x 3 identity matrix. Multiplying both sides of (3) by R1T, one obtains after rearrangement: V1 = R1T R2 V2 + R1T(P2- P1) (4) Let ~P R1T (P2 - P1), and OR = R1T R2, then problem (3) becomes: V1 = ORV2 + OP (5) subject to IIVill < D1, IIV2 II < D2, With the above transformations, the intersection problem is reduced to the problem of finding the intersection between a disk K1 lying in the (XO,Yo) plane and centered at the origin Oo of the fixed coordinates frame F0, and a disk K2 of center OP and rotation matrix OR. III. Geometric Transformations Our approach for solving the intersection problem consists first on transforming the equality in (5) to a simpler form. This can be done by using rotation transformations that do not alternate the geometric structure of the problem. For this, we shall show that for any given matrix OR there exist three rotation matrices A, B, and R such that: B RAT = R (6) where A, B, and R are of the forms: Fcos() -sin(c) 0 cos(c) -sin(O) 0c0 A= sin(a) cos(a) 0 B B= sin(p) cos(P) 0 [ R= 0 cos(y) -sin(y) 0 0 1 0 0 1 0 sin(y) cos(y) For this, let C be a 3 x 3 rotation matrix such that C = OR AT. Post multiply OR by AT and set the entry C31 to zero, we obtain: C31 = OR31 cos(a) - OR31 sin(a) = 0 where ac can be computed as follows: tan (ac) = OR31 2 a = atan (R31) (7) 4

The value of a is not unique, but since the disks are assumed to have two identical sides, the solutions a + 7x and a - nc correspond to the same plane of the disk. Therefore, we can restrict a to be in [0, Ot] by checking the signs of OR31 and OR31. Note that, if OR32 = 0, then we can permute column 1 and 2 of OR so that the entry C31 = 0. In this case, the permutation matrix is obtained by setting a = - /2 in A. Thus, the resulting matrix C is of the form: - Cll C12 C13 - C= C21 C22 C23 - 0 C32 C33 Let D be a 3 x 3 rotation matrix such that D = B C. Post multiply C by B and set the entry D21 to zero, we obtain: D21 = C 1 sin(p) + C21 cos(3) = 0 which implies that: tan (() C1 =atan(C1) (8),11 C11 Similarly, the solutions P + c and 3 - nt provide the same plane for the disk. Therefore, we can determine 3 in [0, nt] by checking the signs of C1 i and C21. If C1 i = 0, then we can permute rows 1 and 2 of C so that the entry D21 = 0. The resulting matrix D is of the form: - D11 D12 D13D= 0 D22 D23 - 0 D32 D33 Since D is an orthonormal matrix, then D11 must be equal to 1 or -1, and D12 = D13 = 0. If D11 = -1, then we can pre multiply D by a matrix Ii such that R = Ii D, where I1 is of the form: -1 0 011= 0 1 0 0 0 1 In this case, we have R11 = 1. Since D is a rotation matrix and D11 = 1, then D22 = D33, and D23 = -D32. Therefore, by setting D22 = cos(y) and D23 = -sin(y), the matrix R will be of the form: 1 0 0 R= O cos(y) -sin(y) (9) 0 sin(y) cos(y) I 5

where R = D, if D11= 1, or R = I1 D, if D11 = -1, and y is uniquely determined by D22 and D23. The above transformations show that for a given matrix OR, we can find a matrix R such that R is a rotation matrix about the Xo-axis of disk K2. Consider now the equality V1 = OR V2 + ~P. Pre multiply this equality by B and post multiply OR by ATA, we obtain: BV1 = BORATAV2 + BOP Let M1 = B V1, M2 = A V2, and P = B ~P, and substitute R for B OR AT in the above equation, we have: M1 = RM2 + P where: M1 = (rl cos(ql+ P), rl sin(ql+ P), 0)T, M2 = (r2 cos(q2+ o), r2 sin(q2+ a), O)T, and P = (PX, Py, Pz)T. Replacing ql+ P by 01 in M1, and q2+ o by 02 in M2, we have: M1 = (ri cos(01), rl sin(01), o)T, 01 = qi+ = (x1, y, O)T (10) M2 = (r2 cos(02), r2 sin(02), O)T, 02 = q2+ C = (x2, y2, O)T Finally, the disk intersection problem (5) is reduced to the following form: M1 = RM2 + P (11) subject to IIM111 < D1, IIM2 II < D2, Expanding (11) in terms of the coordinates of M1, M2, and P, we have: x1 = x2 + Px Y1 = cos(y) Y2 + Py 0 = sin(y) y2 + Pz (12) subject to: (xi)2 + (yl)2 < (D1)2 (x2)2 + (y2)2 < (D2)2 The above transformations, have reduced the problem of computing the intersection between two arbitrary disks in 3D, to a problem where disk K1 is centered at the fixed origin, and disk K2 is centered at a point P, and whose plane is rotated by an angle y about the Xo-axis of the fixed coordinates frame Fo. Finally, it is clear that these transformations preserve the geometric structure of the intersection problem. 6

IV. Intersection Computation Algorithm In this section, we give the algorithm for solving (12): Case 1: If sin(y) = 0, which means that the planes of disks K1 and K2 are parallel. Then the intersection depends on the value of Pz. Case 1.1: If Pz 0, then there is no intersection between K1 and K2. Case 1.2: If Pz = 0, then the intersection depends on the values of Px and Py. Case 1.2.1: If Px = Py = 0. In this case the disks are centered at the origin. The following cases should be examined for the intersection: Case 1.2.1.1: If D1 > D2, then K2 is contained in K1, and the intersection is the set of all points of K2. Case 1.2.1.2: If D1 = D2, then K1 and K2 are identical, and the intersection is the set of all points of K1 or K2. Case 1.2.1.3: If D1 < D2, then K1 is contained in K2, and the intersection is the set of all points of K1. Case 1.2.2: If Px ~ 0 or Py 0, then the intersection can be checked as follows: Case 1.2.2.1: If x(Px)2 + (py)2 > D1 + D2, then there is no intersection between K1 and K2. Case 1.2.2.2: If (Px)2 + (y)2 = D1 + D2, then the intersection is reduced to a unique point given by: D DPx D1 DP xl = D+ D2 l D +D2 - D2 Px -1 D2 Py X2 D+D2 2- cos(y) Dl+D2 where cos(y) = + 1, depending on whether y= 0 or. Case 1.2.2.3: If (Px)2 + (py)2 < D1 + D2, then the following cases should be considered: Case 1.2.2.3.1: If (Px)2 + (py)2 + D2 < D1, then the set of intersecting points is disk K2, since K2 is contained in K1. Case 1.2.2.3.2: If /(Px)2 + (py)2 + D1 < D2, then the set of intersecting points is disk K1, since K1 is contained in K2. Case 1.2.2.3.3: If non of cases (1.2.2.3.1) and (1.2.2.3.2) is valid, then the disks have some overlapping area. In particular, the point M1 on the border of K1 satisfying the following coordinates: 7

= D1 Px, Di Py I(px)2+ (y2 (Px)2 + (py)2 is an intersection point. Substituting xl and yi in (12), we obtain the following coordinates for M2: D1 Px I DI P x2 - =- Py x2 (P2+ (py)2 cos(y) (Px)2 + (Py)2 Case 2: If sin y 0, then we should have for the intersection: P, cos y Y2 =- - and yi - os Pz + P sin y sin y We now use Lemma 1, which states that if K1 and K2 have a non-empty intersection, then one of the intersecting points must be on the border of K1 or K2. The following cases should be studied: Case 2.1: Assume (xl)2 + (yl)2 = D12. Case 2.1.1: If D12 < (yl)2, then the disks have no intersection, since (xl)2 + (yl)2 = D12 has no real solutions. Case 2.1.2: If D12 > (y )2, then the coordinates of M1 are: x!=+f / D-F — cosy 2 cos y Py XI =~+ s|DI2 -[ - Pz+ Py i Pz + Py sin y sin y Using (12), the coordinates of M2 are: Pz X2 = xl-Px Y2 sin y Case 2.1.2.1: If (x2)2 + (y2)2 < D22, then the above points verify the intersection. Case 2.1.2.2: If (x2)2 + (y2)2 > D22, then the disks have no intersection. If Case 2.1 does not hold, then we have to check whether M2 is on the border of K2. This is done in the same way as in Case 2.1, that is: Case 2.2: Assume (x2)2 + (y2)2 = D22. Case 2.2.1: If D22 < (y2)2, then the disks have no intersection, since (x2)2 + (y2)2 = D22 has no real solutions. Case 2.2.2: If D22 > (y2)2, then the coordinates of M2 are: x2_ + /D22_r[PzI2 Pz X2+ sin yi- sin y Using (12), the coordinates of M1 are: 8

cos y xl =2+Px Yi = — Pz + Py sin y Case 2.2.2.1: If (xl)2 + (yl)2 < D12, then the above points verify the intersection. Case 2.2.2.2: If (xl)2 + (yl)2 > D12, then the disks have no intersection. Finally, if non of Cases 2.1 or 2.2 hold, then the disks have no intersection. Note that the above algorithm provides closed-form solutions for all cases of intersection. The worst case is the case for which sin y = 0, and the disks have or not an overlapping area. In this case, at most 7 comparison tests are required to find the result. If the proposed algorithm terminates by finding the intersection, then one has to reapply the inverse transformations given in Section 3 to compute the exact solutions of the initial problem. In this case, if a solution M1 = (xl, yl, 0)T and M2 = (x2, y2, O)T is found, then the relative coordinates of the original points Vi = (Vlx, Vly, O)T and V2 = (V2x, V2y, 0)T corresponding to M1 and M2 respectively are given by the following transformations: V1=BTM1 and V2 =ATM2 where BT and AT are defined by (6), (7) and (8). V. Conclusion: We presented in this report a geometric algorithm for computing the intersection between two circular disks in three-dimensional space. Several transformations were used to simplify the intersection problem and to provide closed-form solutions with simple expressions. The algorithm requires few tests to locate and compute the intersecting points. However, the implementation of the algorithm could be done without making these transformations. In fact, equations (5) will be enough for developing the algorithm. In this case, we may end up with an algorithm that requires more tests to find the intersection, than the proposed algorithm with transformations. Acknowledgments: The authors would like to thank the Research Committee at King Fahd University of Petroleum and Minerals, for its support to conduct and accomplish this work. Thanks are also extended to the Department of Industrial and Operations Engineering at the University of Michigan, Ann Arbor, where the first author is currently on Sabbatical Leave. 9

REFERENCES: [1] H. G. Mairson and J. Stolfi, "Reporting and counting segment intersections", Stanford Univ., Dept. of Computer Science, CA, 1984. [2] R. H. Gutting, and D. Wood, "Finding rectangle intersection by divide-and conquer", Univ. of Waterloo, Tech. report CS-8303, Ontario, 1983. [3] E. M. McCreight, "Efficient algorithms for enumerating intersecting intervals and rectangles", Xerox Palo Alto Res. Center, Tech. report, PARC CSL-80-5, Palo Alto, CA, 1980. [4] J. L Bentley and D. Wood, "An optimal worst-case algorithm for reporting intersections of rectangles", IEEE Trans. Comupt., Vol. C-29, pp. 571-577, July 1980. [5] W. Meyer, "Distance between boxes: Applications to collision detection and clipping", IEEE Inter. Conf. on Robotics and Automation, pp. 597-602, 1986. [6] J. O'Rourke, C. B. Chien, T. Olson, and D. Naddoe, "A new linear algorithm for intersecting convex polygons", Comput. Graph Image Processing, Vol. 19, pp. 384-391, 1982. [7] H. Edelsbrunner, H. A. Maurer, and D. G. Kirkpatrik, " Polygonal intersection searching", Inform. Processing Lett. Vol. 14, pp. 74-79, 1982. [8] F. Chin and C. A. Wang, "Optimal algorithms for the intersection and minimum distance between planar polygons", IEEE Trans. on Computers, Vol. C32, pp. 1203-1207, 1983. [9] D. E. Muller, and F. P. Preparata, "Finding the intersection of two convex polyhedral", Theoretical Computer Science, Vol. 7, pp. 217-236, 1978. [10] M. E. Dyer, "A simplified O(nlogn) algorithm for the intersection of 3-polyhedral", Middlesbrough, Dept. Math., Tech. Report, TPMR 80-5, 1980. [11] D. P. Dobkin, and D. G. Kirkpatrick, "Fast detection of polyhedral intersection", Theoretical Computer Science, Vol. 27, pp. 241-253, 1983. [12] J. L. Bentley, D. Haken, and R. Hon, "Fast geometric algorithms for VLSI tasks, "in Proc. Comput. Conf. pp. 88-92, 1981. [13] 0. Khatib, "Real-time obstacle avoidance for manipulators and mobile robots", Inter. Jour. on Robotics Research, Vol. 5, No. 1, 1986. [14] S. Cameron, "Efficient intersection tests for objects defined constructively", Inter. Jour. on Robotics Research, Vol. 8, pp. 3-25, 1989. [15] D. T. Lee and F P. Preperata, "Computational geometry - A survey", IEEE Trans. on Computers, Vol. C-33, No. 12, pp. 1072-110, Dec. 1984. [16] J. A. Humel, Vector Geometry, Textbook, Addison-Wesley Publishing Co. Inc., 1965. [17] P. A. White, Vector Analytic Geometry, Textbook, Dickenson Publishing Co. Inc., Belmont, California, 1965. [18] D. G. Luenberger, "Optimization by vector space methods", John Wiley & Sons Inc., 1969. 10

[19] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming, Theory and Algorithms, Second Edition, John Wiley and Sons Inc., 1993. 11