OpenCV 2d line intersection helper function

Question

I was looking for a helper function to calculate the intersection of two lines in OpenCV. I have searched the API Documentation, but couldn't find a useful resource.

Are there basic geometric helper functions for intersection/distance calculations on lines/line segments in OpenCV?

score 44 · Accepted Answer · answered Sep 16 '11 at 17:23

44

There are no function in OpenCV API to calculate lines intersection, but distance is:

cv::Point2f start, end;
double length = cv::norm(end - start);

If you need a piece of code to calculate line intersections then here it is:

// Finds the intersection of two lines, or returns false.
// The lines are defined by (o1, p1) and (o2, p2).
bool intersection(Point2f o1, Point2f p1, Point2f o2, Point2f p2,
                      Point2f &r)
{
    Point2f x = o2 - o1;
    Point2f d1 = p1 - o1;
    Point2f d2 = p2 - o2;

    float cross = d1.x*d2.y - d1.y*d2.x;
    if (abs(cross) < /*EPS*/1e-8)
        return false;

    double t1 = (x.x * d2.y - x.y * d2.x)/cross;
    r = o1 + d1 * t1;
    return true;
}

answered Sep 16 '11 at 17:23

Andrey Kamaev

29,582
6
94
88

Just for clarification. Are the lines in your example defined by two points, or as a point and a direction vector? – tisch Sep 17 '11 at 09:15
They are defined by two points. `d1` and `d2` calculated inside the function are direction vectors. – Andrey Kamaev Sep 17 '11 at 09:30
why `cross` variable is float type (why not double)? and why we use `abs` instead of `fabs` (or maybe it's `std::abs`)? why `EPS` variable is not from numerical limits something like `std::numeric_limits::epsilon()`? – mrgloom Dec 22 '15 at 11:49
3

see also [min_enclosing_triangle.cpp](https://github.com/Itseez/opencv/blob/master/modules/imgproc/src/min_enclosing_triangle.cpp#L1380-L1424) – sturkmen Jan 16 '16 at 19:45
@AndreyKamaev does t1 signifies anything? – arvind.mohan Aug 07 '16 at 08:32
Does this code check for the intersection of line or line segment? – kHarshit Jan 19 '21 at 10:34

Maksym Ganenko · Answer 2 · 2020-10-27T06:18:52.963

There's one cool trick in 2D geometry which I find to be very useful to calculate lines intersection. In order to use this trick we represent each 2D point and each 2D line in homogeneous 3D coordinates.

At first let's talk about 2D points:

Each 2D point (x, y) corresponds to a 3D line that passes through points (0, 0, 0) and (x, y, 1).
So (x, y, 1) and (α•x, α•y, α) and (β•x, β•y, β) correspond to the same point (x, y) in 2D space.
Here's formula to convert 2D point into homogeneous coordinates: (x, y) -> (x, y, 1)
Here's formula to convert homogeneous coordinates into 2D point: (x, y, ω) -> (x / ω, y / ω). If ω is zero that means "point at infinity". It doesn't correspond to any point in 2D space.
In OpenCV you may use convertPointsToHomogeneous() and convertPointsFromHomogeneous()

Now let's talk about 2D lines:

Each 2D line can be represented with three coordinates (a, b, c) which corresponds to 2D line equation: a•x + b•y + c = 0
So (a, b, c) and (ω•a, ω•b, ω•c) correspond to the same 2D line.
Also, (a, b, c) corresponds to (nx, ny, d) where (nx, ny) is unit length normal vector and d is distance from the line to (0, 0)
Also, (nx, ny, d) is (cos φ, sin φ, ρ) where (φ, ρ) are polar coordinates of the line.

There're two interesting formulas that link together points and lines:

Cross product of two distinct points in homogeneous coordinates gives homogeneous line coordinates: (α•x₁, α•y₁, α) ✕ (β•x₂, β•y₂, β) = (a, b, c)
Cross product of two distinct lines in homogeneous coordinates gives homogeneous coordinate of their intersection point: (a₁, b₁, c₁) ✕ (a₂, b₂, c₂) = (x, y, ω). If ω is zero that means lines are parallel (have no single intersection point in Euclidean geometry).
In OpenCV you may use either Mat::cross() or numpy.cross() to get cross product

If you're still here, you've got all you need to find lines given two points and intersection point given two lines.

awesome, distance of point from line is here: https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line — Albert Myšák, Oct 25 '20 at 22:05

score 4 · Answer 3 · edited May 23 '17 at 11:47

An algorithm for finding line intersection is described very well in the post How do you detect where two line segments intersect?

The following is my openCV c++ implementation. It uses the same notation as in above post

bool getIntersectionPoint(Point a1, Point a2, Point b1, Point b2, Point & intPnt){
    Point p = a1;
    Point q = b1;
    Point r(a2-a1);
    Point s(b2-b1);

    if(cross(r,s) == 0) {return false;}

    double t = cross(q-p,s)/cross(r,s);

    intPnt = p + t*r;
    return true;
}

double cross(Point v1,Point v2){
    return v1.x*v2.y - v1.y*v2.x;
}

score 2 · Answer 4 · answered Jan 21 '13 at 02:56

Here is my implementation for EmguCV (C#).

static PointF GetIntersection(LineSegment2D line1, LineSegment2D line2)
{

    double a1 = (line1.P1.Y - line1.P2.Y) / (double)(line1.P1.X - line1.P2.X);
    double b1 = line1.P1.Y - a1 * line1.P1.X;

    double a2 = (line2.P1.Y - line2.P2.Y) / (double)(line2.P1.X - line2.P2.X);
    double b2 = line2.P1.Y - a2 * line2.P1.X;

    if (Math.Abs(a1 - a2) < double.Epsilon)
        throw new InvalidOperationException();

    double x = (b2 - b1) / (a1 - a2);
    double y = a1 * x + b1;
    return new PointF((float)x, (float)y);
}

score 2 · Answer 5 · answered Oct 25 '13 at 16:35

Using homogeneous coordinates makes your life easier:

cv::Mat intersectionPoint(const cv::Mat& line1, const cv::Mat& line2)
{
   // Assume we receive lines as l=(a,b,c)^T
   assert(line1.rows == 3 && line1.cols = 1 
          && line2.rows == 3 && line2.cols == 1);

   // Point is p=(x,y,w)^T
   cv::Mat point = line1.cross(line2);

   // Normalize so it is p'=(x',y',1)^T
   if( point.at<double>(2,0) != 0)
     point = point * (1.0/point.at<double>(2,0));
}

Note that if the third coordinate is 0 the lines are parallel and there is not solution in R² but in P^2, and then the point means a direction in 2D.

What's the shape of `point`? Nothing is returned from this function. — Geoff, Aug 01 '17 at 16:30

score 1 · Answer 6 · answered Jul 30 '13 at 11:57

1

my implementation in Python (using numpy array) with line1 = [[x1, y1],[x2, y2]] & line2 = [[x1, y1],[x2, y2]]

def getIntersection(line1, line2):
    s1 = numpy.array(line1[0])
    e1 = numpy.array(line1[1])

    s2 = numpy.array(line2[0])
    e2 = numpy.array(line2[1])

    a1 = (s1[1] - e1[1]) / (s1[0] - e1[0])
    b1 = s1[1] - (a1 * s1[0])

    a2 = (s2[1] - e2[1]) / (s2[0] - e2[0])
    b2 = s2[1] - (a2 * s2[0])

    if abs(a1 - a2) < sys.float_info.epsilon:
        return False

    x = (b2 - b1) / (a1 - a2)
    y = a1 * x + b1
    return (x, y)

answered Jul 30 '13 at 11:57

afiah

507
5
12

x1, y1 & x2,y2 has to be float like (0.0, 1.0) & (2.0, 1.0) – afiah Jul 30 '13 at 12:01
1

This code doesn't work in the presence of a vertical line, because of the divisions by (si[0] - ei[0]) – Arnaud P Oct 22 '13 at 09:14

OpenCV 2d line intersection helper function

6 Answers6

Linked