Faster Line Segment Intersection for Unity3D/C#

This method tests whether two lines are intersecting each other. The code is based on the algorithm described by

Faster Line Segment Intersection
Franklin Antonio, Graphics Gems III, 1992, pp. 199-202
ISBN: 0-12-409673-5

The implementation tests only the intersection and will not calculate any possible intersection point.

static bool FasterLineSegmentIntersection(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4) {
 
    Vector2 a = p2 - p1;
    Vector2 b = p3 - p4;
    Vector2 c = p1 - p3;
 
    float alphaNumerator = b.y*c.x - b.x*c.y;
    float alphaDenominator = a.y*b.x - a.x*b.y;
    float betaNumerator  = a.x*c.y - a.y*c.x;
    float betaDenominator  = alphaDenominator; /*2013/07/05, fix by Deniz*/
 
    bool doIntersect = true;
 
    if (alphaDenominator == 0 || betaDenominator == 0) {
        doIntersect = false;
    } else {
 
        if (alphaDenominator > 0) {
            if (alphaNumerator < 0 || alphaNumerator > alphaDenominator) {
                doIntersect = false;
            }
        } else if (alphaNumerator > 0 || alphaNumerator < alphaDenominator) {
            doIntersect = false;
        }
 
        if (doIntersect && betaDenominator > 0) {
            if (betaNumerator < 0 || betaNumerator > betaDenominator) {
                doIntersect = false;
            }
        } else if (betaNumerator > 0 || betaNumerator < betaDenominator) {
            doIntersect = false;
        }
    }
 
    return doIntersect;
}

4 thoughts on “Faster Line Segment Intersection for Unity3D/C#

  1. Deniz Eren

    Here is a way to make your code even faster:
    float alphaNumerator = b.y*c.x – b.x*c.y;
    float alphaDenominator = a.y*b.x – a.x*b.y;
    float betaNumerator = a.x*c.y – a.y*c.x;
    float betaDenominator = alphaDenominator;

    Reply
  2. Bryon

    This can be simplified, faster, and more memory efficient by combining the logic and variables to be:

    Vector2 a = p2 – p1;
    Vector2 b = p3 – p4;
    Vector2 c = p1 – p3;

    float alphaNumerator = b.y*c.x – b.x*c.y;
    float betaNumerator = a.x*c.y – a.y*c.x;
    float denominator = a.y*b.x – a.x*b.y;

    if (denominator == 0)
    {
    return false;
    }
    else
    {
    if (denominator > 0)
    {
    if (alphaNumerator denominator || betaNumerator denominator)
    {
    return false;
    }
    }
    else if (alphaNumerator > 0 || alphaNumerator 0 || betaNumerator < denominator)
    {
    return false;
    }
    }
    return true;

    Reply
    1. EvilBad Post author

      Great, thanks for this optimized version, I agree on the changes to reduce the variables and to speed it up. Please, can you send a plain copy of the code to ? so I can integrate your changes. Unfortunately, WordPress is eating up some characters in the comment text fields.

      Reply

Leave a Reply

Your email address will not be published.

ohXyOP

Please type the text above: