How to determine if two ellipses overlap?
Arthur van Deudekom
out if two ellipses overlap?
David Ziskind
<hrpurg...@forum.swarthmore.edu> regarding the problem of determining if
two ellipses overlap.
To solve the problem, we will assume without proof the following
categorization:
If Y and Z are non-identical ellipses THEN
exactly one of the next three cases holds true:
[1. All of Y lies wholly in the interior of Z, or vice-versa.
2. All of Y lies wholly in the exterior of Z, and vice-versa.
3. Y and Z have at least one boundary point in common.
]
Now let the interpretation of Y, Z be overloaded so that:
(for all x and y)
[(x, y) lies on the boundary of the "Y ellipse" IFF y=Y(x)]
Similarly, let Z be a second function giving the boundary of the "Z
ellipse".
To proceed with the solution, we will assume that the formulae for Y and Z
are known explicitly. (If they were given implicitly, we would have to
solve the implicit equation.) In a simple case, we might have some formula
for Y such as: Y(x) = (1 - 3*x^2)^(1/2) . From here on, evaluation
parentheses will generally be omitted.
We will further assume that the equations for both ellipses have been
obtained in standard form (as well as in explicit form). (See Comments at
foot.) That is, we will assume that we have found a transformation S=(S_1,
S_2) such that:
[S_1(x,Yx)/a]^2 + [S_2(x,Yx)/b]^2 = 1 (a>=b are parameters) (1)
S is a solid body transformation, and in two dimensions takes parameters t
(Theta), a rotation angle; and h_1, h_2, a sHift vector; and is given by:
S_1(u, v) = u*cos t - v*sin t + h_1 (0<=t<pi) (2)
S_2(u, v) = u*sin t + v*cos t + h_2
Likewise, the standard form for Z has been obtained:
[T_1(x,Zx)/c]^2 + [T_2(x,Zx)/d]^2 = 1 (c>=d) (3)
T follows the same plan as S, but supplies its own set of structure
constants in place of t and h.
We now proceed to the specifics of the solution.
1. Determine if Y = Z (identically). (This will be true IFF (corresponding
structure constants of S and T are equal, and a=c, and b=d).) If so, the
two ellipses are equal, we have overlap, and the problem is finished.
**Assume now that Y = Z is not identically true:**
2. Using the explicit forms for Y and Z, solve the equation Y(x0) = Z(x0).
If there is at least one real solution x0, then the two ellipses have at
least one boundary point in common -- and they overlap.
**Assume now the result that Y(x0)=Z(x0) has no real solution x0:**
3. Find a value x* such that Z(x*) is real; that is, find a value x* which
is within the X-axis limits (using standardized coordinates) of the Z
ellipse. In the following, we take x* to be the semi-major axis, and it
thus satisfies:
T_2(x*, Z(x*)) = 0
4. Map the point (x*, Zx*) into the coordinate values given by the standard
coordinate system established for the Y ellipse (the YCS). This mapped
value is S(x*,Zx*) and in the YCS picture gives a vector which passes from
the YCS origin to the point (x*,Zx*). Now find either of the two points
which in the YCS picture: (a) lie on the ray determined by said vector, and
(b) also lie on the boundary of Y. Thus, solve for p, q, the equations:
p = Yq
S_1(p,q)/S_2(p,q) = S_1(x*,Zx*)/S_2(x*,Zx*)
If |S(p,q)| > |S(x*,Zx*)|, then the representative Z boundary point lies
INSIDE the Y ellipse, and we know from the forgoing, that ALL Z boundary
points also lie inside Y, and we thus have overlap, and are finished.
5. If the inequality |S(p,q)| > |S(x*,Zx*)| does not hold, then repeat
Steps 3 and 4 with the roles of Y and Z interchanged. It may turn out that
all Y boundary points lie inside Z -- again, overlap.
6. If neither of the two inequality tests is satisfied, we are forced to
conclude that Y lies outside Z and vice-versa; that is, Case 2 above, and
there is no overlap.
----------------------------------------------------------------
Comments:
There is initially the problem of placing the equation for each ellipse in
standard form; the process of diagonalization is given in many linear
algebra textbooks as well as Korn and Korn, "Mathematical Handbook for
Scientists and Engineers", 2nd Edition, McGraw Hill, 1967, ISBN 0070353700.
However, even here there is an underlying assumption that the formula for
say Y is in the form Sum(m=0;2:n=0;2: a_mn * q_m * q_n) = 0 with x=q_1 and
Y(x)=q_2 and 1=q_0. If on the contrary, Y was given explicitly, we would
have to isolate and eliminate the radical by squaring, eventually obtaining
the quadratic form.
In Step 4, the same type of reasoning has been employed that was first used
in asserting the categorization axiom at the beginning of the unit. Also,
note that the deduction in Step 4 ("Z boundary point lies inside ... ")
depends on the convexity of the ellipse and would not hold for general
shapes.
David Ziskind
zis...@ntplx.net