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\$
1
  • \$\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, 2014 at 19:28

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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