cepek@vixvax.mgi.com (11/21/90)
I have an application which requires some computations beyond my
abilities. The descriptions of the two problems follow. Any assistance
that anyone can provide along these lines would be greatly appreciated.
- - - - - - - - - - - - - - - - # 1 - - - - - - - - - - - - - - - -
Given two points on a circle and a radius, it is an easy task to
geometrically determine where the center is (there are two solutions,
in fact - let's say the sign of the radius will define which to use).
Now, given two points on an ellipse and both radii, the geometric
solution isn't as intuitive. Instead, plug the two points into the
standard ellipse equation: (x-xc)^2 / a^2 + (y-yc)^2 / b^2 = 1
(twice), and you get two equations with two unknowns, which is
theoretically solvable.
One more twist: add in a rotation angle. The rotated ellipse formula
is a bit more complex, but again we end up with two equations and two
unknowns.
Note that the radii specified may be too small, resulting in an
unsolvable situation; for example, both radii are 5 and the
distance between the two points is 11. Noticing this case for
rotated ellipses is harder. The solution should include detection
of this case. To summarize...
You know: two points, both radii (signed), and an angle.
You want to find: the center point of the ellipse (use the signs of
the radii to specify one of the four possible solutions); else
indicate unsolvability.
- - - - - - - - - - - - - - - - # 2 - - - - - - - - - - - - - - - -
Consider a rotated ellipse, described this time by a center point, two
radii, and a rotation angle. Circumscribe an unrotated rectangle about
this ellipse. Next, asymmetrically scale this rectangle by some amount
about the center point. Now determine the ("maximum"*) ellipse
which is circumscribed by the final rectangle. To summarize...
You know: the center point, two radii, the rotation angle, and the
X and Y scale factors.
You want to find: the new radii and rotation angle.
Note that asymmetrically scaling a rotated ellipse is believed to result
in a shape which is mathematically not an ellipse. Therefore, direct
methods to "asymetrically transform" the ellipse equation should fail.
The indirect method described above is suggested as a way to determine
the closest approximating ellipse.
* - Perhaps a better way to state this would be in terms of the four
"contact points", where the ellipse is tangent to sides of the
rectangle. The contact points of the target ellipse then are the
original contact points scaled appropriately along with the rectangle.
Note that mathematically the (appropriate) derivative at the contact
points goes to zero. There may be better (more "mathematically correct"
or convenient, or more visually intuitive) ways to define the
orientation of the contact points; this aspect of this problem is
somewhat open to interpretation.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
It seems to me that each problem has several possible results, including
equations, algorithms, iterative methods (deterministic only, please!),
and combinations of these.
Implementation of the solutions in portable C code is our eventual goal.
Although complete solutions (including derivations) are most desired,
suggestions for approaching the problems, references to similar work,
etc., would also be appreciated.
Thanks in advance for sharing your wisdom.
+--------------------------------+---------------------------+ - - - - -
| Mike Cepek, Programmer/Analyst | Internet: Cepek@MGI.COM |
| Management Graphics, Inc. | Voice: +1 612/851-6112 | "Engage."
| 1401 East 79th Street | Operator: +1 612/854-1220 |
| Minneapolis, MN 55425 USA | Fax: +1 612/854-6913 |
+--------------------------------+---------------------------+ - - - - -mjw@otter.hpl.hp.com (Mike Wray) (11/29/90)
========================================================================
1) To find the centre,c, of a circle of radius 1, given distinct points
x and y lying on the circle.
We have
2 2
|x - c| = |y - c| = 1
The centre c lies on the perpendicular bisector of the line
through x and y. The equation of this line is
x + y
w = -------- - l u
2
Where w lies on the line, l is real number, and u is a unit
vector perpendicular to x-y.
[ Given x =(r,s), a perpendicular vector is (-s, r), and we can divide
by the length of x to obtain a unit vector.]
[ In the following x.y is dot product, i.e.
(a,b).(u,v) = au+bv. ]
From
2
|x - w| = 1
and
2 2 2 2
|x - w| = |(y-x)/2| + l(y-x)/2 . u + l |u|
2 2
= |x-y| /4 + l
so
2
l = sqrt( 1 - |x-y| )
-----
4
We thus have
c = x+y - l u
---
2
With l as above. We have 2 solutions depending on the sign
of sqrt we choose.
=========================================================================
2) To find the centre, c, of an ellipse of semi-major axis a, semi-minor
axis b, given distinct points x and y on the ellipse.
-1
Let S = ( a 0 ) and T = S
( 0 b )
The x and y lie on the ellipse if and only if u=Tx and v=Ty lie on
the circle radius 1 centre z = Tc.
Solve for z from u and v using problem 1), then c = Sz.
=========================================================================
3) Solving for the centre of an ellipse rotated by angle t is similar
to 2):
let
-1
S = (cos t -sin t)(a 0) and T = S
(sin t con t)(0 b)
and solve as before.
=========================================================================
Mike