How to Compute the Intersection Point of Two Lines

How do I compute the intersection point of two lines?

Unlike other suggestions, this is short and doesn't use external libraries like numpy. (Not that using other libraries is bad...it's nice not need to, especially for such a simple problem.)

def line_intersection(line1, line2):
xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1])

def det(a, b):
return a[0] * b[1] - a[1] * b[0]

div = det(xdiff, ydiff)
if div == 0:
raise Exception('lines do not intersect')

d = (det(*line1), det(*line2))
x = det(d, xdiff) / div
y = det(d, ydiff) / div
return x, y

print line_intersection((A, B), (C, D))

And FYI, I would use tuples instead of lists for your points. E.g.

A = (X, Y)

EDIT: Initially there was a typo. That was fixed Sept 2014 thanks to @zidik.

This is simply the Python transliteration of the following formula, where the lines are (a1, a2) and (b1, b2) and the intersection is p. (If the denominator is zero, the lines have no unique intersection.)

Sample Image

Formula to find intersection point of two lines

Suppose line 1 is defined by [x1, y1] and alpha1 and line 2 by [x2, y2] and alpha2.

Suppose k1 = tan(alpha1) and k2 = tan(alpha2).

Then the formula for the x-coordinate of the intersection is

x = (y2 - y1 + k1 * x1 - k2 * x2) / (k1 - k2)

Note: Function tan is undefined for angles pi / 2 + k * pi (where k is an arbitrary integer), so:

if k1 is undefined, then x = x1 and y = y2 + k2 * (x1 - x2)

if k2 is undefined, then x = x2 and y = y1 + k1 * (x2 - x1)

(both are practically the same with exchange of indices 1 <--> 2).

Identification of the intersection point of two lines

A line which is parallel to the y-axis cannot be expressed as y = ax + b. You need to use the general equation of a line ax + by + c = 0. Determine the coefficients of the equations of your two lines and solve the linear system of their intersection. Make sure the determinant of the system is different from 0, otherwise there is no solution, or an infinity (which you can consider being another case of no solution).

You can obtain a and b coefficients quite easily considering the normal vector of your segment (if vect(AB) = (x,y) then normal(AB) = (-y,x) = (a,b). You then determine c by introducing the coordinates of A in the equation : c = -a*x_A - b*y_A.

You now have a linear system to solve :

(S) : { a1*x + b1*y + c1 = 0    
{ a2*x + b2*y + c2 = 0

If det = a1*b2 - a2*b1 = 0 (be careful with loss of precision, make your comparison epsilon-wise), then the system has no unic solution. Otherwise, you can find the inverse of the matrix of the system :

M = (a1  b1), M^(-1) = 1/det * ( b2  -b1) 
(a2 b2) (-a2 a1)

Now you just need to compute

M^(-1) * (-c1) = 1/det * (-b2*c1 + b1*c2)
(-c2) ( a2*c1 - a1*c2)

And that's it, you have your solution !

calculating the point of intersection of two lines

You don't need to alternate between adding/subtracting y-intersects when plugging 'found-x' back into one of the equations:

(function () {
window.linear = {
slope: function (x1, y1, x2, y2) {
if (x1 == x2) return false;
return (y1 - y2) / (x1 - x2);
},
yInt: function (x1, y1, x2, y2) {
if (x1 === x2) return y1 === 0 ? 0 : false;
if (y1 === y2) return y1;
return y1 - this.slope(x1, y1, x2, y2) * x1 ;
},
getXInt: function (x1, y1, x2, y2) {
var slope;
if (y1 === y2) return x1 == 0 ? 0 : false;
if (x1 === x2) return x1;
return (-1 * ((slope = this.slope(x1, y1, x2, y2)) * x1 - y1)) / slope;
},
getIntersection: function (x11, y11, x12, y12, x21, y21, x22, y22) {
var slope1, slope2, yint1, yint2, intx, inty;
if (x11 == x21 && y11 == y21) return [x11, y11];
if (x12 == x22 && y12 == y22) return [x12, y22];

slope1 = this.slope(x11, y11, x12, y12);
slope2 = this.slope(x21, y21, x22, y22);
if (slope1 === slope2) return false;

yint1 = this.yInt(x11, y11, x12, y12);
yint2 = this.yInt(x21, y21, x22, y22);
if (yint1 === yint2) return yint1 === false ? false : [0, yint1];

if (slope1 === false) return [y21, slope2 * y21 + yint2];
if (slope2 === false) return [y11, slope1 * y11 + yint1];
intx = (slope1 * x11 + yint1 - yint2)/ slope2;
return [intx, slope1 * intx + yint1];
}
}
}());

Need to find the intersection point of two line segments iterated over multiple segments

Since you haven't provided any sample input and expected output, I'm going to use the dummy version of the line_intersection() function shown below. All it does is print its input and returns a hardcoded result — but it will show you how to iterate through the input data and pass it to the real function.

It should be clear from the output what it's doing.

def line_intersection(line1, line2):
print('intersecting:')
print(' ({}. {}), ({}, {})'.format(line1[0][0], line1[0][1],
line1[1][0], line1[1][1]))
print(' ({}. {}), ({}, {})'.format(line2[0][0], line2[0][1],
line2[1][0], line2[1][1]))
print('')
return 100, 200

All the looping has been put in a generator function named find_intersections() which returns successive intersections it finds, skipping any combinations that don't.

def find_intersections(continuous_line, crossing_lines):
for cl_segment in continuous_line:
for xl_segment in crossing_lines:
try:
x, y = line_intersection(cl_segment, xl_segment)
except Exception:
pass
else:
yield x, y

Here's a usage example with made-up input data:

continuous_line = [((1,2),(3,4)), ((5,6),(7,8)), ((9,10),(11,12))]
crossing_lines = [((21,22),(23,24)), ((25,26),(27,28)), ((29,30),(31,32))]
intersections = [(x, y) for x, y in
find_intersections(continuous_line, crossing_lines)]
print('intersections found:')
print(intersections)

Output:

intersecting:
(1. 2), (3, 4)
(21. 22), (23, 24)

intersecting:
(1. 2), (3, 4)
(25. 26), (27, 28)

intersecting:
(1. 2), (3, 4)
(29. 30), (31, 32)

intersecting:
(5. 6), (7, 8)
(21. 22), (23, 24)

intersecting:
(5. 6), (7, 8)
(25. 26), (27, 28)

intersecting:
(5. 6), (7, 8)
(29. 30), (31, 32)

intersecting:
(9. 10), (11, 12)
(21. 22), (23, 24)

intersecting:
(9. 10), (11, 12)
(25. 26), (27, 28)

intersecting:
(9. 10), (11, 12)
(29. 30), (31, 32)

intersections found:
[(100, 200), (100, 200), (100, 200), (100, 200), (100, 200), (100, 200), (100,
200), (100, 200), (100, 200)]

find intersection point of two lines drawn using houghlines opencv

You don't want to get the intersections of the parallel lines; only the intersections of the vertical lines with those of the horizontal lines. Also, since you have vertical lines, calculating the slope will likely result in exploding or inf slopes, so you shouldn't use the y = mx+b equations. You need to do two things:

  1. Segment your lines into two classes based on their angle.
  2. Calculate the intersections of each line in one class to the lines in the other classes.

With HoughLines, you already have the result as rho, theta so you can easily segment into two classes of angle with theta. You can use for e.g. cv2.kmeans() with theta as your data you want to split.

Then, to calculate the intersections, you can use the formula for calculating intersections given two points from each line. You are already calculating two points from each line: (x1, y1), (x2, y2) so you can simply just store those and use them. Edit: Actually, as seen below in my code, there's a formula you can use for calculating the intersections of lines with the rho, theta form that HoughLines gives.

I have answered a similar question before with some python code that you can check out; note this was using HoughLinesP which gives you only line segments.



Code example

You didn't provide your original image so I can't use that. Instead I'll use the standard sudoku image used by OpenCV on their Hough transform and thresholding tutorials:

Sudoku image

First, we'll just read this image and binarize it using adaptive thresholding like what's used in this OpenCV tutorial:

import cv2
import numpy as np

img = cv2.imread('sudoku.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
blur = cv2.medianBlur(gray, 5)
adapt_type = cv2.ADAPTIVE_THRESH_GAUSSIAN_C
thresh_type = cv2.THRESH_BINARY_INV
bin_img = cv2.adaptiveThreshold(blur, 255, adapt_type, thresh_type, 11, 2)

Sudoku image binarized

Then we'll find the Hough lines with cv2.HoughLines():

rho, theta, thresh = 2, np.pi/180, 400
lines = cv2.HoughLines(bin_img, rho, theta, thresh)

Sudoku image with Hough lines

Now, if we want to find the intersections, really we want to find the intersections only of the perpendicular lines. We don't want the intersections of mostly parallel lines. So we need to segment our lines. In this particular example you could easily just check whether the line is horizontal or vertical based on a simple test; the vertical lines will have a theta of around 0 or around 180; the horizontal lines will have a theta of around 90. However, if you want to segment them based on an arbitrary number of angles, automatically, without you defining those angles, I think the best idea is to use cv2.kmeans().

There is one tricky thing to get right. HoughLines returns lines in rho, theta form (Hesse normal form), and the theta returned is between 0 and 180 degrees, and lines around 180 and 0 degrees are similar (they are both close to horizontal lines), so we need some way to get this periodicity in kmeans.

If we plot the angle on the unit circle, but multiply the angle by two, then the angles originally around 180 degrees will become close to 360 degrees and thus will have x, y values on the unit circle near the same for angles at 0. So we can get some nice "closeness" here by plotting 2*angle with the coordinates on the unit circle. Then we can run cv2.kmeans() on those points, and segment automatically with however many pieces we want.

So let's build a function to do the segmentation:

from collections import defaultdict
def segment_by_angle_kmeans(lines, k=2, **kwargs):
"""Groups lines based on angle with k-means.

Uses k-means on the coordinates of the angle on the unit circle
to segment `k` angles inside `lines`.
"""

# Define criteria = (type, max_iter, epsilon)
default_criteria_type = cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER
criteria = kwargs.get('criteria', (default_criteria_type, 10, 1.0))
flags = kwargs.get('flags', cv2.KMEANS_RANDOM_CENTERS)
attempts = kwargs.get('attempts', 10)

# returns angles in [0, pi] in radians
angles = np.array([line[0][1] for line in lines])
# multiply the angles by two and find coordinates of that angle
pts = np.array([[np.cos(2*angle), np.sin(2*angle)]
for angle in angles], dtype=np.float32)

# run kmeans on the coords
labels, centers = cv2.kmeans(pts, k, None, criteria, attempts, flags)[1:]
labels = labels.reshape(-1) # transpose to row vec

# segment lines based on their kmeans label
segmented = defaultdict(list)
for i, line in enumerate(lines):
segmented[labels[i]].append(line)
segmented = list(segmented.values())
return segmented

Now to use it, we can simply call:

segmented = segment_by_angle_kmeans(lines)

What's nice is here we can specify an arbitrary number of groups by specifying the optional argument k (by default, k = 2 so I didn't specify it here).

If we plot the lines from each group with a different color:

Segmented lines

And now all that's left is to find the intersections of each line in the first group with the intersection of each line in the second group. Since the lines are in Hesse normal form, there's a nice linear algebra formula for calculating the intersection of lines from this form. See here. Let's create two functions here; one that finds the intersection of just two lines, and one function that loops through all the lines in the groups and uses that simpler function for two lines:

def intersection(line1, line2):
"""Finds the intersection of two lines given in Hesse normal form.

Returns closest integer pixel locations.
See https://stackoverflow.com/a/383527/5087436
"""
rho1, theta1 = line1[0]
rho2, theta2 = line2[0]
A = np.array([
[np.cos(theta1), np.sin(theta1)],
[np.cos(theta2), np.sin(theta2)]
])
b = np.array([[rho1], [rho2]])
x0, y0 = np.linalg.solve(A, b)
x0, y0 = int(np.round(x0)), int(np.round(y0))
return [[x0, y0]]

def segmented_intersections(lines):
"""Finds the intersections between groups of lines."""

intersections = []
for i, group in enumerate(lines[:-1]):
for next_group in lines[i+1:]:
for line1 in group:
for line2 in next_group:
intersections.append(intersection(line1, line2))

return intersections

Then to use it, it's simply:

intersections = segmented_intersections(segmented)

And plotting all the intersections, we get:

Intersections


As mentioned above, this code can segment lines into more than two groups of angles as well. Here's it running on a hand drawn triangle, and calculating the intersection points of the detected lines with k=3:

Triangle intersections



Related Topics



Leave a reply



Submit