7
\$\begingroup\$

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 ?

\$\endgroup\$
  • 4
    \$\begingroup\$ What is your question? \$\endgroup\$ – Olivier Jacot-Descombes Sep 3 at 14:51
  • 1
    \$\begingroup\$ @OlivierJacot-Descombes this website is for code review and improvements suggestion right? \$\endgroup\$ – Waleed Sep 3 at 15:02
  • 6
    \$\begingroup\$ Are you questioning the interpolation method, the code quality, memory or time efficiency, correctness or something, else? \$\endgroup\$ – Olivier Jacot-Descombes Sep 3 at 15:15
  • 3
    \$\begingroup\$ First of all, which distances are we talking here? If it's on the order of meters or kilometers, that's probably fine. But if you want to show the movement across hundreds or thousands of kilometers, linear interpolation won't work: the shortest path is a geodesic instead of a straight line, and if the route happens to cross the 180 meridian (e.g. Japan to Hawaii), you'll end up going the wrong way all around the globe. \$\endgroup\$ – IMil Sep 4 at 0:33
  • \$\begingroup\$ Also, to make it smooth, you could a variable divider. Start slow at x1, y1, accelerate, brake, stop at x2, y2. \$\endgroup\$ – Eric Duminil Sep 4 at 11:38
6
\$\begingroup\$

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)
};
\$\endgroup\$
  • 1
    \$\begingroup\$ Very acute observation. \$\endgroup\$ – Henrik Hansen Sep 3 at 17:17
  • 3
    \$\begingroup\$ @HenrikHansen there is actually a very nice pattern you can make here by wrapping a dictionary of (double,double) in a function that performs inter- and extrapolation when a requested value is not cached in the dic. this way you could do var f = pointsDic.ToFunction(); var x = 1.16f; var y = f(x); etc without having to worry whether x is observed in the dictionary. \$\endgroup\$ – dfhwze Sep 3 at 17:21
5
\$\begingroup\$
  • 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.
\$\endgroup\$
  • \$\begingroup\$ Do you see a case for the parentheses for readability? \$\endgroup\$ – dfhwze Sep 3 at 15:41
  • 2
    \$\begingroup\$ Parentheses can enhance readability if the expression mixes different types of operators like shift operators, arithmetic operators and others, where the operator precedence might not be obvious at a first glance, since C# has a lot of levels of precedence. In this specific case, I don’t see any advantage for parentheses. \$\endgroup\$ – Olivier Jacot-Descombes Sep 3 at 15:55
  • 2
    \$\begingroup\$ I do see advantage in parenthesses. You don't have to remember the operator precedence and any differences between languagues. You just set them the way you want them to work and you're done. No need to study the docs. cc @dfhwze :P \$\endgroup\$ – t3chb0t Sep 3 at 16:26
  • 2
    \$\begingroup\$ @t3chb0t I've had several discussions about the use of parentheses. And in the end we could argue that: (raganwald.com/2016/03/17/…). \$\endgroup\$ – dfhwze Sep 3 at 16:30
  • 1
    \$\begingroup\$ In addition to the == there's another minor issue of approximate floating-point computations. When you divide the value by, say, 1000 and then add the result a thousand times, you are not guaranteed to get the exact same value: small rounding errors accumulate. So the comment "last coordinate in the list will be equal to point 2" is actually wrong, though the difference will probably be negligible. \$\endgroup\$ – IMil Sep 4 at 0:20
4
\$\begingroup\$

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
    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Linear interpolation \$\endgroup\$ – Henrik Hansen Sep 3 at 15:27
4
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.