4
\$\begingroup\$

I implement the following algorithm in order to find a point from a given X value in a sorted list with the same distance between each X values. Here's an example of my list content with a delta of 10:

(687;10)
(12;20)
(24;30)
(10125;40)
(0;50)
(111;60)
(-2;70)
  • The delta can be any float number;
  • The list can be up to 2.000.000pts so it needs to be as fast as possible;
  • I can't change the type of the points container (IPointList from ZedGraph).

Here's the code:

private ZedGraph.PointPair findPoint(ZedGraph.CurveItem curve, double x) 
{
    if (curve.NPts == 1)
        return curve.Points[0];

    // Look for the min and max value
    double min = curve.Points[0].X;
    double max = curve.Points[curve.NPts - 1].X;

    double delta = curve.Points[1].X - min;

    // Prevent error if mouse is out of bounds.
    if (x > max)
        x = curve.Points[curve.NPts - 1].X;
    else if (x < min)
        x = curve.Points[0].X;

    double index = (x - min) / delta;
    int nearestIndex = (int)Math.Round(index, 0);

    if (nearestIndex < curve.NPts)
    {
        return curve.Points[nearestIndex];
    }
    return curve.Points[curve.NPts - 1];
}
\$\endgroup\$
  • \$\begingroup\$ Ugh, IPointList doesn't implement IEnumerable<PointPair> or even IEnumerable. I assume you can't just add that to IPointList? \$\endgroup\$ – svick Dec 22 '14 at 19:28
4
\$\begingroup\$

The NPts == 1 case shouldn't need to be handled separately. The min-max clamping should take care of it, if you write it smartly (using <= and >= tests).

The min-max clamping should should do a short-circuit return.

Once clamped, there shouldn't be any need to test if (nearestIndex < curve.NPts).

I would prefer to calculate the delta based on the min and max, for better precision. Extrapolating based on Points[1].X - Points[0].X could let floating-point inaccuracies accumulate.

A sanity check before returning the value might be a good idea — it's up to you depending on how much you trust the data.

private ZedGraph.PointPair findPoint(ZedGraph.CurveItem curve, double x) 
{
    // Look for the min and max value
    double min = curve.Points[0].X;
    double max = curve.Points[curve.NPts - 1].X;

    // Prevent error if mouse is out of bounds.
    if (x <= min) return curve.Points[0];
    if (x >= max) return curve.Points[curve.NPts - 1];

    double delta = (max - min) / (curve.NPts - 1);
    int index = (int)Math.round((x - min) / delta, 0);

    Debug.Assert(Math.Abs(x - curve.Points[index].X) <= delta / 2, "Interpolation error");
    return curve.Points[index];
}
\$\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.