Algorithm to calculate distance between a line and a point

Hi

I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?

You can go to this link if you dont understand what I mean:
http://www.allegro.cc/forums/thread/589720

thanks..

Comments

  • : I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?
    Sure.

    : You can go to this link if you dont understand what I mean:
    : http://www.allegro.cc/forums/thread/589720
    Why not use the code over there?

    Or else: what is your problem in writing the code? What is your code now?

    See ya,
    bilderbikkel

  • : Hi
    :
    : I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?
    :
    : You can go to this link if you dont understand what I mean:
    : http://www.allegro.cc/forums/thread/589720
    :
    : thanks..
    :

    Smallest distance between a line and a point is the line drawn from the point perpendicular to the line.
    Say for the line you have the equation y = ax + b, in two dimensions.

    Now for a little bit of Lineair Algebra. If you shift the line so that at x = 0, y = 0, the line is given by the vector (1, a). Meaning for each 1 step to the right, take 'a' steps up.

    For the point, p, we have p = (p1, p2) as it's coordinates.
    Now we shifted our line to go through the origin so we should do the same with p. We shifted the line down by b, so p becomes p = (p1, p2 - b)

    Now there are two ways of doing this... one is elegant, but makes no sense at all if you're not familar with it.
    The other is continuing in the geometry way.

    Let's start with the elegant one:
    If we have a line, and we consider the point as a vector, reaching out from the origin to this point, we can seperate this new vector into two components: one parallel to the line and one perpendicular to it.
    The parallel component is called a projection of the vector onto a line (or onto another vector if you will). The vector that describes the line I will call l. |p| denotes the length of the vector |p|
    [code]
    proj p = ( |p| Cos t ) (l / |l|)
    [/code]
    t is the angle between p and l. If you just look at the first part |p| Cos t then you recognise that you are using goniometrics to calculate the side of a triangle. The second part l / |l|, is basically to give the projection a direction. The first part is just a number, the length of that side, but that side also has a direction, which is the same as the direction of l. So multiplying it by l reduced to length 1, which is l / |l| will add the proper direction without changing the length.
    The definition of the dot product is u . v = |u| |v| Cos t
    So proj p becomes:
    [code]
    proj p = (( p . l ) / |l|) (l / |l|) = ( p . l ) (l / l.l)
    [/code]
    l.l = |l|^2, (Cos t = 1, t = 0 because l and l are the same line)

    So applying this to our problem we have:
    [code]
    proj p = ( p . l ) (l / l.l)
    p =
    l = <1, a>

    proj p = (p1 + ap2 - ab) / (1 + a^2) <1, a>
    [/code]

    We split up the vector into a parallel and orthogonal component. We are actually interested in the orthogonal component because that is the length. This is given by p - proj p

    [code]
    length = p - proj p
    = - (p1 + ap2 - ab) / (1 + a^2) <1, a>
    = <(ab - ap2) / (1 + a^2),
    (p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2) >

    distance = |length|
    = Sqrt[ (ap2 - ab) / (1 + a^2))^2 +
    ((p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2))^2 ]
    [/code]

    Ok so it aint pretty :) But it's a very systematic way of handling and that's where it gets it's elegance.

    The way of Geometry:

    You're looking for a line that is perpendicular to the line given. Now when you picture it in your head, you'll see that a line perpendicular would be to take 'a' steps up, and 1 step to the left. Meaning it is given by the vector (a, -1) or (-a, 1) (for our purposes here, both are good).
    A more mathematical way of looking at this, is using the dot product, which becomes 0 if and only if the vectors are perpendicular to eachother. (1, a) . (p, q) = 1*p + a*q = 0
    Thus p = -aq and so the vector becomes (-aq, q) or (-a, 1) for q = 1.

    So we have -ay = x for our line -> y = -x / a
    Now we have to place it correctly: shift it up or down till it goes through p.
    [code]
    p2 = -p1 / a + z
    z is our shift
    z = p2 + p1 / a
    [/code]

    Now find where it intersects with our original line.
    [code]
    -x / a + p2 + p1 / a = ax + b
    x = (p1/a + p2 + b) / (a + 1/a)
    y = (p1 + ap2 + ab) / (a + 1/a) + b

    Length^2 = ((p1 + ap2 + ab) / (a + 1/a) + b - p2)^2 +
    ((p1/a + p2 + b) / (a + 1/a) - p1)^2
    [/code]
    Take the square root and you're all done.

    Now I really do not know if I made mistakes or not.. ofcourse I like to think I didn't, but... :)
    Anyway, I assumed this kind of explanation is what you wanted since the link you specified contained all the sourcecode.

    Best Regards,
    Richard

  • : : Hi
    : :
    : : I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?
    : :
    : : You can go to this link if you dont understand what I mean:
    : : http://www.allegro.cc/forums/thread/589720
    : :
    : : thanks..
    : :
    :
    : Smallest distance between a line and a point is the line drawn from the point perpendicular to the line.
    : Say for the line you have the equation y = ax + b, in two dimensions.
    :
    : Now for a little bit of Lineair Algebra. If you shift the line so that at x = 0, y = 0, the line is given by the vector (1, a). Meaning for each 1 step to the right, take 'a' steps up.
    :
    : For the point, p, we have p = (p1, p2) as it's coordinates.
    : Now we shifted our line to go through the origin so we should do the same with p. We shifted the line down by b, so p becomes p = (p1, p2 - b)
    :
    : Now there are two ways of doing this... one is elegant, but makes no sense at all if you're not familar with it.
    : The other is continuing in the geometry way.
    :
    : Let's start with the elegant one:
    : If we have a line, and we consider the point as a vector, reaching out from the origin to this point, we can seperate this new vector into two components: one parallel to the line and one perpendicular to it.
    : The parallel component is called a projection of the vector onto a line (or onto another vector if you will). The vector that describes the line I will call l. |p| denotes the length of the vector |p|
    : [code]
    : proj p = ( |p| Cos t ) (l / |l|)
    : [/code]
    : t is the angle between p and l. If you just look at the first part |p| Cos t then you recognise that you are using goniometrics to calculate the side of a triangle. The second part l / |l|, is basically to give the projection a direction. The first part is just a number, the length of that side, but that side also has a direction, which is the same as the direction of l. So multiplying it by l reduced to length 1, which is l / |l| will add the proper direction without changing the length.
    : The definition of the dot product is u . v = |u| |v| Cos t
    : So proj p becomes:
    : [code]
    : proj p = (( p . l ) / |l|) (l / |l|) = ( p . l ) (l / l.l)
    : [/code]
    : l.l = |l|^2, (Cos t = 1, t = 0 because l and l are the same line)
    :
    : So applying this to our problem we have:
    : [code]
    : proj p = ( p . l ) (l / l.l)
    : p =
    : l = <1, a>
    :
    : proj p = (p1 + ap2 - ab) / (1 + a^2) <1, a>
    : [/code]
    :
    : We split up the vector into a parallel and orthogonal component. We are actually interested in the orthogonal component because that is the length. This is given by p - proj p
    :
    : [code]
    : length = p - proj p
    : = - (p1 + ap2 - ab) / (1 + a^2) <1, a>
    : = <(ab - ap2) / (1 + a^2),
    : (p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2) >
    :
    : distance = |length|
    : = Sqrt[ (ap2 - ab) / (1 + a^2))^2 +
    : ((p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2))^2 ]
    : [/code]
    :
    : Ok so it aint pretty :) But it's a very systematic way of handling and that's where it gets it's elegance.
    :
    : The way of Geometry:
    :
    : You're looking for a line that is perpendicular to the line given. Now when you picture it in your head, you'll see that a line perpendicular would be to take 'a' steps up, and 1 step to the left. Meaning it is given by the vector (a, -1) or (-a, 1) (for our purposes here, both are good).
    : A more mathematical way of looking at this, is using the dot product, which becomes 0 if and only if the vectors are perpendicular to eachother. (1, a) . (p, q) = 1*p + a*q = 0
    : Thus p = -aq and so the vector becomes (-aq, q) or (-a, 1) for q = 1.
    :
    : So we have -ay = x for our line -> y = -x / a
    : Now we have to place it correctly: shift it up or down till it goes through p.
    : [code]
    : p2 = -p1 / a + z
    : z is our shift
    : z = p2 + p1 / a
    : [/code]
    :
    : Now find where it intersects with our original line.
    : [code]
    : -x / a + p2 + p1 / a = ax + b
    : x = (p1/a + p2 + b) / (a + 1/a)
    : y = (p1 + ap2 + ab) / (a + 1/a) + b
    :
    : Length^2 = ((p1 + ap2 + ab) / (a + 1/a) + b - p2)^2 +
    : ((p1/a + p2 + b) / (a + 1/a) - p1)^2
    : [/code]
    : Take the square root and you're all done.
    :
    : Now I really do not know if I made mistakes or not.. ofcourse I like to think I didn't, but... :)
    : Anyway, I assumed this kind of explanation is what you wanted since the link you specified contained all the sourcecode.
    :
    : Best Regards,
    : Richard
    :
    :

    Thanks. I just wanted another opinion just to make sure
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories