Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Update

Alternative Statement of Problem, with New Picture

Given three points $P_1$, $P_2$, and $P_3$ in the Cartesian plane, I would like to find the ellipse which passes through all three points, subject to the following constraints:

  1. $P_1$ and $P_2$ lie on axes of the ellipse.

  2. $\|P_2-P_3\|\le\|P_2-P_1\|$, that is, $P_2$ is not farther from $P_3$ than from $P_1$. (If this is not the case, we can simply swap the labels of $P_1$ with $P_3$ to ensure that it is.)

In the picture below, let $O$ be the center of the ellipse and let $F_1$ and $F_2$ be foci. Also let $P_1\prime$ and $P_2\prime$ be the points opposite $P_1$ and $P_2$, respectively, on the ellipse. These points $O$, $F_1$, $F_2$, $P_1\prime$, and $P_2\prime$ are unknowns to solve for. How do I find them? (Note: this is not homework!)

Ellipse2

Here’s what I know

  1. The center point $O$ lies on a circle passing through diametrically opposed points $P_1$ and $P_2$ (shown as a dotted line in orange) because the angle ${\angle}P_1OP_2$ must be 90°.
  2. $\|P_i-F_1\| + \|P_i-F_2\| = 2r$,   $i \in \{1,2,3\}$.    (The sum of the distances from any point on an ellipse to the foci is a constant value, in this case $2r$.)
  3. $\|P_2-P_2\prime\| = 2r$    and    $\|P_2-O\|=r$.    (Follows from #2.)
  4. $\|P_1-O\|^2 + \|P_2-O\|^2 = \|P_2-P_1\|^2$.   (Pythagorean Theorem applied to ${\triangle}P_1OP_2$. Follows from #1.)

What am I missing?

Intuition tells me there must be some simple way to find $O$, $F_1$, $F_2$, and $r$ — and yet I don’t see where to take it from here.

Below is the original statement of the problem, before the update. The original statement takes more of an algebraic approach, whereas this new statement above takes more of a geometric approach.


Original Statement of Problem

How can I find the unique ellipse that passes through three distinct points P₁, P₂, and P₃, such that P₁ and P₂ lie on the axes of the ellipse, and such that P₂ is closer to P₃ than it is to P₁? (P₃ could also lie on the same axis as P₁ in the simplest case, but won’t it ever lie on the same axis as P₂ because the points are distinct.) More specifically, what I want to find is actually the angle θ with which the axis coincident with P₁ is rotated with respect to the x-axis, because this will tell me the angle of the line of tangent at P₂, which is what I’m ultimately interested in.

This is not homework. This is for piecewise (local) curve-fitting of an arbitrary collection of points, where the fitted curve passes through each point using cubic Bézier curve segments. For every triplet of consecutive points, I want to pass an imaginary ellipse through the points, with the middle point (e.g., P₂) provides a pleasing tangent line from which to derive a pair of Bézier control points. This will provide C₁ continuity in the final curve.

Ellipse

Approaches I have tried so far

  1. The first approach I tried was to describe the ellipse parametrically and then scale, rotate, and translate it — and then formulate that as an equation to solve in terms of $\theta$. That ended up reducing to: $$ \Big(\frac{A\cos\theta - B\sin\theta}{C\sin\theta - D\cos\theta}\Big)^2 + \Big(\frac{E\cos\theta + F\sin\theta}{G\sin\theta + H\cos\theta}\Big)^2 = 1 $$ where $A$,$B$,$C$,$D$,$E$,$F$,$G$,$H$ are various vector components of deltas between the three points, but that didn't get me anywhere because I have no idea how to solve that.

  2. The second approach I tried was to try to calculate $\theta$ as a function of the ratio of $\|\vec{P_2}-\vec{P_3}\|$ over $\|\vec{P_1}-\vec{P_2}\|$, but I was mistaken that this would lead me anywhere, since in hindsight I believe the ratio is only helpful here for circles rather than ellipses.

  3. The third approach I tried was to develop a formula for a general ellipse with center $(u,v)$, semi-major/minor axis lengths $\alpha$ and $\beta$, and rotation $\varphi$. This gave me $$ \Big(\frac{(x-u)\cos\varphi + (y-v)\sin\varphi}{\alpha}\Big)^2 + \Big(\frac{-(x-u)\sin\varphi + (y-v)\cos\varphi}{\beta}\Big)^2 = 1 $$ which is all well and good, but I can’t see where to go with it.

  4. The fourth approach I tried was to write the ellipse in general bivariate quadratic form $$ Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 , \quad\textrm{(with A,B,C not all zero)} $$ in which ellipses are represented when $B^2 - 4AC < 0$, and then write out three linear equations of $A$,$B$,$C$,$D$,$E$,$F$ using $P_1$, $P_2$, and $P_3$ as follows: $$Ax_1^2 + Bx_1y_1 + Cy_1^2 + Dx_1 + Ey_1 + F = 0$$ $$Ax_2^2 + Bx_2y_2 + Cy_2^2 + Dx_2 + Ey_2 + F = 0$$ $$Ax_3^2 + Bx_3y_3 + Cy_2^2 + Dx_3 + Ey_3 + F = 0$$ Where I’m stuck right now is how to codify the $B^2 - 4AC < 0$ requirement into this system of linear equations, and how to codify that $P_1$ and $P_2$ lie on the axes of the ellipse.

Other approaches?

I’m out of ideas. I would think the solution is actually probably rather simple, perhaps involving a few inverse sines or cosines and a square root or two. I haven’t been able to find this particular problem stated anywhere (and therefore no conveniently packaged solution), but I’m sure it can’t be all that unusual.

I did have the idea to take my first partial solution (listed above) and do some sort of iterative binary search for $\theta$ (trying different values until the curve passes through $P_3$), but I am much more interested in a closed-formula solution, because this will be executed in a loop over hundreds or thousands of point sets.

share|improve this question
    
What about the circle with these points? I guess the solution is not going to be unique.. –  Berci Sep 29 '12 at 11:36
1  
@Berci, the lines joining $P_1$ and $P_2$ to the center of the ellipse must be perpendicular, which will not be true in general if you take the ellipse to be a circle. –  Rahul Sep 29 '12 at 11:41
    
ah, true, indeed.. –  Berci Sep 29 '12 at 11:50
    
@RahulNarain — A circle works very nicely when $P_2$ is positioned between $P_1$ and $P_3$, particularly when its close to the $P_1P_3$ line segment. But when $P_2$ is, say, way off to the right or left of $P_3$ and close to collinear with $P_1P_3$, then a circle creates an undesirable tangent that’s almost in a perpendicular direction from what I need. I appreciate the suggestion of trying a circle instead, though! I’m definitely open to possibilities besides ellipses. I was thinking last night that maybe a parabola would work. –  Todd Lehman Sep 30 '12 at 13:51

1 Answer 1

Solve for the center $O$ of the ellipse: We know that $O$ is on the circle with $P_1P_2$ as diameter and can verify whether or not $P_3$ is on the corresponding ellipse. We have: $$\tag1\langle P_1-O,P_2-O\rangle=0$$ $$\tag2\frac{\langle P_3-O,P_1-O\rangle^2}{\langle P_1-O,P_1-O\rangle^2}+\frac{\langle P_3-O,P_1-O\rangle^2}{\langle P_2-O,P_2-O\rangle^2}=1$$ I am afraid that equation $(2)$ is of two high a degree to allow unique solutions (I bet there are at least four in the general case).

Why not simply use an approximation, after all you will use the ellipse itself as an approximation only? If $M$ is the middle between $P_1$ and $P_3$, assume that the tangent at $P_2$ should be orthogonal to $MP_2$.

share|improve this answer
1  
That should be $\langle P_3-O,P_2-O\rangle^2$ in the numerator of the second term, shouldn't it? –  Rahul Sep 29 '12 at 12:33
    
If we pick the coordinate system so that $P_1=(-1,0)$ and $P_2=(1,0)$, then we can let $O=(\cos\phi,\sin\phi)$ and $P_3=(x,y)$. Equation (2) then becomes $1+x\cos\phi+(1-x^2+y^2)/(2y)\sin\phi=y\csc\phi$, and that is not likely to have a closed-form solution for $\phi$. –  Rahul Sep 29 '12 at 12:40
    
@Hagen — Well, using a line orthogonal to $P_2-M$, where $M = \frac{1}{2}(P_1+P_3)$, is a decent approximation if $P_2$ is far away from $P_3$. But if $P_2$ is close to $P_3$ (that is, much closer to $P_3$ than it is to $P_1$), then it gives disastrously different line than the tangent to the fitted ellipse. So this is why I’m seeking a solution that actually fits an ellipse, rather than a simpler approximation. Although I won’t be fitting my final curve using the ellipse (I use cubic Bézier curves for that), the tangent of the fitted ellipse supplies a beautiful set of Bézier control points. –  Todd Lehman Sep 29 '12 at 23:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.