I have a set of points on a map (given by x,y coordinates) and I want to find a path between these points. The goal is to have a ship sail this path, so the path can't just be straight lines.
I believe I can calculate the tangent direction or the curve at the given points by looking at the previous and next point, as illustrated below. Since going from point A to B is 100m at an angle of 90° and going from point B to C is 200m at angle 0°, the tangent direction in point B would be $$\frac{100}{100+200} * 90° + \frac{200}{100+200} * 0° = 30°$$
The tangent of the very first point and the very last point would simply be chosen in the direction of the next and previous point respectively. So if there are no other points than A, B and C then the tangent at A would be 90° and the tangent at C would be 0°.
I'm stuck at what to do next.
Preferably I would get a piecewise spline so that the curve between each pair of points can be calculated independently and the entire path doesn't have to be calculated up front, but that is not a requirement.
The special requirement for the curve is that the turns in the curve can't be sharper than a given parameter. The ship has a maximum rate of turn, it can't rotate faster than this maximum. So short U-turns can't exist in the curve.
Is it possible to construct such a curve, given just the points and the maximum curvature (and the speed of the ship if needed)?
If yes, could someone provide the necessary math or at least point me in the right direction?
If not, what other data would I have to provide in order to calculate such a path? If a spline with the maximum curvature restraint can't be calculated then at least I need a method to detect that the curve is too sharp.
Suggestions for solutions where the curve does not go through the points exactly are also welcome, but there would have to be a parameter that controls the maximum distance between the points and the curve (e.g. the curve can't be more than 20 meter away from any point in the input).
Best Answer
It seems to me that what you're trying to do is very similar to the kind of motion planning that's done with robots and automated guided vehicles in the manufacturing industry.
The idea is to plan a path that visits certain points, avoids certain obstacles, and mimimizes the time of travel. The naive minimum distance solution is just a sequence of straight lines. But this requires that the moving thing change direction instantaneously, which is impossible unless it reduces its speed to zero. The minimum time solution is a smooth curve of some kind, but computing it is a pretty difficult optimal control problem.
This is an important problem in manufacturing, and there is a huge body of literature on the subject. There is one paper here, but you'll find hundreds of other ones if you search for terms like "trajectory planning".