Shortest distance between a QPainterPath and a QPoint

Question

I have a QPainterPath that can hold any sequence of lines and/or cubic bezier curves. Now, I've got a QPoint that I need to calculate the shortest distance between the QPainterPath and the point. Since the path itself does not do much more than storing the elements in order I add them to the path, it doesn't provide such functionality by itself. The only idea I had was to construct a polygon using the QPainterPath::toFillPolygon(), but this sometimes returns me a polygon that is equal to the path and sometimes an empty polygon. Moreover, the QPolygonF object is just a list of points, some of them connected with lines, and some of them are not connected in the original path, but I can't find out which of them are connected and which not.

Is there any (simple) solution to calculate the shortest distance between a QPainterPath (preferably without converting to a polygon) and a QPoint?

Duplicate question at http://www.qtcentre.org/threads/31451-How-to-find-the-nearest-point-on-a-QPainterPath, but not one with a solution (simple or otherwise). — eclarkso, Feb 23 '16 at 18:36
@DieterLücking As eclarkso wrote there is no answer in those questions (at least the one he linked and I found using a search engine) — msrd0, Feb 23 '16 at 19:20

score 1 · Answer 1 · edited Feb 23 '16 at 19:06

1

QPainterPath has pointAtPercent() so you can iterate the path at a given step and check the distances between a number of points lying on the path and the target point.

This will give you roughly the shortest distance, and if you want more precision, you can focus on those segments of the path and iterate at a finer step.

edited Feb 23 '16 at 19:06

msrd0

7,816
9
47
82

answered Feb 23 '16 at 18:49

dtech

47,916
17
112
190

thanks, this method is definitely fine for approximating the distance, although I would like to have an exact solution. I'll go with that solution if there is no better one – msrd0 Feb 23 '16 at 19:08
If it is a straight line or an arc you could calculate it exactly, but if you have bezier curves it will be always approximate using line segments either way. – dtech Feb 23 '16 at 19:11
I know and I don't like the way to get the polygon with just lines anyway, but you can also get a function of a bezier curve, although I think I read that this is a 5-polynomial solution which I definitely don't want to solve ... – msrd0 Feb 23 '16 at 19:18

MathCrackExchange · Answer 2 · 2020-01-31T02:43:17.263

Stick this code snippet in your utility.cpp or geom_tools.cpp. It's meant to be a general tool so shouldn't go in say a custom QGraphicsItem subclass.

 #include <QVector2D>
 #include <limits>

 QPointF closestPointOnPath(const QPointF &point, const QPainterPath &path)
{
    if (path.isEmpty())
        return point;

    auto vec = QVector2D(point);
    auto poly = path.toFillPolygon();
    float d, minDist = FLT_MAX;
    QVector2D p, q, v, u, minVec;

    for (int k=0; k < poly.count() - 1; k++)
    {
        p = QVector2D(poly.at(k));
        if (k == poly.count() - 1)
            k = -1;
        q = QVector2D(poly.at(k+1));
        v = q - p;
        u = v.normalized();
        d = QVector2D::dotProduct(u, vec - p);

        if (d < 0.0f) {
            d = (vec - p).lengthSquared();

            if (d < minDist)
            {
                minDist = d;
                minVec = p;
            }
        }
        else if (d*d > v.lengthSquared())
        {
            d = (vec - q).lengthSquared();

            if (d < minDist)
            {
                minDist = d;
                minVec = q;
            }
        }
        else {
            u *= d;
            u += p;
            d = (vec - u).lengthSquared();

            if (d < minDist)
            {
                minDist = d;
                minVec = u;
            }
        }
    }

    if (minDist >= FLT_MAX)
        return point;

    return minVec.toPointF();
}

This results in a very smooth operation say if an arrow has to be attached to a node and you drag the other end of the arrow. It will work on rounded node corners, etc. You pass it a QGrpahicsItem's shape(), which is in item's local coordinates, so point must also first be in the item's local coordinates or you must map it there (mapToItem, mapFromParent, mapFromScene, etc).

Python:

def closest_point_on_path(point:QPointF, path:QPainterPath) -> QPointF:
    if path.isEmpty():
        return point

    vec = QVector2D(point)
    poly = path.toFillPolygon()
    minDist = sys.float_info.max

    for k in range(poly.count()):
        p = QVector2D(poly.at(k))
        if k == poly.count() - 1:
            k = -1 
        q = QVector2D(poly.at(k+1))
        v = q - p
        u = v.normalized()
        d = QVector2D.dotProduct(u, vec - p)

        if d < 0.0:
            d = (vec - p).lengthSquared()
            if d < minDist:
                minDist = d
                minVec = p
        elif d*d > v.lengthSquared():
            d = (vec - q).lengthSquared()
            if d < minDist:
                minDist = d
                minVec = q
        else:
            u *= d
            u += p
            d = (vec - u).lengthSquared()
            if d < minDist:
                minDist = d
                minVec = u

    if minDist >= sys.float_info.max:
        return point

    return minVec.toPointF()

Shortest distance between a QPainterPath and a QPoint

2 Answers2

Python: