0
$\begingroup$

I'm doing some research on my own to find a method to check if two ellipses intersect.

So let's say we have the fallowing two general equations:

$$ ƒ_{1}\ :\ A_{1}x^{2}\ +\ B_{1}xy\ +\ C_{1}y^{2}\ +\ D_{1}x\ +\ E_{1}y\ +\ F_{1}\ =\ 0 $$

and

$$ ƒ_{2}\ :\ A_{2}x^{2}\ +\ B_{2}xy\ +\ C_{2}y^{2}\ +\ D_{2}x\ +\ E_{2}y\ +\ F_{2}\ =\ 0 $$

Since $k_{1}*0 = k_{2}*0$ any linear combination of the two functions intersects all the other linear combinations of the two (including them two) in the same points they'd intersect like this:

enter image description here

So any linear combination of two intersecting ellipses will be non-imaginary and non-degenerate because it has to pass trough those two real points.

With non-intersecting ellipses instead, some linear combinations "disappear" from the real plan like this:

enter image description here

So since reading this Wikipedia article an ellipse is real if:

$$ (A + C) * det A_{Q} < 0 $$

and given that $det A_{q}$ is:

$$ \left(AC\ -\ \frac{B^{2}}{4}\right)F\ +\ \frac{BED}{4}-\frac{CD^{2}}{4}-\frac{AE^{2}}{4} $$

I thought that, for intersecting ellipses the inequality:

$$ ƒ_{3}\ :\left(\left(\left(A_{1}x+A_{2}y\right)\left(C_{1}x+C_{2}y\right)\ -\ \frac{\left(B_{1}x+B_{2}y\right)^{2}}{4}\right)\left(F_{1}x+F_{2}y\right)\ +\ \frac{\left(B_{1}x+B_{2}y\right)\left(E_{1}x+E_{2}y\right)\left(D_{1}x+D_{2}y\right)}{4}-\frac{\left(C_{1}x+C_{2}y\right)\left(D_{1}x+D_{2}y\right)^{2}}{4}-\frac{\left(A_{1}x+A_{2}y\right)\left(E_{1}x+E_{2}y\right)^{2}}{4}\right)\left(\left(A_{1}x+A_{2}y\right)+\left(C_{1}x+C_{2}y\right)\right)\ <\ 0 $$

Would fill the whole plan since there shouldn't be any possibile combinations of $x, y$ ($k_{1}, k_{2}$) that make the general equation degenerate.

What I got is somehow satisfying but at the same time confusing:

enter image description here

So it seems that if the two ellipses are disjoined (the center of one is outside the other), the first and third quadrant are indeed filled.

Those negative slices in the second and fourth, when the two ellipses are disjoint, overlap with slices where the linear combination is an hyperbole ($A_{33} < 0$):

enter image description here

Since my application would be to detect collision of disjoint entities in a 2D plane, I think this method might work:

  1. Determine all coefficients of $ƒ_{3}$
  2. Evaluate $ƒ_{3}$ for points with 30° and 60° angle from $y=0$
  3. If any of the two is $\le 0$ the two ellipses intersect (or touch)
  4. If not, take the lowest result and find points at $\pm 15°$ from it
  5. Keep evaluating & splitting the quadrant fallowing the lowest result

This way with like 7 evaluations I can check down to like 0.7° precision.

So here's some question I got:

  1. What's the formal demonstration that any linear combination of $ƒ_{1}$ and $ƒ_{2}$ pass for their same intersection points?
  2. What are those negative slices in the $ƒ_{3}$ plot?
  3. Is there any wrong passage in my reasoning?
  4. How "good" would this method be compared to standard methods?
  5. Is there any what this can also hint to the actual minimal distance between the two ellipses?

Thanks a lot.

$\endgroup$
2
  • 1
    $\begingroup$ 1. is easy: If $f_1(p) = 0$ and $f_2(p) = 0$, then also $(\lambda f_1 + \mu f_2)(p) = \lambda f_1(p) + \mu f_2(p) = 0$. Also note that I think there is a degenerate case, where the the ellipse defined by $\lambda f_1 + \mu f_2$ is just the line through the intersection points. You even see this in your first animation, when the ellipse "wraps around". $\endgroup$ May 23, 2023 at 11:48
  • $\begingroup$ @red_trumpet thanks a lot for pointing out the easy proof! For your other statement, I think the only way to obtain that is with $𝜆=0$ and $𝜇=0$ because if you draw the linear combination coefficients A, B and C on a 𝜆/𝜇 plane they all pass trough the origin. With those values all the linear combination coefficients are 0 and the conic is degenerate. $\endgroup$ May 23, 2023 at 12:04

0

You must log in to answer this question.