Most common way to compute line line intersection C++?

Question

Seems there is no way to compute line line intersection using boost::geometry, but I wonder what is the most common way to do it in C++?

I need intersection algorithms for two infinite lines in 2D, if it will be faster it can be two different functions like:

bool line_intersection(line,line);
point line_intersetion(line,line);

P.S. I really try to avoid a wheel invention, so incline to use some library.

Answer 1

To solve this problem, I pieced together the following function, but unexpectedly found that it cannot calculate the intersection of line segments, but the intersection of lines.

class Solution {
    typedef complex<double> point;
#define x real()
#define y imag()

    struct LinePara
    {
        double k;
        double b;
    };
    LinePara getLinePara(float x1, float y1, float x2, float y2)
    {
        LinePara ret;
        double m = x2 - x1;
        if (m == 0)
        {
            ret.k = 1000.0;
            ret.b = y1 - ret.k * x1;
        }
        else
        {
            ret.k = (y2 - y1) / (x2 - x1);
            ret.b = y1 - ret.k * x1;
        }
        return ret;
    }

    struct line {
        double a, b, c;
    };
    const double EPS = 1e-6;
    double det(double a, double b, double c, double d) {
        return a * d - b * c;
    }
    line convertLineParaToLine(LinePara s)
    {
        return line{ s.k,-1,s.b };
    }
    bool intersect(line m, line n, point& res) {
        double zn = det(m.a, m.b, n.a, n.b);
        if (abs(zn) < EPS)
            return false;
        res.real(-det(m.c, m.b, n.c, n.b) / zn);
        res.imag(-det(m.a, m.c, n.a, n.c) / zn);
        return true;
    }
    bool parallel(line m, line n) {
        return abs(det(m.a, m.b, n.a, n.b)) < EPS;
    }
    bool equivalent(line m, line n) {
        return abs(det(m.a, m.b, n.a, n.b)) < EPS
            && abs(det(m.a, m.c, n.a, n.c)) < EPS
            && abs(det(m.b, m.c, n.b, n.c)) < EPS;
    }
    vector<double> mian(vector<vector<double>> line1, vector<vector<double>> line2)
    {
        vector<point> points;
        points.push_back(point(line1[0][0], line1[0][1]));
        points.push_back(point(line1[1][0], line1[1][1]));
        points.push_back(point(line2[0][0], line2[0][1]));
        points.push_back(point(line2[1][0], line2[1][1]));

        line li1 = convertLineParaToLine(getLinePara(line1[0][0], line1[0][1], line1[1][0], line1[1][1]));
        line li2 = convertLineParaToLine(getLinePara(line2[0][0], line2[0][1], line2[1][0], line2[1][1]));
        point pos;
        if (intersect(li1, li2, pos))
        {
            return{ pos.x ,pos.y };
        }
        else
        {
            if (equivalent(li1, li2)) {
                if (points[1].x < points[2].x)
                {
                    return vector<double>{ points[1].x, points[1].y };
                }
                else if (points[1].x > points[2].x)
                {
                    return vector<double>{ points[2].x, points[2].y };
                }
                else if (points[1].x == points[2].x)
                {
                    if (points[1].y < points[2].y)
                    {
                        return vector<double>{ points[1].x, points[1].y };
                    }
                    else if (points[1].y > points[2].y)
                    {
                        return vector<double>{ points[2].x, points[2].y };
                    }
                }
                else
                {
                    return vector<double>{ points[2].x, points[2].y };
                }
            }
            else
            {
                return {}/* << "平行！"*/;
            }
            return {};
        }
    }
public:
    vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
        vector<vector<double>> line1{ {(double)start1[0],(double)start1[1]},{(double)end1[0],(double)end1[1] } };
        vector<vector<double>> line2{ {(double)start2[0],(double)start2[1]},{(double)end2[0],(double)end2[1] } };
        return mian(line1, line2);
    }
};

From there

Answer 2

You can try my code, I'm using boost::geometry and I put a small test case in the main function.

I define a class Line with two points as attributes.

Cross product is very a simple way to know if two lines intersect. In 2D, you can compute the perp dot product (see perp function) that is a projection of cross product on the normal vector of 2D plane. To compute it, you need to get a direction vector of each line (see getVector method).

In 2D, you can get the intersection point of two lines using perp dot product and parametric equation of line. I found an explanation here.

The intersect function returns a boolean to check if two lines intersect. If they intersect, it computes the intersection point by reference.

#include <cmath>
#include <iostream>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

namespace bg = boost::geometry;

// Define two types Point and Vector for a better understanding
// (even if they derive from the same class)
typedef bg::model::d2::point_xy<double> Point;
typedef bg::model::d2::point_xy<double> Vector;

// Class to define a line with two points
class Line
{
  public:
    Line(const Point& point1,const Point& point2): p1(point1), p2(point2) {}
    ~Line() {}

    // Extract a direction vector
    Vector getVector() const 
    {
      Vector v(p2);
      bg::subtract_point(v,p1);
      return v;
    }

    Point p1;
    Point p2;
};

// Compute the perp dot product of vectors v1 and v2
double perp(const Vector& v1, const Vector& v2)
{
  return bg::get<0>(v1)*bg::get<1>(v2)-bg::get<1>(v1)*bg::get<0>(v2);
}

// Check if lines l1 and l2 intersect
// Provide intersection point by reference if true
bool intersect(const Line& l1, const Line& l2, Point& inter)
{
  Vector v1 = l1.getVector();
  Vector v2 = l2.getVector();

  if(std::abs(perp(v1,v2))>0.)
  {
    // Use parametric equation of lines to find intersection point
    Line l(l1.p1,l2.p1);
    Vector v = l.getVector();
    double t = perp(v,v2)/perp(v1,v2);
    inter = v1;
    bg::multiply_value(inter,t);
    bg::add_point(inter,l.p1);
    return true;
  }
  else return false;
}

int main(int argc, char** argv)
{
  Point p1(0.,0.);
  Point p2(1.,0.);
  Point p3(0.,1.);
  Point p4(0.,2.);
  Line l1(p1,p2);
  Line l2(p3,p4);

  Point inter;
  if( intersect(l1,l2,inter) )
  {
    std::cout<<"Coordinates of intersection: "<<inter.x()<<" "<<inter.y()<<std::endl;
  }

  return 0;
}

EDIT: more detail on cross product and perp dot product + delete tol argument (off topic)

Answer 3

Perhaps a common way is to approximate the infinity? From my library using boost::geometry:

// prev and next are segments and RAY_LENGTH is a very large constant
// create 'lines'
auto prev_extended = extendSeg(prev, -RAY_LENGTH, RAY_LENGTH);
auto next_extended = extendSeg(next, -RAY_LENGTH, RAY_LENGTH);
// intersect!
Points_t isection_howmany;
bg::intersection(prev_extended, next_extended, isection_howmany);

then you could test whether the 'lines' intersect like this:

if (isection_howmany.empty())
    cout << "parallel";
else if (isection_howmany.size() == 2)
    cout << "collinear";

extendSeg() simply extends the segment in both directions by the given amounts.

---

Also bear in mind - to support an infinite line arithmetic the point type should also support an infinite value. However here the assumption is that you are looking for a numerical solution!

Answer 4

Express one of the lines in parametric form and the other in implicit form:

X = X0 + t (X1 - X0), Y= Y0 + t (Y1 - Y0)

S(X, Y) = (X - X2) (Y3 - Y2) - (Y - Y2) (X3 - X2) = 0

By linearity of the relations, you have

S(X, Y) = S(X0, Y0) + t (S(X1, Y1) - S(X0, Y0)) = S0 + t (S1 - S0) = 0

From this you get t, and from t the coordinates of the intersection.

It takes a total of 15 adds, 6 multiplies and a single divide.

Degeneracy is indicated by S1 == S0, meaning that the lines are parallel. In practice, the coordinates may not be exact because of truncation errors or others, so that test for equality to 0 can fail. A workaround is to consider the test

|S0 - S1| <= µ |S0|

for small µ.

Answer 5

The best algorithms that I've found for finding the intersection of lines are in: Real Time Collision Detection by Christer Ericson, a copy of the book can be found here.

Chapter 5 from page 146 onwards describes how to find the closest point of 3D lines which is also the crossing point of 2D lines... with example code in C.

Note: beware of parallel lines, they can cause divide by zero errors.

Answer 6

This code should work for you. You may be able to optimize it a bit:

template <class Tpoint>
    Tpoint line<Tpoint>::intersect(const line& other) const{
        Tpoint x = other.first - first;
        Tpoint d1 = second - first;
        Tpoint d2 = other.second - other.first;

        auto cross = d1.x*d2.y - d1.y*d2.x;

        auto t1 = (x.x * d2.y - x.y * d2.x) / static_cast<float>(cross);
        return first + d1 * t1;

    }