title: Piecewise linear integer curve interpolation in C#/Unity3D
body: <p>Is there a simple, efficient way to implement a piecewise linear integer-to-integer curve interpolation in C# (for Unity3D, if it matters) ?<br>
  Details are as follows:</p>
  
  <ul>
  <li>The piecewise linear curve representation has to be built over time. The first interpolation request comes before we have all data points</li>
  <li>The curve is strictly monotonous</li>
  <li>The first point is always (0, 0)</li>
  <li>The data points' first coordinates are also strictly monotonous w.r.t arrival time, i.e. the points are naturally ordered by their first coordinate.</li>
  <li>The data points are not in ranges that would cause cause overflow problems for 4-byte integers</li>
  <li>The output does not have to be 100% accurate, so rounding errors are not an issue.</li>
  </ul>
  
  <p>In C++, I would do something like this:</p>
  
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;cassert&gt;
  
  using namespace std;
  
  typedef pair&lt;int, int&gt; tDataPoint;
  typedef vector&lt;tDataPoint&gt; tPLC;
  
  void appendData(tPLC&amp; curve, const tDataPoint&amp; point) {
    assert(curve.empty() || curve.back().first &lt; point.first);
    curve.push_back(point);
  }
  
  int interpolate(const tPLC&amp; curve, int cursor) {
    assert(!curve.empty());
    int result = 0;  
    // below zero, the value is a constant 0
    if (cursor &gt; 0) {
      // find the first data point above the cursor
      const auto upper = upper_bound(begin(curve), end(curve), cursor);
      // above the last data point, the value is a constant 0
      if (upper == end(curve)) {
        result = curve.back().second;
      } else {
        // get the point below or equal to the cursor
        const auto lower = upper - 1;
        // lerp between
        float linear = float((cursor - lower.first) * (upper.second - lower.second)) / (upper.first - lower.first);
        result = lower.second + int(linear);
      }
    }
    return result;
  }
  </code></pre>
  
  <p>I can see how I could do something that work sort of like this in C#, but nothing as concise or efficient. Any help will be appreciated.</p>
  
  <p>EDIT:
  I do not need to be more accurate, and am perfectly happy with piecewise linear interpolation, so better interpolation quality is not my problem here.<br>
  What I am looking for is an efficient, concise way of doing this. By efficient, I mean things like: relying on the fact that the data points are naturally ordered to be able to use binary search to find the proper segment</p>