From GPWiki

Jump to: navigation, search

Abstract

In this tutorial I present a conceptually simple and computationally inexpensive way to compute the tangents to circles and ellipses. The method presented is remarkably simple, however it is rather technical and does require understanding of basic linear algebra.

Prerequisite Linear Algebra

The math in this article is unfortunately fairly technical. It is not necessarily difficult (it is, in fact, fairly straightforward), but merely uncommon knowledge. For many people, hearing of "homomorphisms of vector spaces" is something akin to stirring thoughts of the occult. There is little I can do about this, and I make no pretense of having spared from the reader these complexities.

Rather than include an exposition on the prerequisite notions of linear algebra and abstract algebra, I will instead give a list of links to external resources explaining these things in much more detail than I could here. You should be familiar with the following concepts:

Field
Vector
Vector Space
Vector Space Basis
Matrices
Linear Transformation
I will use the word homomorphism in this article. A homomorphism is a map (i.e., a function) between two algebraic structures (for example, $f : \R^3 \to \R^2$ ) which preserves all relevant structure (e.g., $f (c x + y) = c f (x) + f (y)$ ). Hence, a linear transformation is a homomorphism of vector spaces.

Although unnecessary, it would ease comprehension to be familiar with Set Notation.

Tangents to a Circle

A circle or 2-sphere is given by the set

$S_2 = \{(x,y) \in \R^2 | x^2 + y^2 = r^2 \}$

for some positive $r \in \R$ . The unit circle, then, is that for which $r = 1$ .

If the circle is positioned so that its center is the origin, then we have that the vector normal to the circle at the point $\vec p = (x,y)$ is $\vec n = \vec p$ , that is, points along the circle specify implicitly the normals. We will not prove this, but take it on intuition.

We may parameterize a line in the direction of $\vec n$ by the vector-valued function

$\vec n(t) = t\vec p$ .

Hence, the slope of the line $\vec n(t)$ is $\frac{\vec p_y}{\vec p_x}$ . It follows from elementary algebra that the vector perpendicular to $\vec n$ is $(-\vec p_y,\vec p_x)$ , which describes the slope of the tangent line. We may parameterize this line similarly:

$\vec t(t) = t(-\vec p_y,\vec p_x)$ .

However, this line will pass through the origin, not the point at which the tangent it describes touches the circle. We remedy this by applying the offset $\vec p$ :

$\vec t(t) = \vec p + t(-\vec p_y,\vec p_x)$ .

Observe that we obtain the very same tangent by flipping the signs of the x- and y-components of $\vec p$ . This expresses the fact that although a point on the circle specifies uniquely one tangent, a tangent to the circle specifies two points on the circle.

Tangents to an Ellipse

Firstly, I should note that there exist many methods for computing the tangents to ellipses. The one which follows is only one of them, and may or may not suit your needs. The derivation is detailed, however, and is such that it has a variety of applications other than ellipse tangents.

To determine the tangent to an ellipse, we use the clever technique of mapping our ellipse into a new vector space in which it becomes a unit circle.

Consider the ellipse in the above diagram. It can be seen that we may uniquely specify an ellipse so long as it is situated so that its center is the origin by a tuple $(w, h)$ where w and h are its half-width and half-height, respectively.

Here, we exploit the properties of a vector space. The trick is to map points along the ellipse $\vec p$ onto a unit circle in a different vector space. All we must do is construct a homomorphism $\gamma : \R^2 \to E$ , where $E$ is our new vector space which we will dub "ellipse space", which changes the basis vectors appropriately from $(1,0)$ and $(0,1)$ to $(w,0)$ and $(0, h)$ .

The change in basis vectors means that the point $(w,0)$ in $\R^2$ becomes $(1,0)$ in $E$ , and likewise for $(0, h)$ . Consider that our ellipse was described by the "radius vector" $(w, h)$ in Euclidean space; the mapping $γ$ places our ellipse into a vector space with basis vectors such that its radius vector becomes $(1,1)$ , i.e. it becomes a unit circle!

Such a mapping may be defined as follows:

$\gamma(\vec p) = (\vec p_x\frac{1}{w}, \vec p_y\frac{1}{h})$ .

However, this is nothing but a linear transformation, and a simple one at that, so we shall simply write it as a matrix:

$\lambda = \begin{bmatrix} \frac{1}{w} 0 \\ 0 \frac{1}{h} \\ \end{bmatrix}$ .

We may prove the correctness of this transformation by showing that applying it to the standard equation for an ellipse yields a geometric entity for which all points are equidistant from the origin (i.e. a circle):

$\frac{x^2}{w^2} + \frac{y^2}{h^2} = 1$

$(x^2, y^2) = (w^2 - \frac{y^2w^2}{h^2}, h^2 - \frac{x^2h^2}{w^2})$

$\lambda (x, y) = (\frac{1}{w}\sqrt{w^2(1 - \frac{y^2}{h^2})}, \frac{1}{h}\sqrt{h^2(1 - \frac{x^2}{w^2})})$

However,

$1 - \frac{y^2}{h^2} = \frac{x^2}{w^2}$

and

$1 - \frac{x^2}{w^2} = \frac{y^2}{h^2}$

from the standard equation for an ellipse above. Hence,

$\lambda (x,y) = (\frac{1}{w}\sqrt{w^2\frac{x^2}{w^2}}, \frac{1}{h}\sqrt{h^2\frac{y^2}{h^2}})$

$\lambda (x,y) = (\frac{x}{w}, \frac{y}{h})$

We now show that all points of the form $λ(x, y)$ where $(x, y)$ is a point on the ellipse in Euclidean space are equidistant from the origin in $E$ (assuming the ellipse was centered on the origin).

We know that

$||(\frac{x}{w},\frac{y}{h})|| = \sqrt{\frac{x^2}{w^2} + \frac{y^2}{h^2}}$ .

However, observe that the radicand is the left side of the standard equation for an ellipse. We derived our new vector $λ(x, y)$ based on the assumption that $\frac{x^2}{w^2} + \frac{y^2}{h^2} = 1$ , hence this equality must hold here as well. This means

$||(\frac{x}{w},\frac{y}{h})|| = \sqrt{\frac{x^2}{w^2} + \frac{y^2}{h^2}} = \sqrt{1} = 1$

and we have proved that not only is our new structure a circle, but the unit circle.

Suppose now that we have mapped our ellipse into $E$ . Then its circular image is given by

$\{(x,y) \in E | x^2 + y^2 = 1\}$ .

That is, it is consisted of all points $\vec p \in E$ which are unit distance from the origin. Thus, we may use the math described in the section "Tangents to a Circle" above to determine its tangents as being lines parameterized by

$\vec t(t) = \vec p + t(-\vec p_y,\vec p_x)$ .

However, this line exists in $E$ . To transform it into $\R^2$ , we apply the inverse of $λ$ :

$\lambda^{-1} = \begin{bmatrix} w \, 0 \\ 0 \, h \\ \end{bmatrix}$ .

Hence, the tangent to an ellipse in standard Euclidean space $\R^2$ at a point $\vec q$ represented in $E$ coordinates is parameterized by:

$\vec t(t) = \lambda^{-1}(\vec q + t(-\vec q_y,\vec q_x))$ .

This equation requires, however, that the point $\vec q$ be in $E$ coordinates, a condition very unlikely to be fulfilled in any practical situations. In the probable case that $\vec q$ holds the raw Cartesian coordinates of a point directly on the ellipse in $\R^2$ , we make some modifications to the equation.

In order to use the above equation, we must first map $\vec q$ into $E$ by $(\lambda \vec q)$ . If we let $(\lambda \vec q)_t = (-(\lambda \vec q)_y, (\lambda \vec q)_x)$ be the tangential vector to the ellipse's circular image, then we have

$\vec t(t) = \lambda^{-1}(\lambda \vec q + t(\lambda \vec q)_t)$ .

Simplifying yields the following parameterization:

$\vec t(t) = (x(t), y(t)) = (\vec q_x - \frac{wt\vec q_y}{h}, \vec q_y + \frac{ht\vec q_x}{w})$ .

As an example, consider that we have an ellipse parameterized by

$(x (t), y (t)) E = (w cos t, h sin t)$ .

Then, any point along the ellipse's circular image is simply

$(x (t), y (t)) C = (cos t,sin t)$

obtained by multiplying $(x (t), y (t)) E$ by the $λ$ transformation. This shows much more clearly than the laborious math above that $λ$ properly maps ellipses to circles.

By the above, we may determine the tangent to the ellipse at a point thereon with angle of elevation $α$ thusly:

$(x (t), y (t)) t = (w cosα - w t sinα, h sinα + h t cosα)$ ,

$(x (t), y (t)) t = (w (cosα - t sinα), h (sinα + t cosα))$ .

Testing It

I have tested the formula using the Microsoft Student Graphing Calculator 2006 so that I could watch the tangent move around the circle as I changed the parameters. If you have this software, or similar software, I highly recommend inputting the equations so you can see first-hand that they work.

Here is a picture of a tangent computed with the formula:

thumb|none|400px

In the image, the trigonometric parameterizations for the ellipse and its tangents have been used, with the following:

$α$ = 0.48 radians
w = 1.78 units
h = 0.7 units

Transformations to Code

Transforming the final equation into code is an easy and straightforward process. Here is a snippet of pseudo-code which demonstrates how one might use the equation $\vec t(t) = (x(t), y(t)) = (\vec q_x - \frac{wt\vec q_y}{h}, \vec q_y + \frac{ht\vec q_x}{w})$ to compute ellipse tangents:

//
 /* Exactly how this will be implemented will depend on how you
  * store your ellipse. We will assume the ellipse is located at
  * the origin and specified by the tuple (w,h) as discussed in
  * the tutorial.
  */
 
// To store an ellipse centered at the origin:
struct Ellipse2D
{
     float HalfWidth;
     float HalfHeight;
};
 
// Simple 2-vector:
struct Vector2D
{
     float x;
     float y;
 
     // Include constructor...
};
 
 
 /* To calculate the tangent depends on the exact information
  * you want about it. If, for example, you simply want a vector
  * describing the direction of the tangent to an ellipse at a
  * point, you might do the following:
  */
 
Vector2D DetermineEllipseTangent( const Ellipse2D& Ellipse,
                                  const Vector2D& Point     )
{
 
      /* This is just an implementation of the equation in the
       * tutorial. All we need is a vector giving the direction
       * of the tangent, hence we only pay attention to the
       * final terms.
       */
 
      /* The variable t is simply a parameter to the equation.
       * We are only paying attention to the final terms, and
       * since they give the slope (i.e., the direction of the
       * tangent), we let t = 1.
       */
 
     Vector2D tangent = Vector2D(0, 0);
     tangent.x = Point.x - (Ellipse.HalfWidth*Point.y)/Ellipse.HalfHeight;
     tangent.y = Point.y + (Ellipse.HalfHeight*Point.x)/Ellipse.HalfWidth;
 
     return tangent;     
}

Various Applications

In all its simplicity, the $λ$ transformation matrix is rather powerful. It morphs ellipses into circles, and its inverse morphs circles into ellipses. Here I list several ways to use or exploit the equation for the ellipse tangent found in this article or the $λ$ matrix itself.

Rebound Effect in Pong

One application of the tangent equation is that of obtaining a good rebound effect in Pong. Often times, in Pong when the ball collides with a paddle, a perturbation is applied to the reflected path of the ball to add variety to the game.

We can systematically compute this perturbation easily by exploiting the equation for an ellipse tangent.

Assume for simplicity that the paddle is a rectangle and the ball is a sphere. This means the normals to the paddle on the upper-side are all the same. If we cleverly treat the paddle, however, as if it were an ellipse (even though it is not and is not so rendered), we can obtain a curved upper-side which contributes itself to the perturbation applied to the ball's reflected path. That is, we reflect the ball's velocity vector over the normal to the ellipse approximating the paddle rather than the actual normal.

In this case, the half-width and half-height w and h become tuning constants which we may use to control how much perturbation is applied.

We know that the tangent to an ellipse at a point $\vec q$ is given parametrically by

$\vec t(t) = (x(t), y(t)) = (\vec q_x - \frac{wt\vec q_y}{h}, \vec q_y + \frac{ht\vec q_x}{w})$ .

Hence, the normals to an ellipse are given parametrically by

$\vec n(t) = (x(t), y(t)) = (\vec q_x(1 + t\frac{h}{w}), \vec q_y(1 + t\frac{w}{h}))$ .

However, how do we determine $\vec q$ ? A simple method is to imagine the rectangle of the paddle immersed inside an ellipse. We may then project points along the upper- or lower-sides of the rectangle up onto the bottom of the top-side of the ellipse according to these rules, where $\vec r$ is the point on the rectangle and $\vec e$ is the point on the ellipse:

$\vec e_x = \vec r_x$ ,

$\vec e_y = \sqrt{h^2(1 - \frac{\vec r_x^2}{w^2})} = h\sqrt{1 - \frac{\vec r_x^2}{w^2}}$ .

Hence, the vector normal to the ellipse over which to reflect the ball's velocity vector is

$\vec n(t) = (x(t), y(t)) = (\vec r_x(1 + t\frac{h}{w}), h\sqrt{1 - \frac{\vec r_x^2}{w^2}}(1 + t\frac{w}{h}))$ .

Collision Detection with Ellipses

This does not directly deal with ellipse tangents, but rather is an exploitation of the properties of the $λ$ transformation.

Suppose we wish to perform a simple boolean intersection test of an ellipse and a segment. This sounds difficult, but it doesn't have to be. If we map both the ellipse and the segment into $E$ , then we have the situation that the ellipse becomes a circle but the segment remains a segment. We may then perform a boolean intersection test of a circle and a segment!

A detailed explanation of how to do this (including the ellipse-to-circle trick) may be found here.

Tangents To Circles And Ellipses

Contents

Abstract

Prerequisite Linear Algebra

Tangents to a Circle

Tangents to an Ellipse

Testing It

Transformations to Code

Various Applications

Rebound Effect in Pong

Collision Detection with Ellipses

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Toolbox