Nearest line point for a given point

yonnak

Hello, all is in the title.

How can I retrieve the nearest point on a line for an arbitrary given point?

I saw the pointAt() function in QLineF that could help but can not sort it out.

Thanks

kshegunov

Take the line's normal vector. Construct a line equation based on the normal vector, such that the line will pass through the outside point. Solve for the unknown x and y in the two line equations system - that's the intersection point, and by definition the point on the line that's nearest (as it's along the perpendicular to the line) to the one you specified.

VRonin

Or you let Qt do the math for you

QPointF nearestPoint(const QLineF& line, const QPointF& point){
QLineF perpendicLine(point,QPointF(point.x(),0.0));
perpendicLine.setAngle(90.0+line.angle());
QPointF result;
line.intersect(perpendicLine,&result);
return result;
}

EDIT

Fixed some disgraceful math

Rondog

You could find this using two cross products. I assume you have a point and direction for the line and only an xyz value for the point.

PLine = {0,0,0} // any point on the existing line
ALine = {1,0,0} // direction of the line
PPoint = {10,10,0) // some random point in space

V = PPoint - PLine = {10,10,0}
C1 = ALine * V // cross product, result is {0,0,10}
C2 = C1 * ALine // cross product, result is {0,-10,0}

Closest point on line:
CPoint = PPoint + C2 = {10,0,0}

The corss product is calculated like this:

V.i = V1.j*V2.k - V1.k*V2.j;
V.j = V1.k*V2.i - V1.i*V2.k;
V.k = V1.i*V2.j - V1.j*V2.i;

VRonin

Given the inputs available in a QLineF and a QPointF I think it's a 5x5 matrix to invert to solve (unknown being: slope of line, offset of line, offset of perpendicular line, x of intersection, y of intersection). I'd gladly leave it to the machine if I can (i.e. is not a drag on performance)

kshegunov

@VRonin said in Nearest line point for a given point:

Or you let Qt do the math for you

You know why I oppose this? Not that's it's wrong (I haven't checked it, but I assume it's correct), but because one should first learn the math, and only then delegate the math to a black box. Otherwise one gets into situations like calculating trigonometric functions of angles under 1 degree, and ultimately looking like an illiterate (and acting like one, which is worst). :)

kshegunov

@VRonin said in Nearest line point for a given point:

Given the inputs available in a QLineF and a QPointF I think it's a 5x5 matrix to invert to solve

Nope, you need to solve a system of 2 equations with 2 unknowns, you don't even need matrices for this ...

VRonin

I agree if you have the equation describing the first line (i.e. you already know the slope and offset parameters of that line) put all QLineF gives you are 2 points so you have to use them to build the equation first

kshegunov

@VRonin said in Nearest line point for a given point:

I agree if you have the equation describing the first line

This is obtained trivially from the coordinates of two points lying on the line.

(i.e. you already know the slope and offset parameters of that line)

There's no slope and offset here. We are not talking about functions, the line could very well be vertical and then the slope would be infinite. One should be using line equations:

A * x + B * y + C = 0

defines a line in the plane. (you can easily extend this to 3D, 4D or w/e space). It's left to the reader to show how to most easily determine A, B and C from two points with 2 coordinates each in such a way that plugging in the coordinates of each point will keep the equation true.

VRonin

@kshegunov said in Nearest line point for a given point:

This is obtained trivially from the coordinates of two points lying on the line.

Agree once again but either you do it separately or you put even this system in the previous one making the system matrix bigger. Using your naming convention (dividing both sides by B) you solve for A/B and C/B (2 equations) then you plug them into y-point.y()+B/A(x-point.x())=0 and xA/B+y+C/B=0 (2 equations)

You also have to handle trivial cases (horizontal (A=0) and vertical (B=0) line separately). I stand by my 5 lines turn-your-brain-off solution

kshegunov

Sure, I don't like "brain off solutions" though, as I mentioned why.

Consider this:
The (unnormalized) vector that's along the two points is (x1 - x0, y1 - y0) where an obvious notation for the coordinates of the two points is used. Now, you know that this is the tangential vector to the line, then the normal vector is (y1 - y0, x0 - x1). Then you know that A = y1 - y0 and B = x0 - x1 are exactly the normal vector's coordinates. Then you're left only to determine C. From the original equation: C = - A * x - B * y. Plugging any of the two points that define the line will give you the answer for C.
Nifty, no?

Now, back to the original problem. You have 2 lines and 3 points. 2 points define the first line equation (as described above, with appropriate renaming of coefficients): A * x + B * y + C1 = 0. You search from this a family of lines that are perpendicular, or trivially: B * x - A * y + C2 = 0. You're only left to find C2, which you obtain by a simple arithmetic substitution from the known A and B and the outside point's coordinates. What you're left with is to find the intersection of those two lines, namely to solve the following system:

A * x + B * y + C1 = 0
B * x - A * y + C2 = 0

for the unknowns x and y.

ofmrew

@yonnak

I will give you two solutions, one is dumb and dirty and the other is elegant. The dumb and dirty involved finding the angle required to rotate the line to the x-axis (remember to translate the line to the origin). Use that angle to rotate the point. The closest point is (x of the rotated point, 0), the y value is irrelevant because the point on the line you want will only have an x value until it is reverse rotated. What you have done is a dirty way of projecting the line from the origin of your line to the given point.
The elegant solution uses the dot product of your line and the line to the point to project the latter onto the former.

The code is:
correlationReturn Correlator::lineSegCorrelationPoint(QLineF ls, QPointF pm, qreal d)
{

valid = false;
qreal dSquare = d * d;
correlationReturn cr;
QPointF pbs = ls.p1();
QPointF pes = ls.p2();
QPointF pep = pes - pbs;
QPointF pmp = pm - pbs;
qreal dp = pmp.dotProduct(pmp, pep);
QPointF cp = (dp / (pmp.dotProduct(pep, pep)) * pep) + pbs;
cr.correlationPoint = cp;
QPointF mToCP = pm - cp;
qreal cd = QPointF::dotProduct(mToCP, mToCP);
cd = qSqrt(cd);
cr.distanceToPM = cd;
if (cd > d){
    cr.isCorrelationValid = false;
    valid = false;
    return cr;
} else {
    valid = true;
    cr.isCorrelationValid = true;
    qreal x1 = pes.rx() - pbs.rx();
    qreal x2 = cp.rx() - pbs.rx();
    qreal t = x2/x1;
    cr.isPointAtEnd = false;
    if (t < 0.0){
        cr.isPointAtEnd = true;
        cr.correlationPoint = pbs;
        QPointF cToB = cp - pbs;
        if ((QPointF::dotProduct(cToB, cToB)) > dSquare){
            cr.isCorrelationValid = false;
            valid = false;}
    }
    if (t > 1.0){
            QPointF cToE = cp - pes;
            cr.isPointAtEnd = true;
            cr.correlationPoint = pes;
            if (QPointF::dotProduct(cToE, cToE) > dSquare){
                cr.isCorrelationValid = false;
                valid = false;}
    }
}
correlationPoint = cr.correlationPoint;
return cr;

}
struct correlationReturn{
QPointF correlationPoint;
bool isCorrelationValid;
bool isPointAtEnd{false};
qreal distanceToPM;
};

Hope this helps. If you have any question, please ask.

yonnak

Thank you for all this answers!

I I agree understanding and doing all the maths is way better than using a blackbox that do all the stuff for you! but... My trigo lessons are old and I don't want taking too much time re-learning it :)

I solved it like this:

    QPointF pt = mapFromParent(point);
    QLineF trackLine((m_angles.at(i-1)->pos()),(m_angles.at(i)->pos()));

    double APx = pt.x() - trackLine.x1();
    double APy = pt.y() - trackLine.y1();
    double ABx = trackLine.x2() - trackLine.x1();
    double ABy = trackLine.y2() - trackLine.y1();
    double magAB2 = ABx*ABx + ABy*ABy;
    double ABdotAP = ABx*APx + ABy*APy;
    double t = ABdotAP / magAB2;

    QPointF newPoint;

    if ( t < 0) {
        newPoint = trackLine.p1();
    }else if (t > 1){
        newPoint = trackLine.p2();
    }else{
        newPoint.setX(trackLine.x1() + ABx*t);
        newPoint.setY(trackLine.y1() + ABy*t);
    }

    return newPoint;

( used an algo found on the internet and adpat it a little before seeing all your answers :)