Line intersection

[dacoolest]

if four points are given in a plane (for two lines) what is the best method to find out if lines are intersecting or not? Any tips on building the algorithm would be highly appreciated since I have no clue about where to begin!

[webJose]

The only pair or lines that don't intersect are those with the same slope and different intersect.

[dacoolest]

Thanks for the reply. And I'm sorry that I could not mention that any intersection between given two points should be only considered. Any idea?

[webJose]

Thanks for the reply. And I'm sorry that I could not mention that any intersection between given two points should be only considered. Any idea?

I don't understand that.

The bottom line is very simple: 2 lines will never intersect only if they are parallel to each other. Being parallel means both lines have the same slope. You just need to verify that the intersect is different just to ensure you are talking about 2 different lines, not just one.

[Disch]

webJose's advise will work only if both lines extend to infinity.

If you are looking for intersection between two finite line segments, linear algebra is your friend.

Here's a function I made which does exactly that:

inline double Dot(const Point& a,const Point& b)                        { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b)                    { return (a.y*b.x) - (a.x*b.y); }

bool LineCollision( const Point& A1, const Point& A2,
                    const Point& B1, const Point& B2,
                    double* out = 0                            )
{
    Point a(A2-A1);
    Point b(B2-B1);

    double f = PerpDot(a,b);
    if(!f)      // lines are parallel
        return false;
    
    Point c(B2-A2);
    double aa = PerpDot(a,c);
    double bb = PerpDot(b,c);

    if(f < 0)
    {
        if(aa > 0)     return false;
        if(bb > 0)     return false;
        if(aa < f)     return false;
        if(bb < f)     return false;
    }
    else
    {
        if(aa < 0)     return false;
        if(bb < 0)     return false;
        if(aa > f)     return false;
        if(bb > f)     return false;
    }

    if(out)
        *out = 1.0 - (aa / f);
    return true;
}

'Point' is typedef'd as sf::Vector2<double>. If you aren't using SFML, you can write your own such class. It's just a class with x,y members, and overloaded operators.

LineCollision will return true if the lines intersect. If they do intersect, and if 'out' is provided, 'out' will be set to the point of collision along line B (scaled 0-1). To get the exact point of intersection, you can do this:

Point intersection = ((B2 - B1) * out) + B1;