intersecting lines between 2 objects

Question

I'm trying to calculate where two objects in a picture are pointing at one another. I figured I would use intersecting lines to perform this as the objects can be converted into a straight line. One problem though is I seem to be finding code mostly for finding intersection between infinite lines which is something I don't need.

I found this code from a matlab blog which details how to find intersecting infinite lines.

A = [lineA(1,:) - lineA(2,:); lineB(2,:) - lineB(1,:)]'; 
if rank(A) < 2
    disp('Parallel')
    B = [lineA(1,:) - lineA(2,:); lineA(1,:) - lineB(1,:)]'; 
    if rank(B) < 2
        disp('Collinear')
        if all( (sort(lineA(:,1),'descend')-sort(lineB(:,1))) ...
                .*[-1;1] <= sqrt(eps) )
            tf = true;
        else
            tf = false;
        end
    else
        tf = false;
    end
else
    pq = linsolve(A,(lineB(2,:) - lineA(2,:))');
    tf = all(pq>=-sqrt(eps)) & all(pq<=1+sqrt(eps));
end

I have also located old questions about line + circle intersections which looks closer to what I might need.

However the problem is that I am trying to check for 1 line to intersect with a finite line. The picture represents what I'm trying to draw between. The blue line has a limited length while the red line is infinite and I am trying to determine if they intersect.

It's not clear to me from the diagram what you are trying to accomplish. If you are looking for a line-segment/line-segment intersection algorithm you can find some information [here](https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) and [here](http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/) — jodag, Sep 03 '17 at 15:38
Sorry about that. yes I am looking for an intersection between 2 line segments but with one staying as a segment and the other going infinite. — Hojo.Timberwolf, Sep 03 '17 at 15:40

jodag · Accepted Answer · 2017-09-03T16:39:32.560

It sounds like you already have the ability to determine the point of intersection between two lines (i.e. infinite lines). Once you have that point you can easily check to see if the intersection falls on the line segment.

Lets assume that p0 and p1 are the points defining the endpoints of the linesegment, and px is the intersection point between the two infinite lines. The following condition will check if px is between p0 and p1.

d = dot(px-p0,p1-p0)/sum((p1-p0).^2);
if d >= 0 && d <= 1
    % intersecting
else
    % not intersecting
end

Justification

If we assume the point px falls along the line defined by p0 and p1 then it can be expressed by the following parametric vector equation

px = p0 + (p1 - p0)*d

where d is the scalar parameter. From the formula it should be clear that px is between p0 and p1 if and only if 0 <= d <= 1.

We can solve for d using some linear algebra

% subtract p0 from both sides
(px - p0) = (p1 - p0)*d

% multiply by (p1 - p0)' to make the vectors into scalars
(p1 - p0)'(px - p0) = (p1 - p0)'(p1 - p0)*d

% divide to find d
d = ((p1 - p0)'(px - p0)) / ((p1 - p0)'(p1 - p0))

% express using dot product and l2 norm.
d = dot(p1-p0,px-p0) / norm(p1-p0)^2

intersecting lines between 2 objects

1 Answers1