QPainterPath和QPoint之间的最短距离

Question

我有一个QPainterPath，可以保存任何线段和/或三次贝塞尔曲线的序列。现在，我有一个QPoint，需要计算QPainterPath与该点之间的最短距离。由于路径本身除了按顺序存储元素之外并没有做更多的事情，所以它本身不提供这样的功能。我唯一想到的办法是使用QPainterPath::toFillPolygon()构造多边形，但有时会返回等于路径的多边形，有时则返回空白的多边形。此外，QPolygonF对象只是一些点的列表，其中一些点通过线连接，而原始路径中有一些点是未连接的，但我无法确定哪些点是连接的，哪些点是未连接的。

是否存在（简单的）解决方案来计算QPainterPath（最好不要转换为多边形）与QPoint之间的最短距离？

- msrd0

---

重复问题在http://www.qtcentre.org/threads/31451-How-to-find-the-nearest-point-on-a-QPainterPath，但没有解决方案（简单或其他）。 - eclarkso

@eclarkso：引用答案并将其作为答案在此处。 - user2249683

@DieterLücking，正如eclarkso所写的那样，在这些问题中没有答案（至少在他链接的那个和我使用搜索引擎找到的问题中没有）。 - msrd0

Answer 1

QPainterPath有 pointAtPercent()，所以你可以在给定步骤上迭代路径并检查位于路径上的一些点与目标点之间的距离。

这将大致给出最短距离，如果您想要更高的精度，可以关注路径的那些线段，并以更细的步骤进行迭代。

- dtech

---

谢谢，这种方法对于近似距离来说肯定是可以的，尽管我更想要一个精确的解决方案。如果没有更好的解决方案，我会采用这个方案。 - msrd0

如果是直线或弧线，您可以精确计算它，但如果有贝塞尔曲线，则始终使用线段进行近似处理。 - dtech

我知道并不喜欢通过仅使用线条获取多边形的方式，但你也可以获得贝塞尔曲线的函数，尽管我认为我读过这是一个五次多项式解决方案，我绝对不想解决它... - msrd0

Answer 2

将此代码片段放入您的utility.cpp或geom_tools.cpp中。它旨在成为一个通用工具，因此不应该放在自定义QGraphicsItem子类中。

 #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();
}

这将导致非常平滑的操作，例如如果需要将箭头附加到节点并拖动箭头的另一端。它可以在圆角节点上工作等。您需要传递一个QGrpahicsItem的shape()，该形状位于项目的本地坐标中，因此point也必须首先在项目的本地坐标中或者您必须将其映射到那里（mapToItem，mapFromParent，mapFromScene等）。

---

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

- D Left Adjoint to U