How to determine the shortest distance from a point to a curve

Question

0.00/5 (No votes)

See more:

In C++ MFC or C#.
first, I draw a line, which consists of continuous straight lines and curves. the equations of straight lines and curves are given.
then , there are some points near the line above,
my question is how to deterimine the shortes distance between the points and the line in C++ or C#.
I know it's very simple in AutoCAD, but I cannot figure it out in C++ or C#.
Thanks very much, guys, I need your help

Maybe I didnot express clearly.
I met a problem in a train construction project. The train line designed consists of continuous straight lines and curves. Circular curve and easement curve are often used. Every curve is given in ‎analytical equations.
(easement curve: A curve, as on a highway, whose degree of curvature is varied to provide a gradual transition between a tangent and a simple curve, or between two simple curves which it connects. Also known as transition curve).
Then I measured some points along the train line, I need to know the distance between the points i measured and the designed line.
By AutoCAD, i can draw the designed line, and also my points. It's very simple to find the shortest distance.
But I cannot solve it in C++ or C#. Is there any way to catch every point or line i drawed on the screen?

PS, the train line if often horizontal or vertical,

Posted 19-Apr-11 23:40pm

ming596

Updated 21-Apr-11 3:14am

v3

Add a Solution

Comments

BobJanova 21-Apr-11 9:12am

According to Wikipedia, transition curves are segments of an Euler spiral, which has an ugly parametric representation and I doubt you can calculate it analytically. However, determining the bounding box for such a curve is easy (it is the triangle formed by the two and points, and the intersection of the continuation of the straight line tangent at each end). I believe my solution will work well for this case, as the track won't have crossovers or loops that make the point close to more than one (or maybe two) curve segments.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

BobJanova · Answer 1 · 2011-04-20T04:00:00

Closest point to a Bézier curve segment seems not to be possible analytically.[^] So you will need to do some iteration.

Here's how I would tackle it. First, find the closest approach of the target point to each of the line segments, which is a well known algorithm. To quote myself:

Point-line closest approach: to find the point on a line segment (p1 to p2) that is the closest to another point (q) in space. First, find how far along the line the point will be: f = [(q-p1).(p2-p1)]÷|p2-p1|². If f is less than zero, then q is off the 'beginning' of the line and the closest point is p1; likewise, if f>1, the closest point is p2. Otherwise, q is alongside the line segment and the closest point is p1+f(p2-p1).

Then, find the closest point on the bounding polygon of each of the curve segments (defined by the four control points). If the point is within the bounding polygon of a segment, give that segment a distance value of 0.

If the smallest value is for a line segment, you have the closest approach. If it is for a curve segment, walk along the curve to find the minimum, using a step size appropriate for your problem. If the smallest value is shared, you may need to walk more than one curve segment. But you won't need to walk the whole path.

Edit: In certain pathological cases, the point may be inside one or more curve bounding boxes, but closest to a line. So once you have found the real closest approach for each curve segment that has a lower distance value than the smallest line, by walking the segment, you need to check if the real distances are still lower than the smallest line.

In addition, the point can be close to the bounding box of a curve, but not to the curve itself. You should therefore also store the maximum distance to a point in the curve's bounding box, and walk all curves with a minimum value less than (i) the smallest distance-to-line for a line segment and (ii) the maximum distance for the curve(s) with the smallest minimum value. In the extreme case of a path which is 100% curves, all of which have large bounding boxes and are near to each other, this may mean you will still have to walk the entire path.

tnd2000 · Answer 2 · 2011-04-20T08:19:00

Solution 3

You'll need calculus to do this. If given point (a,b) and y=f(x) then calculate the distance between (a,b) and (x,y) using the equation s = sqrt( (a-x)^2 + (b-y)^2) ) then find ds/dx and set it as 0 and solve for x.
Ex
Given point (3,2) and curve y=x^2 + 2
then
s = sqrt( (3-x)^2 + (2- (x^2 + 2))^2 )
s = sqrt(9 - 6*x + x^2+ x^4)
ds/dx = 1/2*(-6+2*x+4*x^3)/sqrt(9 - 6*x + x^2+ x^4)
set ds/dx to 0 and solve for x
0 = 1/2*(-6+2*x+4*x^3)/sqrt(9 - 6*x + x^2+ x^4)
x=1
then solve for y in y=x^2+2, y = 3
so (1,3) is the point on the curve that's closet to (3,2)
solving for s in the original equation, the shortest distance between (3,2) and y=x^2 + 2 is sqrt(5)

Posted 20-Apr-11 8:19am

tnd2000

Comments

#realJSOP 20-Apr-11 14:28pm

I have no idea if the math is right, but it looks complicated enough to be correct, so I give you a 5. If this were on a whiteboard of mine, it would be comprised of a simple square with the words "Magic Happens Here" inside the square. :)

Sergey Alexandrovich Kryukov 20-Apr-11 18:00pm

I don't want to down-vote it (because a part of this work can be quite useful), but is simply cannot be all correct. Here is why: neither OP nor tnd2000 described any assumption on the class of curves considered. What do you assume: circles, Besier, spirals, polynomial splines, what?

No...

Also: do you call ***this*** "calculus"?! Oh, I did not know mathematical education degradation is so deep. It used to be called "elementary mathematics", later "pre-calculus", now what?! For your information, even "real" calculus (with derivatives/integrals) is not considered as a real mathematics by many decent people.

--SA

tnd2000 21-Apr-11 12:33pm

I simply provided a means for it to calculated and gave an example. The OP said there are straightlines and curves and every curve had an equation to go with it. And yes it does work with a circle or whatever else as long as there is a mathmatical equation for it.
I am not going to discuss what is considered calculus.

Sergey Alexandrovich Kryukov 21-Apr-11 16:42pm

Sure. Great. So what was you assumption on the class of curves considered? I still did not get it. What is you "curve"?
Thank you.
--SA

CPallini 21-Apr-11 2:39am

Good, even if SA doesn't appreciate you use of the 'calculus' term. Please note you may drop the square root from the distance formula (after all you're just finding the minimum).

CPallini · Answer 3 · 2011-04-19T23:54:00

Solution 1

Just minimize the distance function between the points and each of the curves, then, choose, for every point, the 'minimum of the minima'.

Posted 19-Apr-11 23:54pm

CPallini

Comments

Sergey Alexandrovich Kryukov 20-Apr-11 18:02pm

Everyone understand that, but how? The correct answer is: impossible to answer before OP specifies the class of curves to be considered.
--SA

CPallini 21-Apr-11 2:43am

Is is not impossible at all. The aren't just analytical methods to find minimum distance (and who knows, the OP might be pleased by local minima). Anyway, I agree, the problem, as it stands, is not clearly stated.

Sergey Alexandrovich Kryukov 21-Apr-11 3:06am

It is impossible in only one sense: the question is not completely formulated. Of course, depending on the set of curves (say, just Bezier), it can have analytical solution... I think after some thinking I can give an example of equations which do not have analytical solution (but can be rendered on screen, solved digitally with approximation, etc.)
--SA

How to determine the shortest distance from a point to a curve

3 solutions

Solution 2

Solution 3

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us