2

The curve is in fact the trajectory of a bus, the curve is represented by many (up to a few thousand) discrete points on the curve (the points were recorded by a GPS device installed on the bus). Input a point P, I need to find the closest point on the curve to the point P. The point P is usually no more than 30m away from the trajectory of the bus. Note, the closest point isn't necessary a point recorded by the GPS device, it could be a point somewhere between two recorded points.

First I need an algorithm to recover the trajectory from those recorded points. It would be great if the interpolated curve could show sharp turns made by the bus. Which curve is best for such task ? Is Bezier curve good enough ? And finally I have to calculate the closest point on the curve, of course the algorithm completely depends on the kind of curve chosen.

I'm doing some research, and don't have much knowledge in curve interpolation, so any suggestions are welcome.

user416983
  • 974
  • 3
  • 18
  • 28
  • 1
    There are many possible options but the answer mostly depends on what you are planning to use the curve for. In many scenarios a simple polyline interpolation would do the job. – Tomasz Lenarcik Aug 15 '15 at 23:27
  • I would use [piecewise interpolation cubics](http://stackoverflow.com/a/30438865/2521214) ... for the point finding just find 4 consequent closest points to it and interpolate the point ... – Spektre Aug 16 '15 at 07:38
  • cf. https://en.wikipedia.org/wiki/Cubic_Hermite_spline – Will Ness Aug 16 '15 at 13:38

1 Answers1

2

For computing the trajectory from recorded points, I recommended using the centripetal or chord-length Catmull-Rom splines. See link for more details. Catmll-Rom splines are in fact special cubic Hermite curves, which can be easily converted into cubic Bezier curves. Please note that the result from Catmull-Rom spline is a G1 curve only in general. If you want the trajectory to be with higher continuity (such as C2), you can go with natural cubic splines or general B-spline interpolation. Whatever approach you take, it is advised to keep the spline's degree no higher than 5. Degree 3 is a popular choice.

Once you have the mathematical representation for the trajectory, you can compute the minimum distance between a given point P and the trajectory. In general, the squared distance between point P and a curve C(t) is represented as D(t) = |P-C(t)|^2. The minimum of D will happen at where its first derivative is zero, which means we have to find the root for the following equation:

dD/dt = 2*(P-C(t)).C'(t) =0

When C(t) is of degree 3, dD/dt will be of degree 5. This is the reason why it is recommended to use a low degree curve earlier.

There are many literatures or online materials talking about how to find the root of a polynomial (of any degree) efficiently and robustly. Here is another SO post that might be useful.

Community
  • 1
  • 1
fang
  • 3,473
  • 1
  • 13
  • 19