Sorting Circles 2: The Answer

First, we formally state the problem: we are looking for a partial order of a set of circles C_n, defined by a point (X_n, Y_n) and a quadrance Q_n, according to the following relation:

C₁ ≤ C₂ ⇔ Y₂ - sqrt(Q₂) ≤ Y₁ - sqrt(Q₁)

Note carefully that the coeffiecients one one side of the relation are flipped from the other side; this is because the circles are ordered top-to-bottom, so the 'least' circle will be the highest one. Note also that X_n does not appear anywhere in this relation, so without loss of generality, we may assume that X_n = 0. Informally, translation the circles horizontally doesn't affect their order. In practice, we can use the X values of the circle centers as a tiebreaker if the first relation says that the circles would be equal.

Our problem is made more complicated by the fact that we cannot always take the square root of a quadrance, so we seek an algorithm that will give the correct answer without having to leave the domain of natural numbers. We can start with a special case of the two circles being the same size; that is, Q₁ = Q₂. In this case, although we can't take the square root of either, we know that the square root of both is the same, and so we can just subtract whatever its value would be from both sides of the inequality:

C₁ ≤ C₂ ⇔ Y₂ ≤ Y₁

Informally, this case shows that for two circles the same size, then the higher one comes first in the ordering, as in this example:

We can cross off another special case if the two circles are centered at the same height; that is, Y₁ = Y₂:

C₁ ≤ C₂ ⇔ -sqrt(Q₂) ≤ -sqrt(Q₁)
C₁ ≤ C₂ ⇔ sqrt(Q₁) ≤ sqrt(Q₂)
C₁ ≤ C₂ ⇔ Q₁ ≤ Q₂

The last step in this derivation comes from the fact that the square root function is monotonic; that is, x ≤ y ⇔ f(x) ≤ f(y). We can't actually determine the value of the square root, but we don't need the actual value to know which one is greater. Informally, this case shows that for two circles centered at the same height, the smaller one comes first in the ordering, as in this example:

At this point we have exhausted any equivalences between the two circles, so Q₁ ≠ Q₂ and Y₁ ≠ Y₂ for the remainder of this discussion. Let's see if we can make any more progress by rearranging the relation:

C₁ ≤ C₂ ⇔ Y₂ - sqrt(Q₂) ≤ Y₁ - sqrt(Q₁)
C₁ ≤ C₂ ⇔ Y₂ + sqrt(Q₁) - sqrt(Q₂) ≤ Y₁
C₁ ≤ C₂ ⇔ sqrt(Q₁) - sqrt(Q₂) ≤ Y₁ - Y₂

Let us make a few assumptions and see where they lead:

Q1 < Q2 sqrt(Q1) < sqrt(Q2) sqrt(Q1) - sqrt(Q2) < 0

Y2 < Y1 0 < Y1 - Y2

sqrt(Q₁) - sqrt(Q₂) < Y₁ - Y₂
C₁ < C₂

An equivalent derivation will show that Q₂ < Q₁ and Y₁ < Y₂ implies that C₂ < C₁. Informally, this case shows that if the circle with the higher y-coordinate is also smaller, then it comes first in the ordering, as in this example:

We seem to be narrowing in on the answer. At this point, we know that the only unconsidered case is the one where the larger circle has the higher center. That is, Q_L > Q_S and Y_L > Y_S. In actuality, we are still where we started, because even under these constraints, the relative ordering of the two circles could still be any of the three possible answers.

We can knock out one final special case. Make the following assumption, and see where it leads:

Q_L < (Y_L - Y_S)²
sqrt(Q_L) < Y_L - Y_S
Y_S < Y_L - sqrt(Q_L)
Y_S - sqrt(Q_S) < Y_L - sqrt(Q_L)
⇔ C_L < C_S

Informally, we know already that the smaller circle is below the larger one. If the smaller circle is also outside of the larger one (because the squared distance between the two circle centers is larger than the quadrance of the larger circle), then the smaller circle must come second in the order, since its bottom must be lower than that of the larger circle, as in this example:

We are still where we started, though. The smaller circle is centered lower than the larger circle, and is inside it. It may be poking outside of the larger circle though, in which case it should come second in the ordering. It may be fully within the larger circle, in which case it should come first in the ordering. Or it may be the case that the two circles are just touching at their bottoms, in which case the two circles are 'equal' under the ordering. How can we tell?

The answer is to count the number of intersection points between the two circles, after the circles have been translated to have their centres on the Y axis (ie, X = 0). If there are no intersection points, then we have the 'smaller circle inside larger one' case and the smaller circle comes first. If there is one intersection point, then we have the 'circles touching at the bottom' case and they are equal. If there are two intersection points, then we have the 'smaller circle poking out of the larger one' case, and the larger circle comes first.

It is important to note, however, that in order for this answer to be correct, the special cases already proven above have to be ruled out. If the two circles centered on the Y axis meet at exactly one point, then in the general case, the top or bottom of the smaller circle might be touching the top or bottom of the larger circle, for a total of four possibilities. The fact that the smaller circle is centered below the larger one rules out that they are touching at the larger circle's top, and the fact that the smaller circle's center is inside the larger circle rules out that the smaller circle's top is touching the larger circle's bottom.

To find the circle's intersections, we start by observing that the intersections, if any, lie on both circles. The larger circle's points satisfy the equation x² + (y - Y_L)² = Q_L, and similarly, the smaller circle's points satisfy the equation x² + (y - Y_S)² = Q_S. Therefore, we have:

x² + (y - Y_L)² - Q_L = 0 = x² + (y - Y_S)² - Q_S
(y - Y_L)² - Q_L = (y - Y_S)² - Q_S
y² - 2Y_Ly + Y_L² - Q_L = y² - 2Y_Sy + Y_S² - Q_S
2(Y_S - Y_L)y = Y_S² - Y_L² + Q_L - Q_S
y = [Y_S² - Y_L² + Q_L - Q_S] / 2(Y_S - Y_L)

Call this quantity y_I; I for intersection. The x-coordinates of the intersection point(s) can be found by subbing this back into one of the circle equations:

x² + (y - Y_S)² = Q_S
x² + (Y_I - Y_S)² - Q_S = 0

Here we have a quadratic equation with a = 1, b = 0, and c = (Y_I - Y_S)² - Q_S. Its determinant, b² - 4ac, is simply -4c. We thus know the following:

• C_S < C_L ⇔ zero intersections between circles ⇔ -4c < 0 ⇔ 0 < c ⇔ 0 < (Y_I - Y_S)² - Q_S ⇔ Q_S < (Y_I - Y_S)²
• C_S = C_L ⇔ one intersections between circles ⇔ -4c = 0 ⇔ 0 = c ⇔ 0 = (Y_I - Y_S)² - Q_S ⇔ Q_S = (Y_I - Y_S)²
• C_S > C_L ⇔ two intersections between circles ⇔ -4c > 0 ⇔ 0 > c ⇔ 0 > (Y_I - Y_S)² - Q_S ⇔ Q_S > (Y_I - Y_S)²

The salient facts being:

• C_S < C_L ⇔ Q_S < (Y_I - Y_S)²
• C_S = C_L ⇔ Q_S = (Y_I - Y_S)²
• C_S > C_L ⇔ Q_S > (Y_I - Y_S)²

Informatlly, this test is comparing the squared distance between the intersection line and the circle center to the circle's quadrance (the squared distance between the circle's edge and the circle center).

---

That was a long one, so let's wrap it up with a handy chart:

	Q1 < Q2	Q1 = Q2	Q1 > Q2
Y1 < Y2	special	C1 > C2	C1 > C2
Y1 = Y2	C1 < C2	C1 = C2	C1 > C2
Y1 > Y2	C1 < C2	C1 < C2	special

In the special case, the smaller circle's center is lower than the larger circle. If the smaller circle's center is completely outside the larger circle, then the larger circle is the 'lesser' circle. Otherwise, the order of the two circles is determined by the number of points at which the circles intersect: zero for smaller circle first, one for circles equal, or two for larger circle first.