Home » Algorithms » Finding the crossing points of two lines

Finding the crossing points of two lines

This is a task that has come up for me many times when creating algorithms for images analysis. Searching the web will invariably turn up the y = Mx + C solution. This is sub-optimal in two ways. First, it has big problems with vertical lines. As the line tends to vertical then m will tend to infinity. This Is Not Good. Secondly, getting any sort of accuracy is impossible without using floating point or large scaling factors.

The code I was modifying at the time was using the y = Mx + C method. It was fairly complex and had to check for lines that were nearly vertical, and flip the axes. It had bugs. I had this gut feeling that must be a better way to solve this, without all of the messing about with edge cases.

Finally after a bit of Googling I came across the lesser used form for describing lines, C = Ax + By. Having lines described in this slightly different form allows a method to find crossing points that is much more code friendly.

Most image processing algorithms I have created work perfectly fine when pixel coordinates are restricted to integral values, allowing integer maths for the following example.

Take two lines, L1 = x1,y1 to x2,y2 and L2 = x3,y3 to x4,y4.

Calculate the values of A, B and C for each line.

For L1:
A1 = y2 – y1
B1 = x1 – x2
C1 = (A1 * x1) + (B1 * y1)

And similarly for L2:

A2 = y4 – y3
B2 = x3 – x4
C2 = (A2 * x3) + (B2 * y3)

Next, work out the determinant.

D = (A1 * B2) – (A2 * B1)

If D is zero then the lines are parallel and there is no crossing point to be found.

If D is not zero then the coordinates of the crossing point may be found thus:

X = ((B2 * C1) – (B1 * C2)) / D
Y = ((A1 * C2) – (A2 * C1)) / D

The two lines do not have to actually cross for this to work. This makes it a great way to find all of the crossing points relative to a reference line.

Next time I will show you how this technique can allow you to scan a rectangular region that is at an arbitrary angle.

John Wellbelove

John Wellbelove

Director of Aster Consulting Ltd
United Kingdom
I have been involved in technology and computer systems for all of my working life and have amassed considerable knowledge of designing and implementing systems that are both performant and correct. My role normally encompasses the entire project life-cycle, from specification to maintenance phase. Most systems I have worked on have required high speed and deterministic performance, often within a highly constrained platform. I am experienced in designing and adapting algorithms to solutions that are both space and time efficient, avoiding the normal overheads of standard solutions. Acting as a mentor for colleagues has often been a significant, though unofficial, part of my role.

I administer an open source project on Github.
See http://www.etlcpp.com/

Leave a comment

Your email address will not be published. Required fields are marked *