Sign in to follow this  
D3DXVECTOR3

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

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this