Algorithm for Intersection of 2 Lines

Algorithm for intersection of 2 lines?

Assuming you have two lines of the form Ax + By = C, you can find it pretty easily:

float delta = A1 * B2 - A2 * B1;

if (delta == 0) 
    throw new ArgumentException("Lines are parallel");

float x = (B2 * C1 - B1 * C2) / delta;
float y = (A1 * C2 - A2 * C1) / delta;

Pulled from here

Counting the intersection points (lines) of two sets of sequences

Given two number M and N, the lines won't intersect if

• the top M is to the right of the top N, and the bottom M is to the right of the bottom N
• the top M is to the left of the top N, and the bottom M is to the left of the bottom N

In the other two cases:

• left top, right bottom
• right top, left bottom

the lines do intersect.

In the example, 8 is to the left of all 4 numbers on the top row, and to the right of 3 numbers on the bottom, so 8 intersects with three numbers.

5 is to the right of 8 on top, left of 8 on the bottom, giving one intersection. 5 is left of 4 and 1 on top, and right of 4 and 1 on the bottom, giving two more. So 5 intersects with three numbers.

Note that we counted the intersection of 5 and 8 twice. In fact every intersection will be counted twice. If you finish the example, you'll count 14 intersections. Divide by 2 at the end to get the answer.

What is an algorithm to find intersection of two linear equations?

If your input lines are in slope-intercept form, an algorithm is an over-kill as there is a direct formula to calculate their point of intersection. It's given on a Wikipedia page and you can understand it as explained below.

Given the equations of the lines: The x and y coordinates of the
point of intersection of two non-vertical lines can easily be found
using the following substitutions and rearrangements.

Suppose that two lines have the equations y = ax + c and y = bx + d where a
and b are the slopes (gradients) of the lines and where c and d are
the y-intercepts of the lines. At the point where the two lines
intersect (if they do), both y coordinates will be the same, hence the
following equality:

ax + c = bx + d.

We can rearrange this expression in order to extract the
value of x,

ax - bx = d - c, and so,

x = (d-c)/(a-b).

To find the y coordinate, all we need to do is substitute the value of x into > either one of the two line equations. For example, into the first:

y=(a*(d-c)/(a-b))+c.

Hence, the Point of Intersection is {(d-c)/(a-b), (a*(d-c)/(a-b))+c}

Note: If a = b then the two lines are parallel. If c ≠ d as well, the lines
are different and there is no intersection, otherwise the two lines are
identical.

Intersection of two infinite lines specified by points

Following AKX's solution, I have adapted the solution reported in his linked thread into a brief Python snippet:

import numpy as np

# The intersection point of the example below should be (0,0)

# Vertices for the first line
p1_start    = np.asarray([-5,   0])
p1_end      = np.asarray([-3,   0])

# Vertices for the second line
p2_start    = np.asarray([0,    4])
p2_end      = np.asarray([0,    2])

p       = p1_start
r       = (p1_end-p1_start)

q       = p2_start
s       = (p2_end-p2_start)

t       = np.cross(q - p,s)/(np.cross(r,s))

# This is the intersection point
i       = p + t*r

The algorithm to find the point of intersection of two 3D line segment

I found a solution: it's here.

The idea is to make use of vector algebra, to use the dot and cross to simply the question until this stage:

a (V1 X V2) = (P2 - P1) X V2

and calculate the a.

Note that this implementation doesn't need to have any planes or axis as reference.

---

Related Topics