• Advertisement
  • 07/16/99 05:58 PM
    Sign in to follow this  

    Fast 2D Line Intersection Algorithm

    Math and Physics

    Perhaps something like this may help. Though it may not be fast enough

    void Intersect_Lines(float x0,float y0,float x1,float y1,
    float x2,float y2,float x3,float y3,
    float *xi,float *yi)
    // this function computes the intersection of the sent lines
    // and returns the intersection point, note that the function assumes
    // the lines intersect. the function can handle vertical as well
    // as horizontal lines. note the function isn't very clever, it simply
    //applies the math, but we don't need speed since this is a
    //pre-processing step

    float a1,b1,c1, // constants of linear equations
    det_inv, // the inverse of the determinant of the coefficient
    m1,m2; // the slopes of each line

    // compute slopes, note the cludge for infinity, however, this will
    // be close enough

    if ((x1-x0)!=0)
    m1 = (y1-y0)/(x1-x0);
    m1 = (float)1e+10; // close enough to infinity

    if ((x3-x2)!=0)
    m2 = (y3-y2)/(x3-x2);
    m2 = (float)1e+10; // close enough to infinity

    // compute constants

    a1 = m1;
    a2 = m2;

    b1 = -1;
    b2 = -1;

    c1 = (y0-m1*x0);
    c2 = (y2-m2*x2);

    // compute the inverse of the determinate

    det_inv = 1/(a1*b2 - a2*b1);

    // use Kramers rule to compute xi and yi

    *xi=((b1*c2 - b2*c1)*det_inv);
    *yi=((a2*c1 - a1*c2)*det_inv);

    } // end Intersect_Lines


      Report Article
    Sign in to follow this  

    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now


    Share this review

    Link to review

  • Advertisement