title: Multilinear Interpolation for unknown number of points in n dimensions
body: <p>I'm currently trying to create a method which can make a multilinear interpolation for an unknown number of points (the number is equal to 2^n) in n-dimensional space.</p>
  
  <p>The cases for n = 1 (no interpolation) and n = 2 (linear interpolation) are already implemented and seem to work. But now I'm already struggling to make the bilinear interpolation (for the case n = 4) dimension agnostic and I have no idea how I should progress from that point on (n = 8, ..., 2^n).</p>
  
  <p>Is there a general approach for this problem or should I hardcode some of the cases and throw an UnsupportedOperationException otherwise? </p>
  
  <p>Below I added an SSCCE which should hopefully clarify my problem. It consists of a point class which stores the coordinates and a value and also contains some functionality like calculating the distance to another point and the interpolation method which already contains my implementation of the cases for n = 1 and n = 2.</p>
  
  <h2>Code</h2>
  
  <hr>
  
  <pre><code>import java.util.ArrayList;
  import java.util.List;
  
  public class Interpolator {
  
      public static void main(String[] args) {
          Interpolator ip = new Interpolator();
  
          Point currentPoint = new Point(new long[]{5, 5}, 0);
  
          List&lt;Point&gt; neighbors = new ArrayList&lt;Point&gt;() {{
              add(new Point(new long[]{3, 3}, 7));
              add(new Point(new long[]{10, 10}, 4));
          }};
  
          System.out.println(ip.interpolate(currentPoint, neighbors));
      }
  
      public float interpolate(Point currentPoint, List&lt;Point&gt; neighbors) {
  
          if (neighbors.size() == 1) {
              // no interpolation necessary with only one neighbor
              return neighbors.get(0).getValue();
          } else if (neighbors.size() == 2) {
              // distance between point and the two neighbors
              float distanceOne = currentPoint.distance(neighbors.get(0));
              float distanceTwo = currentPoint.distance(neighbors.get(1));
              float completeDistance = distanceOne + distanceTwo;
  
              // calculate weights
              float weightOne = 1 - distanceOne / completeDistance;
              float weightTwo = 1 - distanceTwo / completeDistance;
  
              // linear interpolation
              return neighbors.get(0).getValue() * weightOne
                      + neighbors.get(1).getValue() * weightTwo;
          } else if (neighbors.size() == 4) {
              //TODO: bilinear interpolation
          } else if(neighbors.size() == 8){
              //TODO: trilinear interpolation
          }
  
          //TODO: quadlinear interpolation or higher?
          return -1;
      }
  
      public static class Point {
  
          private long[] m_coordinates;
          private float m_value;
  
          public Point(final long[] coordinates, float value) {
              this.m_coordinates = coordinates;
              this.m_value = value;
          }
  
          public long[] getCoordinates() {
              return this.m_coordinates;
          }
  
          public int numDim() {
              return m_coordinates.length;
          }
  
          public long dim(final int i) {
              return this.m_coordinates[i];
          }
  
          public float distance(final Point otherPoint) {
              if (this.numDim() != otherPoint.numDim()) {
                  throw new IllegalArgumentException(
                          "Can't measure distance between points with different dimensionality");
              }
  
              float sum = 0;
              for (int i = 0; i &lt; this.numDim(); i++) {
                  sum += Math.pow(this.dim(i) - otherPoint.dim(i), 2);
              }
  
              return (float) Math.sqrt(sum);
          }
  
          public float getValue() {
              return m_value;
          }
      }
  }
  </code></pre>
  
  <hr>