Numerical Robustness - Real-Time Collision Detection - page 458

the terms a / b and c / d compare as follows:

⎧
⎨

, d
c

b
a

Greater than >

, d
c

b
a

order a

d b , c

= Less than <

⎩

order d mod c
c

, b mod a
a

otherwise

Accounting for arbitrary values of a , b , c , and d , the ordering test can be
implemented as follows.

// Compare rational numbers a/b and c/d
int Order(int a, int b, int c, int d)
{

// Make c and d be nonnegative
if(c<0)b=-b,c=-c;
if(d<0)a=-a,d=-d;
// Handle a and/or b being negative
if(a<0&&b<0){
int olda = a, oldb = b;
a=c;b=d;c=-olda; d = -oldb;

}
if (a < 0) return LESS_THAN;
if (b < 0) return GREATER_THAN;

// Make a <= b, exit if order becomes known
if(a>b){
if (c < d) return GREATER_THAN;
int olda = a, oldb = b;
a=d;b=c;c=oldb; d = olda;

}
if (c > d) return LESS_THAN;

// Do continued fraction expansion (given that 0<=a<=b, 0<=c<=d)
while (a != 0 && c != 0) {
intm=d/c;
intn=b/a;
if (m != n) {
if (m < n) return LESS_THAN;