15,662,668 members
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
Updated 21-Apr-11 3:14am
v3
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.

Solution 2

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.

v3
Sergey Alexandrovich Kryukov 20-Apr-11 18:04pm
Hi Bob. This answer is better because you limit the class of curves to be considered. Note, that the answer is not possible because OP did not specify it.
Please see my other notes. I voted 5 because the problem is not so simple and you did not say anything wrong. All your notes are valid and useful.
--SA
BobJanova 20-Apr-11 18:45pm
True, but, it's posted in a C# forum, so I reckon assuming cubic Bézier curve segments is pretty safe. This method works in the general case as long as you can generate the curve segment bounding box, but for some curve types it will be possible to find the closest approach directly which is obviously better if possible.
Sergey Alexandrovich Kryukov 20-Apr-11 21:54pm
The only difference is: you assumed this and explicitly explained it, tnd2000 just put some expressions. That's why what you posted makes sense.
--SA
BobJanova 21-Apr-11 11:41am
Turns out the assumption was wrong ;) but I think the method still works, since all it assumes is that you can walk the curve segments and calculate their bounding boxes.
Sergey Alexandrovich Kryukov 21-Apr-11 16:41pm
Really?! OK, you give the idea how to solve it anyway I guess.
:-)
--SA

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)

#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).

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'.

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