I need an efficient methode to detect the distance from a point to a line

This topic is 4557 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I need a simple, lightweight method to see if as point A is on a line created by 2 other points ie C, D.
         /
A   /
/
D
/
/
/
C
/
/


I have 2 coordinates C and D and I want to see if point A is on the line CD. It has to be very simple cus this need to work in J2ME (Java for Mobile Phones)

Share on other sites
This does the trick for me:
	double distanceFromPoint( int x, int y )	{		double u = squaredDistance( fromX, fromY, toX, toY );		// If from and to are same point, give distance from point to one of those two		if( u == 0 )			return Math.sqrt( squaredDistance( fromX, fromY, x, y ) );		// Calculate intersection (1)		u = 1/u;		u *= (x - fromX)*(toX - fromX) + (y - fromY)*(toY - fromY);		if( u < 0 )			return Math.sqrt( squaredDistance( fromX, fromY, x, y ) );		if( u > 1 )			return Math.sqrt( squaredDistance( toX, toY, x, y ) );		// Calculate intersection (2)		int ix = (int)((fromX + u * (toX - fromX)) + 0.5d);		int iy = (int)((fromY + u * (toY - fromY)) + 0.5d);		return Math.sqrt( squaredDistance( ix, iy, x, y ) );	}	private double squaredDistance( int x1, int y1, int x2, int y2 )	{		return ((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1));	}

The global variables fromX, fromY, toX and toY are the coordinates of the line..

Share on other sites
here's the hacked code I use...returns nearest distance squared, to save on sqrt.

float Point2LineDis2 (float *p1, float *p2, float*px){    //  remember:    //  a*x*x + b*x + c = 0    //  min or max happens at:    //  2ax + b = 0;    float a, b, t;    float dp, dl, l;        //*    a = b = 0.0;        for (int i = 0; i < 3; ++i)    {        dp = p1[i] - px[i];        dl = p2[i] - p1[i];        a += dl*dl;        b += 2*dl*dp;    }        //  error check: if p1 == p2, then a = 0    if (a == 0.0)        t = 0.0;    else        //  otherwise, compute best         t = -0.5 * b / a;            //  cap infinite lines to the endpoints    if (t < 0.0) t = 0.0;    else if (t > 1.0) t = 1.0;    //  and find the distance    l = 0.0;    for (int i = 0; i < 3; ++i)    {        dl = p2[i] * t + p1[i] * (1.0 - t) - px[i];        l += dl*dl;    }        return (l);}

Share on other sites
WoW, thx guys for the fast reply :)
I will try/use both :D

edit:

Hey DaBono, im also from the Netherlands(Overijssel) :D

Share on other sites
Hmmm, this can be done much more lightweight...

Consider capital letters to be vectors.

Line through C and D: P = C + q*(D - C), P is a point on this line for a specific q

So if A is on this line we can solve q for A = C + q * (D- C)

A 2D version:

Ax = Cx + q1 * (Dx - Cx) AND
Ay = Cy + q2 * (Dy - Cy)

So:

q1 = (Ax - Cx) / (Dx - Cx) AND
q2 = (Ay - Cy) / (Dy - Cy)

If q1 and q2 are more or less equal (use an epsilon) then A is on the line.
Beware of two special cases: when the line is either horizontal or vertical then these divisions go wrong. In these cases: if the line is horizontal check whether Ay has the right value or when it is vertical check Ax.

Cheers

Share on other sites
Well, yes , the first two solutions find the distance for ma point to a SEGMENT from A to B.

If you need to check if its on the line use what the above poster said or if you need the distance do this (x,y are coordinates of A and xc,yc,xd,yd, are coordinates of C and D respectively)

deltaX=xd-xc;
deltaY=yd-yc;

distance=(x*deltaY-y*deltaX+yc*deltaX-xc*deltaY)/sqrt(deltaX*deltaX+deltaY*deltaY)

or if you just need to know if its on the line ommit the whole /sqrt part.

so just do:
d = (x*deltaY-y*deltaX+yc*deltaX-xc*deltaY);
and check if d is equal to 0 (within some epsilon value because of rounding errors).

Share on other sites
You may want to look at mathworlds formula
here at (9)

Which is simular to some of the others posted.

The same as A Guy from CRO's[/edit]

Share on other sites
Another one...

// dot product of vectors
// E.Dot(F) = E.x * F.x + E.y * F.y + E.z * F.z;

// how 'thick' is the line
float line_thickness = 1; // two pixels thick (radius of line = 1).

// code......
Vector H = A - C;
Vector E = D - C;
float e2 = E.Dot(E);
float eh = H.Dot(E);
float t = eh / e2;
if (t < 0.0f) t = 0.0f;
if (t > 1.0f) t = 1.0f;

// F = closest point on the segment [CD] from point A.
Vector F = C + t * E;

// distance of point to cloest point on segment = distance of point to segment.
// use squared distances to save expensive square roots.
Vector S = A - F;
float s2 = S.Dot(S);

// point inside the segment's thickness
if (s2 < line_thickness * line_thickness)
{
// point on the segment
return true;
}

// point outside the segment
return false;

Share on other sites
Easier way.

Turn the line into a simple linear equation (this is for 2d, right?), and then test the point's coordinates in that equation.

If it's true, it's on the line.

Share on other sites
Quote:
 Easier way.Turn the line into a simple linear equation (this is for 2d, right?), and then test the point's coordinates in that equation.If it's true, it's on the line.

That's what I did... :)

Cheers

Share on other sites
yeah, but we are talking also with precision. You can rely on the point being *exactly* on the line.

And not just the line, but also being in the segment.

Plus, you have to use divisions, which is unsafe, especially when dealing with fixed point maths (for a mobile game, he will have too) or integers.

Using the Point-Distance-From Segment allows you to change the thickness of the line, and uses no division (only one, which is a constant from the segment data, so it should be safe and turned into an inverse multiplication).

It's also parametric, and gives you the closest point on the segment to the point, useful for collision response, if you have too.

Share on other sites
Sure, I don't argue with that. I was just answering the exact question.

With regard to thickness of the line; choosing the epsilon carefully will do the same... and looking at the sign of q1 and q2 is an indication of on what side of the line the point is.

Cheers

Share on other sites
const double dTolerance = 0.001;

if (abs(DotProduct(A-C, D-C)) < dTolerance)
{
// Point A lies on line C, D
}

If you want to know if point A actually lies between points C and D you will need to do some additional checks but from the diagram it seems like you are not so interested in that.

Share on other sites

This topic is 4557 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628706
• Total Posts
2984309

• 23
• 10
• 9
• 13
• 13