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

This topic is 4774 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 - px;        dl = p2 - p1;        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 * t + p1 * (1.0 - t) - px;        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

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631759
• Total Posts
3002138
×