Calculate whether a point exists on a line

[motorollin]

Given the coordinates x50,y50 and x100,y100, is there an equation which can determine whether another point exists along the "line" between the first two? Or better yet whether it is a certain distance from the line?

--
moto

[Cymric]

motorollin wrote:
Given the coordinates x50,y50 and x100,y100, is there an equation which can determine whether another point exists along the "line" between the first two? Or better yet whether it is a certain distance from the line?

Of course. I'll assume you're running things in 2D which keeps the maths to a minimum. I'll also be using vector maths.

Assume we have a point A(A_x, A_y) and B(B_x, B_y). You can think of these points as vectors ('arrows') starting at the origin, and ending (with the pointy head) at the coordinates specified by those points. If you want to figure out the equation for line L, it is easiest if you think of that line as being a smooth transition---'morphing'---between vector A (which I'll write as ) and vector B (). There exists a simple equation for any point / vector in between:

= + q * ( - )

Let's take a look at how this works. If q = 0, then is just (obviously). If q = 1, then we must add the arrow to and then subtract again: we're left with , in other words. Basically, this equation starts at and then adds a little to that vector in the direction of . If you make q < 0 then you extend the line beyond point A, and if you make q > 1 then you extend beyond B.

But now you want to calculate something, as your code doesn't know about vector maths. For that, you must take the above equation and write it down for each coordinate---in this case, x and y:

L_x = A_x + q * (B_x - A_x)
L_y = A_y + q * (B_y - A_y)

Note that q is just a number, and not susceptible to x's and y's. Only the arrows / vectors are. That's why you don't write q_x and q_y. These two equations must hold simultaneously for a point to be on L. You now have several ways of checking whether that is the case, and they all work like this:

1. Take the X-coordinate of your point P: P_x.
2. Plug this in the X-half of the above set of equations, yielding

P_x = A_x + q * (B_x - A_x)

3. Solve for q:

q = (P_x - A_x) / (B_x - A_x)

4. Now you have a value for q. If you plug that into the Y-half of the above set of equations, the result L_y must be equal to P_y. If it is not, then the point P does not lie on line L.

Unfortunately, while the above is mathematically completely correct, in practice it can yield erroneous results because the equations are susceptible to roundoff errors. You are multiplying, adding, dividing floating point numbers, and along the line, tiny roundoffs are made. An exact comparison of the original P_y and and calculated P_y might differ by 1 part in a lot---and is sufficient cause for the computer to flag them as 'not equal'. There is not a lot you can do about this, save for attempting to come up with routines which do not do straight comparisons between floating point numbers. This is part of a field known as computational geometry, and a lot of time and effort is put into minimising these errors. It would take me way too far to explain how these things work. (And that assumes that I know exactly how they work, which I don't :-).) If you're really interested, look here for libraries which you can link to your code. Don't expect superfast results, though---these routines are made for precision, not speed!

--------------------

On to the second problem: calculating the distance of P to L. This cannot be done without vector math, and I'll just state the result. Or better yet---as it is a complex expression---refer you to the site of Paul Bourke. Paul has a lot of these things already written out for you to abuse for your own nefarious purposes, including ready-to-run source code samples. I'll be happy to explain what goes on in the equations if you're interested; it's quite an elegant technique, really. And unfortunately, yes, as implemented in the example code, you can once again expect roundoff errors to creep up to you when you least expect them.


So why bother writing out the equations like I did? Well, it doesn't really matter then if you're using 2D, 3D or even nD. That's the power of vector algebra.

[motorollin]

Wow, thanks! Now for a stupid question... In the set of calculations 1 - 4, what value do I use for q?

--
moto

[Cymric]

You calculate q, according to eq. 3, based on the X-coordinate of the point you want to check. See it as a challenge-response tactic: first you 'challenge' the line to yield q based on the X-coordinate, then you check the 'response' by plugging in that value of q for the Y-coordinate and comparing the result to the Y-coordinate of your point.

[motorollin]

Excellent - thanks!

--
moto

[Karlos]

From your other thread about scores, if floating point is too much of a performance hit, try fixed point.

Depending on your screen's spatial resolution, you arent likely to encounter extreme gradients (except in the straight vertical/hortizontal cases, which should be handled separately)*

In other words, suppose your screen size was 640x480. The steepest non-vertical gradient you will be able to represent on screen anyway is 480 (ie dy/dx = 480) and the shallowest is 1/640.

You can use a signed 15:16 fixed point format (basically 32-bit signed integer where the lowest 16-bits are assumed to be fractional) which is more than precise enough for any screen based calculation you need to do at that resolution.

*a word of warning. If your line is vertical, the basic gradient is going to be infinite, since dx=0. If you use your basic 2D equation of a line approach as presented, you need to handle pure vertical lines as a special case.