cyclic_interpolation.py

#!/usr/bin/env python

# Circle runs from 0 to 99
CIRCLE_SIZE = 100
FIX_POINTS = [
  (10, 50),
  (25, 25),
  (30, 25),
  (40, 1025),
  (75, 525),
  (80, 30),
  (90, 100)
]

# Assumptions: FIX_POINTS non empty
# Undefined: Behaviour for points outside [0,CIRCLE_SIZE-1]

def get_fixpoint_at(x):
  """
    Helper Method: If there is a fix point at exactly position `x`, return it,
    otherwise return None
  """
  assert x >= 0
  assert x < CIRCLE_SIZE
  assert CIRCLE_SIZE > 0

  re = filter(lambda l: l[0] == x, FIX_POINTS)
  if len(re) > 0:
    return re[0]
  else:
    return None

def get_fixpoint_before(x):
  """
    Helper Method: Find the fix point directly before the provided x value.
    This takes into account the wrapping around on the x axes.
  """
  assert len(FIX_POINTS) > 0
  assert x >= 0
  assert x < CIRCLE_SIZE
  assert CIRCLE_SIZE > 0

  while True:
     fixpoint = get_fixpoint_at(x)
     if fixpoint:
       return fixpoint
     
     x = x - 1
     if x < 0:
       x = CIRCLE_SIZE - 1

def get_fixpoint_after(x):
  """
    Helper Method: Find the fix point directly after the provided x value.
    This takes into account the wrapping around of the x axes.
  """
  assert len(FIX_POINTS) > 0
  assert x >= 0
  assert x < CIRCLE_SIZE
  assert CIRCLE_SIZE > 0

  while True:
     fixpoint = get_fixpoint_at(x)
     if fixpoint:
       return fixpoint
     
     x = x + 1
     if x >= CIRCLE_SIZE:
       x = 0

def interpolate_value(x):
  """
    Interpolates the value at the provided x-value. It uses the FIX_POINTS
    for the interpolation and assumes that x wraps around at CIRCLE_SIZE.
    So the x-axis runs from 0 to CIRCLE_SIZE - 1
  """
  assert len(FIX_POINTS) > 0
  assert x >= 0
  assert x < CIRCLE_SIZE
  assert CIRCLE_SIZE > 0

  before = get_fixpoint_before(x)
  after = get_fixpoint_after(x)  

  # If we are directly on a fix point, return it
  # In this case before == after == x
  if x == before[0]:
    return before[1]

  # Compute Slope
  if before[0] > after[0]:
     # Wrap Around case: The delta on the x scale has to take
     # into account the wrapping around.
     delta_x = (CIRCLE_SIZE - before[0]) + after[0]
  else:
    # Normal Case
    delta_x = after[0] - before[0]
  delta_y = after[1] - before[1]
  slope = float(delta_y) / float(delta_x)

  # Compute Increment
  if (before[0] > after[0]) and (x < before[0]):
    # Wrap Around Case, after the wrap-around of the circle
    increment = ((CIRCLE_SIZE - before[0]) + x) * slope
  else:
    increment = (x - before[0]) * slope

  return before[1] + increment

import unittest
class TestHelpers(unittest.TestCase):
  def test_get_fixpoint_at_positive(self):
    for (p, v) in FIX_POINTS:
      self.assertEqual(get_fixpoint_at(p), (p, v))

  def test_get_fixpoint_at_negative(self):
    self.assertIsNone(get_fixpoint_at(11))
    self.assertIsNone(get_fixpoint_at(0))

  def test_get_fixpoint_before_simple(self):
    # If you are on a fix point, this point is taken
    for (p, v) in FIX_POINTS:
      self.assertEquals(get_fixpoint_before(p), (p, v))

    self.assertEquals(get_fixpoint_before(15), (10, 50))
    self.assertEquals(get_fixpoint_before(24), (10, 50))
    self.assertEquals(get_fixpoint_before(34), (30, 25))
    self.assertEquals(get_fixpoint_before(83), (80, 30))
    self.assertEquals(get_fixpoint_before(92), (90, 100))

  def test_get_fixpoint_before_wrap_around(self):
    self.assertEquals(get_fixpoint_before(3), (90, 100))
    self.assertEquals(get_fixpoint_before(9), (90, 100))

  def test_get_fixpoint_after_simple(self):
    # If you are on a fix point, this point is taken
    for (p, v) in FIX_POINTS:
      self.assertEquals(get_fixpoint_after(p), (p, v))

    self.assertEquals(get_fixpoint_after(1), (10, 50))
    self.assertEquals(get_fixpoint_after(24), (25, 25))
    self.assertEquals(get_fixpoint_after(34), (40, 1025))
    self.assertEquals(get_fixpoint_after(78), (80, 30))
    self.assertEquals(get_fixpoint_after(83), (90, 100))

  def test_get_fixpoint_before_wrap_around(self):
    self.assertEquals(get_fixpoint_after(91), (10, 50))
    self.assertEquals(get_fixpoint_after(99), (10, 50))


class TestCircleInterpolation(unittest.TestCase):
  def test_fixpoints(self):
    # All the fixpoints should return their values
    for (p, v) in FIX_POINTS:
      self.assertEqual(interpolate_value(p), v)

  def test_simple(self):
      self.assertEqual(interpolate_value(13), 45)
      self.assertEqual(interpolate_value(22), 30)

      self.assertEqual(interpolate_value(26), 25)       
      self.assertEqual(interpolate_value(29), 25)       

      self.assertEqual(interpolate_value(31), 125)
      self.assertEqual(interpolate_value(32), 225)
      self.assertEqual(interpolate_value(38), 825)
      self.assertEqual(interpolate_value(39), 925)

      self.assertAlmostEqual(interpolate_value(55), 810.71, 2)
      self.assertAlmostEqual(interpolate_value(70), 596.428, 2)

      self.assertEqual(interpolate_value(76), 426)
      self.assertEqual(interpolate_value(77), 327)
      self.assertEqual(interpolate_value(78), 228)
      self.assertEqual(interpolate_value(79), 129)

      self.assertEqual(interpolate_value(85), 65)
      self.assertEqual(interpolate_value(88), 86)
      self.assertEqual(interpolate_value(89), 93)

  def test_wraparound(self):
      self.assertEqual(interpolate_value(91), 97.5)
      self.assertEqual(interpolate_value(92), 95)
      self.assertEqual(interpolate_value(93), 92.5)
      self.assertEqual(interpolate_value(94), 90)
      self.assertEqual(interpolate_value(95), 87.5)
      self.assertEqual(interpolate_value(96), 85)
      self.assertEqual(interpolate_value(97), 82.5)
      self.assertEqual(interpolate_value(98), 80)
      self.assertEqual(interpolate_value(99), 77.5)
      self.assertEqual(interpolate_value(0), 75)
      self.assertEqual(interpolate_value(1), 72.5)
      self.assertEqual(interpolate_value(2), 70)
      self.assertEqual(interpolate_value(3), 67.5)
      self.assertEqual(interpolate_value(4), 65)
      self.assertEqual(interpolate_value(5), 62.5)
      self.assertEqual(interpolate_value(6), 60)
      self.assertEqual(interpolate_value(7), 57.5)
      self.assertEqual(interpolate_value(8), 55)
      self.assertEqual(interpolate_value(9), 52.5)

if __name__ == '__main__':
    unittest.main()