Jump to content
  • Advertisement
Sign in to follow this  
D3DXVECTOR3

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.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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 - 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 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!