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?

Answer 1

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()

Answer 2

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.