Any way to avoid or allow division by zero in this line intersection algorithm?

Question

I wrote an algorithm to find the intersection between two line segments some time ago. Coming back to look at it though, I noticed that division by zero is possible in two different places. It's okay if it does this, from a logical perspective I think, but of course the program crashes if it does so. This is the algorithm:

class Segment{
    public:

    Vector first, second;


    bool getIntersection(const Segment arg, Vector * intersect = NULL)const{
        Segment segment(b - a, arg.b - arg.a);
        double s, t;

        // These two equations run the risk of division by zero
        s = (-segment.a.y * (a.x - arg.a.x) + segment.a.x * (a.y - arg.a.y)) 
             / (-segment.b.x * segment.a.y + segment.a.x * segment.b.y);
        t = ( segment.b.x * (a.y - arg.a.y) - segment.b.y * (a.x - arg.a.x)) 
             / (-segment.b.x * segment.a.y + segment.a.x * segment.b.y);

        if (s > 0.0 && s < 1.0 && t > 0.0 && t < 1.0)
        {
            // Collision detected
            if (intersect != NULL)
            {
                intersect->x = a.x + (t * segment.a.x);
                intersect->y = a.y + (t * segment.a.y);
            }
            return true;
        }
        return false; // No collision
    }

};

Division by zero is possible where s and t are calculated, if the values behind the divisor are (and may likely turn out to be) all zero. From a geometry perspective, this means the two lines are parallel to each other; parallel lines should never be considered intersecting in this case, even if they overlap perfectly.

Is there a way to allow this function to divide by zero? Assuming of course, that it would not affect the logic behind the algorithm (anything with NANs or INFs will not result in a collision I think)? Or is there a better line segment intersection algorithm I should be using instead?

Calculate the divisor separately and even store it as a separate variable. Check if it's 0, and take appropriate action. Since it is the same for both `s` and `t`, you only need to do this once. — Code-Apprentice, Apr 07 '13 at 18:49
@Code-Guru I feel silly for not even considering that... thanks! — Anne Quinn, Apr 07 '13 at 18:51

score 2 · Accepted Answer · answered Apr 08 '13 at 08:04

I would recommend to compute the two numerators and the denominator separately:

double num1 = (-segment.a.y * (a.x - arg.a.x) + segment.a.x * (a.y - arg.a.y));
double num2 = ( segment.b.x * (a.y - arg.a.y) - segment.b.y * (a.x - arg.a.x));
double denom = (-segment.b.x * segment.a.y + segment.a.x * segment.b.y);

then normalize the denominator to be non-negative:

if (denom < 0) { denom = -denom; num1 = -num1; num2 = -num2; }

and finally check

if (0.0 < num1 && num1 < denom && 0.0 < num2 && num2 < denom) {
    double t = num2 / denom;
    ...
}

This catches not only the "denominator is zero" problem, but avoids also possible overflow problems if the denominator is very small.

score 1 · Answer 2 · edited May 23 '17 at 10:25

1

If you want to do it programmatically it will be a little difficult, as C++ does not support a divide_by_zero-exception or anything similar.

According to this thread here, it is a hardware-error that is detected and returned to the process by the OS.

QUOTE:

It's not an exception. It's an error which is determined at hardware level and is returned back to the operating system, which then notifies your program in some OS-specific way about it (like, by killing the process).

You could catch it via signal-handlers. A Division by Zero will create a SIGFPE. But this might not be very useful or reliable.

edited May 23 '17 at 10:25

Community

1
1

answered Apr 07 '13 at 18:54

bash.d

13,029
3
29
42

1

Or you could just use an if statement. – Code-Apprentice Apr 07 '13 at 19:09
Yes sure, of course you can. Would make sense in this case, also. – bash.d Apr 07 '13 at 19:10

Any way to avoid or allow division by zero in this line intersection algorithm?

2 Answers2