# Need help about point and line

• 01-01-2009
audinue
[SOLVED] Need help about point and line
Anyone know how to detect if a Point(x, y) is in a Line(x1, y1, x2, y2) or not?

Quiet not good at math :( please...
• 01-01-2009
tabstop
If the slope from (x1,y1) to (x,y) is the same as the slope from (x1,y1) to (x2,y2). Breaking out the formula for slope gives (x-x1)*(y2-y1) == (x2-x1)*(y-y1).
• 01-01-2009
audinue
Quote:

Originally Posted by tabstop
If the slope from (x1,y1) to (x,y) is the same as the slope from (x1,y1) to (x2,y2). Breaking out the formula for slope gives (x-x1)*(y2-y1) == (x2-x1)*(y-y1).

Works like a charm, thanks~! You are smart tabstob! Thanks!

http://audinue.navhost.com/LineTest.html

Code:

var line = {x1:10, y1:10, x2:100, y2:100};
_root.lineStyle(1);
_root.moveTo(line.x1, line.y1);
_root.lineTo(line.x2, line.y2);
onEnterFrame = function () {
var point = {x:_root._xmouse, y:_root._ymouse};
hit_mc._visible = (point.x-line.x1)*(line.y2-line.y1) == (line.x2-line.x1)*(point.y-line.y1);
};

• 01-01-2009
Salem
You also need to check that x >= x1 && x <= x2 to make sure it is on the line.
The slope extends to +/- infinity, so you need to test for more than just being on the slope.
• 01-01-2009
audinue
Quote:

Originally Posted by Salem
You also need to check that x >= x1 && x <= x2 to make sure it is on the line.
The slope extends to +/- infinity, so you need to test for more than just being on the slope.

What do you mean? I don't get it.
• 01-01-2009
tabstop
Salem's point is that if you want if you want the point to be on the line segment strictly between (x1, y1) and (x2, y2) [as opposed to the line between the points that goes forever], then you need to check that x is between x1 and x2 (i.e., that (x1-x)*(x2-x) < 0).
• 01-01-2009
audinue
Code:

boolean i s H i t (Point point, Line line) {
return ((point.getX() >= line.getX1()) && (point.getX() <= line.getX2()) && (point.getY() >= line.getY1()) && (point.getY() <= line.getY2()))
&& ((point.getX() - line.getX1()) * (line.getY2() - line.getY1()) == (line.getX2() - line.getX1()) * (point.getY() - line.getY1()));
}

What the... :D
• 01-01-2009
matsp
Quote:

Originally Posted by audinue
Code:

boolean i s H i t (Point point, Line line) {
return ((point.getX() >= line.getX1()) && (point.getX() <= line.getX2()) && (point.getY() >= line.getY1()) && (point.getY() <= line.getY2()))
&& ((point.getX() - line.getX1()) * (line.getY2() - line.getY1()) == (line.getX2() - line.getX1()) * (point.getY() - line.getY1()));
}

What the... :D

I'm sure that can be written a bit more readable by storing the results of the getters in a set of suitably named variables. Calling the getter functions several times over is hardly meaningful.

--
Mats
• 01-02-2009
mike_g
Heres a version I came up with:
Code:

int PointIsOnLine(int x1, int y1, int x2, int y2, int x3, int y3)
{
if(x1 == x2 && y1 == y2) //Not a line
return(x1 == x3 && y1 == y3);
return (y3 == y1);
return (x3 == x1);

float gradient = (float)(y2 - y1) / (float)(x2 - x1);
int x01 = x1 - ((float)y1 / gradient +0.5);
int x02 = x3 - ((float)y3 / gradient +0.5);
return (!(x02-x01));
}

int PointIsInLine(int x1, int y1, int x2, int y2, int x3, int y3)
{
if(! PointIsOnLine(x1, y1, x2, y2, x3, y3)) return 0;
if(x3 > MAX(x1, x2)  || x3 < MIN(x1, x2)) return 0;
return 1;
}

• 01-02-2009
brewbuck
Hrm. So if your line is from (0, 0) to (100, 1)... There are absolutely no points which are on that line which have integer coordinates, except for the endpoints.

So using this sort of algorithm, you'd decide that nothing at all ever intersects that line, even though it's over 100 units long. Using integer coordinates isn't really the best choice for this sort of thing I think
• 01-02-2009
mike_g
Yeah, the co-ords get rounded:
Code:

int x01 = x1 - ((float)y1 / gradient +0.5);
int x02 = x3 - ((float)y3 / gradient +0.5);

I was using integer maths for this as I was checking pixel values in 2D to see if they sat on a line. I guess generally it would be better to do everything in floating point - that would very simple modification.

Edit: although actually it looks as if its rounding the wrong way, lol. Perhaps it should have been:
Code:

int x01 = x1 - ((float)y1 / gradient) +0.5;
int x02 = x3 - ((float)y3 / gradient) +0.5;

this might fix an old bug I never worked out...
• 01-02-2009
CornedBee
But if you do it with floating point, you'll want to do a delta comparison, since floating points rarely compare exactly equal, even when they should.
• 01-02-2009
mike_g
Yeah, thats one of the reasons I have an irrational fear of using floats, lol.