5

Possible Duplicate:
Shortest distance between a point and a line segment

i am looking for a way to calculate the minimum distance in all cases. the problems with solutions i found are:

  1. Solutions with graphical conceptual drawings show point always on perpendicular from line segment so it's "between line segment's end points". My geometry skills are horrible so i can't verify that these solutions work in all cases.

  2. Algorithm solutions are a: with fortran or some other language i don't fully understand, b: are flagged as incomplete by people, c: calling methods/functions that are not described in any way (considered trivial).

Good example of 2 a, b and c is

Shortest distance between a point and a line segment

i have the 2D line segment as double-type co-ordinate pair (x1, y1), (x2,y2) and point as double type co-ordinate (x3,y3). C#/Java/C solutions are all appreciated.

Thanks for your answers & BR: Matti

Community
  • 1
  • 1
char m
  • 7,840
  • 14
  • 68
  • 117
  • 2
    I counted implementations in 6 different languages here: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment – Tim Robinson Dec 14 '10 at 10:45
  • @oded: which part u refer? that it's asked and answered million times? or that there's no 'how to calculate' in the beginning? as i said apologies for bad search skills but if one can't imagine the 'how to calculate' to the beginning... well. ur link is 2 help people 2 understand each other. think u understood me perfectly. – char m Dec 14 '10 at 10:55
  • You are a. Not describing your question properly. b. Not showing us what you have tried so far. c. Not explaining where you are having difficulties. – Oded Dec 14 '10 at 10:56
  • ok. missing 'how to...' seems 2 b a problem. didn't occur 2 me at all but i ask better questions in future. – char m Dec 14 '10 at 10:57
  • @tim: this was the link i found earlier (php/fortran). actually most of the implemetations are flagged as faulty and C# missing so didn't help a lot. – char m Dec 14 '10 at 11:08
  • @matti apart from Fortran, the other languages on there are similar to C#. It should be easy to come up with a C# routine. Once you have it, you could add your own C# answer to the original question. – Tim Robinson Dec 14 '10 at 12:41

2 Answers2

19

Answered also Shortest distance between a point and a line segment because that gathers solutions in all languages. Answer put also here because this questions asks specifically a C# solution. This is modified from http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :

//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
    double[] AB = new double[2];
    double[] BC = new double[2];
    AB[0] = pointB[0] - pointA[0];
    AB[1] = pointB[1] - pointA[1];
    BC[0] = pointC[0] - pointB[0];
    BC[1] = pointC[1] - pointB[1];
    double dot = AB[0] * BC[0] + AB[1] * BC[1];

    return dot;
}

//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
    double[] AB = new double[2];
    double[] AC = new double[2];
    AB[0] = pointB[0] - pointA[0];
    AB[1] = pointB[1] - pointA[1];
    AC[0] = pointC[0] - pointA[0];
    AC[1] = pointC[1] - pointA[1];
    double cross = AB[0] * AC[1] - AB[1] * AC[0];

    return cross;
}

//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
    double d1 = pointA[0] - pointB[0];
    double d2 = pointA[1] - pointB[1];

    return Math.Sqrt(d1 * d1 + d2 * d2);
}

//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC, 
    bool isSegment)
{
    double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
    if (isSegment)
    {
        double dot1 = DotProduct(pointA, pointB, pointC);
        if (dot1 > 0) 
            return Distance(pointB, pointC);

        double dot2 = DotProduct(pointB, pointA, pointC);
        if (dot2 > 0) 
            return Distance(pointA, pointC);
    }
    return Math.Abs(dist);
}
sorifiend
  • 5,927
  • 1
  • 28
  • 45
char m
  • 7,840
  • 14
  • 68
  • 117
  • 4
    Err, which points A,B,C are the line end points and which is the actual singular point ? You should really name the vars properly, tahts why we use names and not numbers. – mP. Dec 05 '12 at 00:16
  • 1
    It's in the comments. A and B are the vertices of the line or line segment, and C is the point in question. Once you've got that it's arguably more readable with single letter variables names. – Nat Mar 30 '14 at 16:41
  • Verified. You may use `System.Windows.Point` and `System.Windows.Vector`, which will greatly simplify the code. – Gqqnbig May 14 '14 at 12:24
  • @LoveRight, indeed. Here is WPF version: http://stackoverflow.com/a/32814053/332528 – torvin Sep 27 '15 at 23:56
  • 1
    The comment for the first function says `//Compute the dot product AB . AC`, but it appears as if it computes the dot AB • BC. Is this a typo, or is this me not fully understanding dot products? – M-Pixel Dec 01 '15 at 05:15
  • 1
    This is giving NaN with vertical line and colinear point. – crokusek Jul 01 '16 at 08:54
  • 1
    //Compute the dot product AB . AC... should not it be AB.BC ? – Humam Helfawi Jul 04 '16 at 21:08
0

If you have line

L: A * x + B * y + C = 0

Then distance from this line to point (x1, y1) is abs(A * x1 + B * y1 + C) / sqrt(A * A + B * B). in your case if you has interval, (xa, ya); (xb, yb) you should find min( distance(x1, y1, xa, ya), distance(x1, y1, xb, yb)) then see if perpendecular from (x1, y1) to line L is on the interval, then the answer is the distance is it. otherwise min of two distances.

Mihran Hovsepyan
  • 10,810
  • 14
  • 61
  • 111