[Interest] Distance from point to path.

Jason H jhihn at gmx.com
Tue Dec 29 16:10:45 CET 2015



> Sent: Monday, December 28, 2015 at 4:49 PM
> From: "william.crocker at analog.com" <william.crocker at analog.com>
> To: "interest at qt-project.org" <interest at qt-project.org>
> Subject: [Interest] Distance from point to path.
>
> Hello:
> 
> Given a QPoint and a QPainterPath.
> How do I find the distance from the QPoint to the
> closest point along the QPainterPath.
> 
> I could step along the path with pointAtPercent
> looking for the closest point, but that seems unduly
> expensive: O(100N).
> 
> Any better ideas.

Even 100N is still considered linear, so not that bad, algorithmically speaking. The problem with any approach is you will be very susceptible to local minima unless you can find bounding approximations. I think the approach you have is just fine and cannot be simplified in the general case. If you know more, like if the curve is convex or concave (parabolas, hyperbolas) , you might be able to craft a binary search of log2(n). Also knowing the [ir]regularity would allow you to (discard|include) some segments.




More information about the Interest mailing list