Sorting Circles 3: Implementation

To finish off the last two posts, here is an implementation of the circle sorting algorithm as a Python script. The method, order_circles, accepts as input the x, y and quadrance of two circles, and returns -1 if C₁ < C₂, or returns 0 if C₁ = C₂, or returns 1 if C₁ > C₂. The ordering is based on descending order of the circle bottoms, but the x-coordinate is used as a tiebreaker.

This design is slightly different than a native speaker of Python might design it: they would typically implement the algorithm as a true/false result depending on whether C₁ < C₂. I implemented the three-return-code result for two reasons: I am a native C# speaker, where the IComparable interface rules, and because I found the Python way to be a bit less elegant when I was implementing the tiebreaker code. It's trivially easy to convert my answer to the Python one, if you are so inclined.

CIRCLE_1_FIRST = -1
CIRCLES_EQUAL = 0
CIRCLE_2_FIRST = 1

def order_circles(x1, y1, q1, x2, y2, q2):
 result = order_circle_bottoms(y1, q1, y2, q2)
 
 if result == CIRCLES_EQUAL:
  result = order_numbers(x1, x2)

 return result


def order_circle_bottoms(y1, q1, y2, q2):
 if q1 == q2:
  return order_numbers(y2, y1)
  
 if q1 < q2:
  yS,qS = y1,q1
  yL,qL = y2,q2
  invert = 1
 else:
  yS,qS = y2,q2
  yL,qL = y1,q1
  invert = -1
  
 if yS >= yL:
  return CIRCLE_1_FIRST * invert
 elif pow(yL - yS, 2) > qL:
  return CIRCLE_2_FIRST * invert
 else:
  yC = (pow(yS, 2) - pow(yL, 2) + qL - qS) / (2 * (yS - yL))
  return order_numbers(qS, pow(yC - yS, 2)) * invert


def order_numbers(a, b):
 if a < b:
  return CIRCLE_1_FIRST
 elif a > b:
  return CIRCLE_2_FIRST
 else:
  return CIRCLES_EQUAL

#------------------------------------------------------------------------------------

def test_case(desc, x1, y1, q1, x2, y2, q2, expected):
 if (order_circles(x1, y1, q1, x2, y2, q2) == expected and
  order_circles(x2, y2, q2, x1, y1, q1) == -expected):
  print('PASS\t' + desc)
 else:
  print('!FAIL!\t' + desc)
 
test_case('Equal circles', 0, 0, 4, 0, 0, 4, CIRCLES_EQUAL)
test_case('Same size circles', 0, 1, 4, 0, 0, 4, CIRCLE_1_FIRST)
test_case('Same center circles', 0, 0, 1, 0, 0, 4, CIRCLE_1_FIRST)
test_case('Smaller circle higher', 0, 10, 1, 0, 0, 4, CIRCLE_1_FIRST)
test_case('Smaller circle beneath larger', 0, 0, 4, 0, -10, 1, CIRCLE_1_FIRST)
test_case('Smaller circle inside larger', 0, 0, 1, 0, 5, 100, CIRCLE_1_FIRST)
test_case('Smaller circle poking out of larger', 0, 3, 16, 0, 0, 4, CIRCLE_1_FIRST)
test_case('Unequal circles tangent', 0, 1, 1, 0, 2, 4, CIRCLES_EQUAL)
test_case('Equal circles x order', 0, 0, 4, 1, 0, 4, CIRCLE_1_FIRST)
test_case('Unequal circles tangent x order', 0, 1, 1, 1, 2, 4, CIRCLE_1_FIRST)