Ok, here’s a scenario I’m trying to figure out:
How can I detect if a point (x,y) exists on a line between points A (x,y,) and B(x,y)?
I can tell if a point exists in a square, or even a circle, but on a line? This one is getting me, and I can’t help but to think it’s got to be simple. I thought I had it at first, but then when I tried it with diagonal lines my algorithm proved wrong.
Anyone know how to do this?
Basically you can the cross product to calculate the perpendicular distance from the line:
You do not say whether it is integer or float, so I will assume float and work it out to a certain error margin…
boolean isPointOnLine( float px, float py, float ax, float ay, float bx, float by, float error )
{
float dx = bx - ax;
float dy = by - ay;
float len = Math.sqrt( dx*dx + dy*dy );
// Distance is '(B - A)(normalised) X (P - A)'
float d = (dx * (py - ay) - dy * (px - ax)) / len;
if( (d < error) && (d > -error) )
return true;
return false;
}
Apologies for syntax errors, etc.
Man, thanks! I knew I should have paid better attention in my math classes all those years ago (or maybe just committed it to memory better).
Could someone please explain the forumula above? Just so I can understand it better for next time?
(B-A)(normalized) - It’s the normal of the line. A line of length 1 that is at 90 degree angle to the line.
normal X (P-A) - The dot product between the normal and a vector from the point to one of the enpoint. The dot product is the length of one of the vectors projected onto the other, wich gives the length to the line.
I bet I didn’t help you understand, but you could try reading up on the dot product. It’s used alot in computer graphics.
The original didn’t account for being outside the two points, so heres a revision:
boolean isPointOnLine( float px, float py, float ax, float ay, float bx, float by, float error )
{
float dx = bx - ax;
float dy = by - ay;
float len = Math.sqrt( dx*dx + dy*dy );
float rLen = 1.0f / len;
// Distance is '(B - A)(normalised) X (P - A)'
float d = (dx * (py - ay) - dy * (px - ax)) * rLen;
if( (d < error) && (d > -error) )
{
// Now use the dot product to determine distance down the line.
d = (dx * (px - ax) + dy * (py-ay)) * rLen;
if( (d >= 0.0f) && (d <= len) )
return true;
}
return false;
}
There are two stages to this now:
The cross product of 2 vectors produces a third vector that is perpendicular to the two input vectors (A and B), and has magnitude AB sin theta, where theta is the angle between the two vectors. If one of these vectors (B) is a unit vector (1 unit long), then the result is A sin( theta ). This value is the distance of the point from the line.
As we are in 2 dimensions, the cross product ‘vector’ would be entirely up the z- axis, so we can skip most of the cross product and just use the ‘z component’:
(A x B)z = distance from line = Ax * By - Ay * Bx
If this distance is less than the error, we are along the line.
Step 2:
To test if we lie between pointA and pointB, we need the distance of the point along the line. This is done with the DOT product, which gives AB cos (theta).
(A . B) = distance along line - Ax * Bx + Ay * By
Google for ‘cross product’, ‘dot product’ and trigonometry to find more 
PS: Can someone set ‘code’ to use Courier or some other fixed-space font please?
I don’t mean to sound too dumb, but isn’t this fairly straight forward?
Why can’t you just -
If the y’s match, its on the line. You could also do a pre check by ensuring the test x is between the A and B points x’s.
Am I not understanding something?
Dr. A>
that would be what I’d do.
First, like you said, 4 if statements to make sure xCheck and yCheck are within the bounding rectangle of (x1,y1) and (x2, y2).
Then compare the yCheck you have to ( (y2 - y1)/(x2 - x1)*(xCheck - x1) + y1 ). If it’s equal, it’s on the line. That’s right isn’t it?
You could also try the java.awt.geom.Line2D class and one of its contains(…) methods.
I don’t know if it’s fast, but handy. (Same applies to the other classes like Rectangle etc).
Yep, that would be easier I guess I’m in the habit of solving for 3D vectors! 
Taking Malohkan’s soln., I think you can do it without a divide too:
For floating point (with an error margin):
bool isPointOnLine( float ax, float ay, float bx, float by, float xCheck, float yCheck, float error)
{
if( ax < bx)
{
if( (xCheck < ax - error) || (xCheck > bx+error) )
return false;
}
else
{
if( (xCheck < bx-error) || (xCheck > ax+error) )
return false;
}
float test1 = (yCheck - ay) * (bx - ax);
float test2 = (by - ay) * (xCheck - ax);
float scaledError = error * (bx - ax);
if( ( test1 < test2 + scaledError)&&( test1 > test2 - scaledError) )
return true;
return false;
}
No divides or sqrts
If you are just using ints, you can do it without the error bounds, which will make it a whole lot simpler:
bool isPointOnLine( int ax, int ay, int bx, int by, int xCheck, int yCheck)
{
if( ax < bx)
{
if( (xCheck < ax) || (xCheck > bx) )
return false;
}
else
{
if( (xCheck < bx) || (xCheck > ax) )
return false;
}
float test1 = (yCheck - ay) * (bx - ax);
float test2 = (by - ay) * (xCheck - ax);
if( test1 != test2)
return false;
return true;
}
Apologies for syntax errors, etc.
Hello
Line2D contains method will always return false as specified in the javadoc.
crystalsquid, his thanks for your example but I am having a little trouble
If I use
x1 = 24 y1 = 345
x2 = 24 y2 = 350
checkx = 24
checky = 378
it returns true because the test1 and test2 are multiplying by 0. I’m really ocnfusing myself looking at this, any more help would be greatly appeciated
Thanks
The last isPointOnLine functions posted will fail when the line is vertical. The fix is to check wich of abs(dx) and abs(dy) is largest and switch x with y if dy is larger.
This is the reason why almost everyone is useing vector math instead. Use the code posted in the 5th post. It will always work (unless there is a bug).
True. The bounding box check at the start should also check the y-bounds (for a vertical or horizontal line the bounding box check would be exact):
bool isPointOnLine( int ax, int ay, int bx, int by, int xCheck, int yCheck)
{
if( ax < bx)
{
if( (xCheck < ax) || (xCheck > bx) )
return false;
}
else
{
if( (xCheck < bx) || (xCheck > ax) )
return false;
}
if( ay < by)
{
if( (yCheck < ay) || (yCheck > by) )
return false;
}
else
{
if( (yCheck < by) || (yCheck > ay) )
return false;
}
float test1 = (yCheck - ay) * (bx - ax);
float test2 = (by - ay) * (xCheck - ax);
if( test1 != test2)
return false;
return true;
}
That should fix it
Tom; This is actually doing exactly the same maths as the post in (5) but removes the need for a divide when generating the line equation. If you write out the vector maths and re-arrange it you get the maths for the test1 test2. At least thats how I wrote this!