Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

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

    Fast 2D Line Intersection Algorithm

    Math and Physics
       (1 review)

    Myopic Rhino
    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
    a2,b2,c2,
    det_inv, // the inverse of the determinant of the coefficient
    matrix
    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);
    else
    m1 = (float)1e+10; // close enough to infinity

    if ((x3-x2)!=0)
    m2 = (y3-y2)/(x3-x2);
    else
    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

    Scott


      Report Article
    Sign in to follow this  


    User Feedback


    Fantastic for people who needs those "long projectiles" like fast bullets.
    Missing only the line versus rectangle collision!

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

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

    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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!