Generate points for smooth movement between two given points

Question

This is one of the methods in a project for generating points between two given points. We add points of route with a 25ms delay in an array and a camera on Google Maps is always at the last point. So we need to move it smoothly. This method adds those extra points between any two given points to make it move smoothly.

public List<Tuple<double, double>> GeneratePointsForSmoothMovement(double x1, double y1, double x2, double y2, double divider)
{
    // If points are same, return empty list
    if (x1 == x2 && y1 == y2)
        return new List<Tuple<double, double>>();

    // get difference between x and y cordinates
    double xi = (x2 - x1);
    double yi = (y2 - y1);

    // divide difference into n parts
    xi = xi / divider;
    yi = yi / divider;

    // set new temp vars equal to first point
    double xf = x1;
    double yf = y1;

    // initialize list to save new points
    List<Tuple<double, double>> points = new List<Tuple<double, double>>();

    // increment temp vars by difference-division parts
    for (int i = 0; i < divider; i++)
    {
        xf += xi;
        yf += yi;

        points.Add(Tuple.Create(xf, yf));
    }

    // last cordinate in the list will be equal to point 2
    // return
    return points;
}

Is this the most efficient way ?

Answer 1

Dividor

dividor is ill-defined. It acts as a factor for quantization:

 xi = xi / divider;

But also as threshold for yielding smoothed results:

for (int i = 0; i < divider; i++)

While this seems fine if dividor is \$integer >= 2\$, it could yield unwanted results for fractions (as it is a double precision integer). I would at least change its type to int or uint instead and add an out-of-bound guard. If you would decide to allow fractions, make it clear in the spec how the edge case near the end is handled, since you might get a scenario where you don't synchronize with the end value.

---

Usability

GeneratePointsForSmoothMovement is a low level generator. The caller code should still think about technical parameters to provide. And if a caller requires several levels of smoothness, multiple calls with different parameters have to be executed. In order to provide the consumer a solution that avoids most overhead, you could write an extension method on IEnumerable<Tuple<Double,Double>> and preferrably also on IDictionary<Double,Double> for faster lookup.

In pseudo code:

public static Func<Double, Double> ToContinuousFunction(
    this IDictionary<Double,Double> points)
{
    return new Func<Double, Double>(x => 
    {
        if (points.TryGetValue(x, out var y))
        {
            return y;
        }

        // .. perform lineair interpolation or extrapolation based on nearby points
    });
}

Let's say we have points (x: 1, y: 10) and (x: 2, y: 20):

var f = points.ToContiniousFunction();
var yValues = new [] 
{
    f(1)    // 10  (from cache)
   ,f(1.5)  // 15  (interpolation)
   ,f(2)    // 20  (from cache)
   ,f(3)    // 30  (extrapolation)
};

Answer 2

• The Tuple<T1, T2> type is a reference type requiring to create objects on the heap, what puts strain on the GC. Use a value type, i.e. a struct type. Use the new ValueTuple type or an existing point or vector type or create your own struct. In public API's dedicated types are preferred over tuple types.

• You are testing x1 == x2 && y1 == y2. This is a bit hazardous, since double values are subject to tiny rounding errors. Define a minimum allowed difference.

  private const double Eps = 1e-6;
  
  if (Math.Abs(x2 - x1) < Eps && Math.Abs(y2 - y1) < Eps) 
  

• Parentheses are superfluous here. The assignment operator has always the lowest precedence (except sequential evaluation with ,).

  double xi = x2 - x1;
  

• You could make the divider dependent on the distance between the points. Doing this creates a more uniform camera speed. If you want to keep the original relative speeds, don't do this.

• Don't repeat long type names. Use var instead.

  var points = new List<Tuple<double, double>>();
  

  When to use var is a matter of preference. My rules are:

  • If the type is explicitly visible (as here after the new keyword) or is otherwise obvious, use var.
  • Don't use var for primitive types like int, string, or double.
  • LINQ expressions often return complex nested types involving IOrderedEnumerable and IGrouping etc. nobody wants to know. These types are mostly used for temporary results either. Use var here.
  • Anonymous types have no name and require var. var a = new { Id = 1, Value = 1.4 };. It's the main reason the var keyword has been introduced.

Answer 3

Make it an enumerator You can make the evaluation lazy and get rid of the intermediate list by changing the return type to IEnumerable<>.

Use named tuples You can make the API more user-friendly by using named tuples. Something like a readonly struct Point would be preferable but if you don't have it or don't want it then named tuples are your best friend.

Interpolation The point generation you're doing is called interpolation. You can use this word in the method name like InterpolateMovement. I don't know if these calculations have any concrete name, but if they have than you may use an even more exact name like InterpolateMovementByAlgorithmName.

Here's an example of how this could look like after implementing the above suggesions:

public IEnumerable<(double X, double Y)> InterpolateMovement(double x1, double y1, double x2, double y2, double divider)
{
    // If points are same, return empty list
    if (x1 == x2 && y1 == y2)
    {
        yield break; // break the enumeration
    }

    // ..

    // increment temp vars by difference-division parts
    for (int i = 0; i < divider; i++)
    {
        xf += xi;
        yf += yi;

        yield return (xf, yf); // <-- return tuples
    }
}

Answer 4

The parameter name divider doesn't say much. I think I would call it numPoints or countOfPoints or numOffsets.

---

List<Tuple<double, double>> points = new List<Tuple<double, double>>();

You know the size of the list, so to improve performance you can set the capacity of the list

List<Tuple<double, double>> points = new List<Tuple<double, double>>(divider);

---

double xi = (x2 - x1);
double yi = (y2 - y1);

// divide difference into n parts
xi = xi / divider;
yi = yi / divider;

can be done more elegantly:

double xi = (x2 - x1) / divider;
double yi = (y2 - y1) / divider;