Distance Between a point to a line formed by two points

Question

I am trying to find the perpendicular distance from point 3 (newPoint) to a line formed by point 1 (prevPoint) and point 2 (curPoint) in C++.

I was using this formula previously. But now I am questioning the correctness of my program upon some cross-checking.

EDIT: all the points(prevPoint, curPoint and newPoint) is of Point type

struct Point {
    string name;
    int x;
    int y;
    bool visited;
};


double d = distance(prevPoint, curPoint);
double dx = (curPoint.x - prevPoint.x) / d;
double dy = (curPoint.y - prevPoint.y) / d;
double distToLine = abs((newPoint.x - prevPoint.x) * dy - (newPoint.y - prevPoint.y) * dx);

The distance function:

double distance(Point a, Point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);}

Is my code correct? I need some correct formula if its not. Thanks!

https://math.stackexchange.com/ seems more suitable for this question. — Jason, Feb 27 '23 at 07:23
Without knowing what `prevPoint` and `curPoint` represent, it's difficult to even guess about whether your code is correct or not (and impossible to be sure). I did post some code for this task in an old answer though: https://stackoverflow.com/a/1574493/179910 — Jerry Coffin, Feb 27 '23 at 07:28
@JerryCoffin sorry for that, i added the struct definition, is that sufficient? — Carolyn, Feb 27 '23 at 07:31
You might get slightly better performance/accuracy implementing `distance` in terms of `std::hypot`: `double distance(point a, point b){ return std::hypot(a.x - b.x, a.y - b.y); };` — Red.Wave, Feb 27 '23 at 09:03

score 3 · Accepted Answer · answered Feb 27 '23 at 07:29

3

The formula would be as follows in your case:

double d = distance(prevPoint, curPoint);
double area = abs((curPoint.x - prevPoint.x) * (newPoint.y - prevPoint.y) - (curPoint.y - prevPoint.y) * (newPoint.x - prevPoint.x));
double distToLine = area / d;

answered Feb 27 '23 at 07:29

nielsen

5,641
10
27

hi, thanks for replying but is that essentially the same as the formula that i used? cuz the output is the same – Carolyn Feb 27 '23 at 07:33
1

@Carolyn Yes, looking at it, it is the same formula, just arranged differently. So the short answer is that your formula is correct :-). Now you also have the justification in the linked Q/A. – nielsen Feb 27 '23 at 07:36
hi, thanks for your answer, any idea on how to check those points that will never be perpendicular to the line? See example here: https://imgur.com/c4f7Pdt – Carolyn Feb 27 '23 at 15:18
@Carolyn The formula should be understood as the distance from the point (D) to the infinite line passing through the two points (C,B). It does not matter that the projected point is not between the two points. Of course, it is required that C and B are not the same point. In practice (to avoid numerical issues) they must be some distance apart (`d` should not be a very small number). – nielsen Feb 27 '23 at 16:51

score 0 · Answer 2 · answered Feb 27 '23 at 09:42

In the following test code, your code had the same results as mine.

struct Point
{
    int x,y;
    Point( int x=0, int y=0 ) : x(x),y(y) {}
};

double MyMethod( Point prevPoint, Point curPoint, Point newPoint )
{
    //For simplicity, solve the problem in a coordinate system with the origin at prevPoint.
    Point B( curPoint.x-prevPoint.x, curPoint.y-prevPoint.y );
    Point C( newPoint.x-prevPoint.x, newPoint.y-prevPoint.y );

    // Considering the Vector P as
    //  P = t*B - C
    // where, t is scalar.
    //
    // What we need to do is find the value of t that minimizes the length of this P.
    // Objective Function is :
    //  Err(t) = (P dot P) = (t*Bx - Cx)^2 + (t*By - Cy)^2
    // And Then
    //  dErr(t)/dt  =  2*(t*Bx - Cx)Bx + 2*(t*By - Cy)By = 0
    // So
    //  t = (CxBx + CyBy) / (BxBx + ByBy)
    double t = ( C.x*B.x + C.y*B.y ) / double(B.x*B.x + B.y*B.y);

    // Now the distance we want to obtain is length of P (with the calculated t value).
    double Px = t*B.x - C.x;
    double Py = t*B.y - C.y;
    return sqrt( Px*Px + Py*Py );
}

namespace YourCode
{
    double distance(Point a, Point b)
    {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return sqrt(dx * dx + dy * dy);
    }

    double YourMethod( Point prevPoint, Point curPoint, Point newPoint )
    {
        double d = distance(prevPoint, curPoint);
        double dx = (curPoint.x - prevPoint.x) / d;
        double dy = (curPoint.y - prevPoint.y) / d;
        double distToLine = abs((newPoint.x - prevPoint.x) * dy - (newPoint.y - prevPoint.y) * dx);
        return distToLine;
    }
}

int main(int argc, char *argv[])
{
    Point A( 3,10 );
    Point B( -5, 22 );
    Point C( 1,4 );

    std::cout << YourCode::YourMethod(A,B,C) << std::endl;
    std::cout << MyMethod(A,B,C) << std::endl;
    
    return 0;
}

Distance Between a point to a line formed by two points

2 Answers2