2

I need to be able to find the intersection between two lines defined by 2 points each. I have 2 functions; one to calculate if there is an intersection between two lines, and on to determine the point of intersection of those lines. Please respond with some possible code for each function.

Code structure so far:

struct Pos
{
    float x;
    float y;
};

struct Line
{
    Pos Pos1;
    Pos Pos2;
};

bool Collide(Line Line1, Line Line2)
{
    return true;// Return if there is an intersection 
}

Pos CollidePoint(Line Line1, Line Line2)
{
    return {0, 0};// return the point of intersection
}

int main()
{
    Line Line1 = { { 10, 20 }, { 20, 20 } };// Define one line

    Line Line2 = { { 5, 30 }, { 15, 15 } };// Define another line

    if (Collide(Line1, Line2))//check if a collision exists
    {
        //Display the point of intersection
        cout << "X:" << CollidePoint(Line1, Line2).x << " Y:" << CollidePoint(Line1, Line2).y << endl;
    }
    else
    {
        //If there is no collision
        cout << "No Collision" << endl;
    }
    return 0;
}

NOTE: The function has to be able to work if one or all the lines are vertical and if the lines are on top of each other. Because of this, the code probably won't work with the form y=m*x+b due to the divide by 0 error with vertical lines.

If there is a better way to do this than using the 2 functions please tell me. I'm open to any solution.

EDIT: The two lines are bounded by the points; they are not infinite.

Conner Tenn
  • 63
  • 3
  • 8
  • 2
    You can get the logic for the functions from [Wikipedia](http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection). If you have trouble converting the logic into code, come back with relevant questions. – R Sahu Jan 26 '15 at 19:21
  • I'm voting to close this question as off-topic because it asks for [Code Review](http://codereview.stackexchange.com/) – πάντα ῥεῖ Jan 26 '15 at 19:24
  • 1
    There are many duplicates and near duplicates, such as: http://stackoverflow.com/q/563198/179910 and http://stackoverflow.com/q/14176776/179910. – Jerry Coffin Jan 26 '15 at 19:24

1 Answers1

3

Calculate an intersection value, which you can pass to a line for an intersection point calculation:

/// A factor suitable to be passed to line \arg a as argument to calculate 
/// the intersection point.
/// \NOTE A value in the range [0, 1] indicates a point between
/// a.p() and a.p() + a.v().
/// \NOTE The result is std::numeric_limits<double>::quiet_NaN() if the
/// lines do not intersect. 
/// \SEE  intersection_point
inline double intersection(const Line2D& a, const Line2D& b) {
    const double Precision = std::sqrt(std::numeric_limits<double>::epsilon());
    double d = a.v().x() * b.v().y() - a.v().y() * b.v().x();
    if(std::abs(d) < Precision) return std::numeric_limits<double>::quiet_NaN();
    else {
        double n = (b.p().x() - a.p().x()) * b.v().y()
                 - (b.p().y() - a.p().y()) * b.v().x();
        return n/d;
    }
}

/// The intersection of two lines.
/// \NOTE The result is a Point2D having the coordinates
///       std::numeric_limits<double>::quiet_NaN() if the lines do not
///       intersect. 
inline Point2D intersection_point(const Line2D& a, const Line2D& b) {
    // Line2D has an operator () (double r) returning p() + r * v()
    return a(intersection(a, b));
}

Note: p() is the origin of the line and v() a vector to the end point = p() + v()