# Euclidean Vectors in Flash

**Twice a month, we revisit some of our readers’ favorite posts from Activetuts+ history. This week’s retro-Active tutorial, first published in April, is a guide to Euclidean vectors: what they are, why you'd use them, and how to implement them in Flash with AS3.**

Euclidean vectors are objects in geometry with certain properties that are very useful for developing games. They can be seen as points, but they also have a magnitude and a direction. They are represented as arrows going from the initial point to the final point, and that's how we will draw them in this article.

Euclidean vectors are commonly used in mathematics and physics for a lot of things: they can represent velocity, acceleration and forces in physics, or help prove a lot of important theorems in mathematics. In this tutorial, you'll learn about Euclidean vectors, and build a class that you can use in your own Flash projects.

Please note that Euclidean vectors are different than ActionScript's Vector class, and also different than vector drawing.

Vectors can be used in the Flash environment to help you achieve complex tasks that would otherwise require a lot of effort if done without them. In this article you will learn how to use them in Flash, as well as learn a lot of cool tricks with vectors.

## Step 1: Cartesian Coordinates and Flash's Coordinates

Before jumping into vectors, let's introduce Flash's coordinate system. You are probably familiar with the Cartesian coordinate system (even if you don't know it by name):

Flash's system is very similar. The only difference is that the y-axis is upside-down:

When we start working with vectors in flash, we need to remember that. However, good news: this different system doesn't make much difference. Working with vectors in it will be basically like working with vectors in the Cartesian system.

## Step 2: Defining a Vector

For the purpose of this tutorial, we will define and work with all vectors' initial points as being the registration point of the stage, just as they are commonly used in mathematics. A vector will then be defined just like a common point, but it will have magnitude and angle properties. Take a look at some example vectors defined in the stage:

As you can see, a vector is represented by an arrow, and each vector has a certain length (or *magnitude*) and points along a certain *angle*. The tail of each vector is at the registration point `(0, 0)`

.

We will create a simple EuclideanVector class for this tutorial, using the Point class to hold the vector's coordinates. Let's create the basic vector class now:

package { import flash.geom.Point; public class EuclideanVector { public var position:Point; public var magnitude:Number; public var angle:Number; public function EuclideanVector(endPoint:Point) { position = endPoint; } } }

During this tutorial, we will talk about the *sense* and the *direction* of a vector. Note that the direction just defines a line that "contains" the vector. The sense is what defines which way the vector points along this line.

## Step 3: Inverse of a Vector

In this tutorial we will use the expression "inverse of a vector". The inverse of a vector is another vector with the same magnitude and direction, but a contrary sense. That translates to a vector with the opposite signal of the first vector's coordinates. So a vector with an endpoint of (x, y) would have an inverse vector with an endpoint of (-x, -y).

Let's add a function to our EuclideanVector class to return the inverse vector:

public function inverse():EuclideanVector { return new EuclideanVector(new Point(-position.x, -position.y)); }

## Step 4: Basic Operations Addition

Now that we have learned how to define a vector, let's learn how to add two vectors: it's as simple as adding their coordinates separately. Look at this image:

If you notice in the image, the result of the addition of two vectors is another vector, and you can see that its coordinates are the sum of the coordinates of the other two vectors. In code, it would look like this:

public function sum(otherVector:EuclideanVector):EuclideanVector { position.x += otherVector.position.x; position.y += otherVector.position.y; return this; }

So we can say that:

vecR == vec1.sum(vec2);

## Step 5: Basic Operations Subtraction

Subtraction works almost the same as addition, but instead we will be adding the *inverse* of the second vector to the first vector.

It is already known how to sum two vectors, so here's the code for subtraction:

public function subtract(otherVector:EuclideanVector):EuclideanVector { position.x -= otherVector.position.x; position.y -= otherVector.position.y; return this; }

This code is extremely useful to get a vector that goes from the point of a vector to the point of another. Look again at the image and you will see this is true. It will be used a lot in the later examples.

## Step 6: Basic Operations Multiplication by a Number

The multiplication between a vector and a number (regular numbers are known as "scalars" in vector math) results in a vector which has had magnitude multiplied by this number, but still pointing in the same direction; it's "stretched" if the scalar is larger than 1, and squashed if the scalar is between 0 and 1. The sense of the new vector will be the same as the original vector if the scalar is positive, or the opposite if negative. Basically, this number "scales" the vector. Look at the picture:

In the code, we only multiply a vector's coordinates by the number, which will then scale the vector:

public function multiply(number:Number):EuclideanVector { position.x *= number; position.y *= number; return this; }

## Step 7: Getting a Vector's Magnitude

In order to get a vector's magnitude, we will use the Pythagorean theorem. If you forgot what is it, here is a quick refresher:

The code is very simple:

public function magnitude():Number { return Math.sqrt((position.x * position.x) + (position.y * position.y)); }

You should also remove the line `public var magnitude:Number`

, as this is what we'll use from now on.

The magnitude of a vector will always be positive, since it is the square root of the sum of two positive numbers.

## Step 8: Getting the Angle of a Vector

The angle of a vector is the angle between the x-axis and the vector's direction line. The angle is measured going from the x-axis and rotating anti-clockwise until the direction line in the cartesian system:

However, in Flash's coordinate system, since the y-axis is upside down, this angle will be measured rotating clockwise:

This can be easily calculated using the following code. The angle will be returned in radians, in a range from 0 to 2pi. If you don't know what radians are or how to use them, this tutorial by Michael James Williams will help you a lot.

public function angle():Number { var angle:Number = Math.atan2(position.y, position.x); if (angle < 0) { angle += Math.PI * 2; } return angle; }

## Step 9: Dot Product

The dot product between two vectors is a number with apparently no meaning, but it has two useful uses. Let's first take a look at how the dot product can be calculated:

But it also can be obtained by each vector's coordinates:

The dot product can tell us a lot about the angle between the vectors: if it's positive, then the angle ranges from 0 to 90 degrees. If it's negative, the angle ranges from 90 to 180 degrees. If it's zero, the angle is 90 degrees. That happens because in the first formula only the cosine is responsible for giving the dot product a "signal": the magnitudes are always positive. But we know that a positive cosine means that the angle ranges from 0 to 90 degrees, and so on for negative cosines and zero.

The dot product can also be used to represent the length of a vector in the direction of the other vector. Think of it as a projection. This proves extremelly useful in things like the Separation of Axis Theorem (SAT) and its implementation in AS3 for collision detection and response in games.

Here is the practical code to get the dot product between two vectors:

public function dot(otherVector:EuclideanVector):Number { return (position.x * otherVector.position.x) + (position.y * otherVector.position.y); }

## Step 10: Smallest Angle Between Vectors

The angle between vectors, as seen in Step 9, can be given by the dot product. Here is how to calculate it:

public function angleBetween(otherVector:EuclideanVector):Number { return Math.acos(dot(otherVector) / (magnitude() * otherVector.magnitude())); }

## Step 11: Ranged Angle Between Vectors

There is also another way to calculate the angle, which gives results between -pi and pi and always calculates the angle that goes from the first vector to the second vector; this is useful when you want to easily integrate with a display object's rotation (which ranges from -180 to 180).

The method works by getting the angle for both vectors, then subtracting the angles and working on the result.

The code:

public function rangedAngleBetween(otherVector:EuclideanVector):Number { var firstAngle:Number; var secondAngle:Number; var angle:Number; firstAngle = Math.atan2(otherVector.position.y, otherVector.position.x); secondAngle = Math.atan2(position.y, position.x); angle = secondAngle - firstAngle; while (angle > Math.PI) angle -= Math.PI * 2; while (angle < -Math.PI) angle += Math.PI * 2; return angle; }

Note that this angle returns positive if *secondAngle* is higher than *firstAngle*, so the order in which you get the ranged angle will affect the result!

## Step 12: Normalizing a Vector

Normalizing a vector means making its magnitude be equal to 1, while still preserving the direction and sense of the vector. In order to do that, we multiply the vector by `1/magnitude`

. That way, its magnitude will be reduced, or increased, to 1.

public function normalize():EuclideanVector { var m:Number = magnitude(); position.x /= m; position.y /= m; return this; }

## Step 13: Getting the Normal of a Vector

The *normal* of a vector is another vector that makes a 90 degree angle to the first. It can be calculated by the following formulas:

The formulas rely on the fact that, since the normal is always perpendicular to a vector, we only need to change the order of the x and y coordinates and invert one of them in order to get a normal. The following image shows the process:

In the image, *Vec* is the original vector, *Vec2* is the vector with *Vec*'s swapped coordinates, and *Vec3* is a vector with *Vec2*'s negative y coordinate. *Ang* and *Ang2* are variable, but the angle between *Vec* and *Vec3* is always 90 degrees.

And the code is simple

public function normalRight():EuclideanVector { return new EuclideanVector(new Point(-position.y, position.x)); } public function normalLeft():EuclideanVector { return new EuclideanVector(new Point(position.y, -position.x)); }

## Step 14: Rotating a Vector

In order to rotate a vector, we assume the (0, 0) position (its initial point) will be the rotation center. The rotated point is given by the formula:

This formula is obtained by applying a rotation matrix to that vector. We would be going beyond the scope of this tutorial if we went into the matrix and how it works, so I will just leave the formula here.

The code is pretty much the same:

public function rotate(angleInRadians:Number):EuclideanVector { var newPosX:Number = (position.x * Math.cos(angleInRadians)) - (position.y * Math.sin(angleInRadians)); var newPosY:Number = (position.x * Math.sin(angleInRadians)) + (position.y * Math.cos(angleInRadians)); position.x = newPosX; position.y = newPosY; return this; }

This is the end of our basic vector operations. What you will see next is ways to use this class to do interesting things. Here is our class so far:

package { import flash.geom.Point; public class EuclideanVector { public var position:Point; public var angle:Number; public function EuclideanVector(endPoint:Point) { position = endPoint; } public function inverse():EuclideanVector { return new EuclideanVector(new Point(-position.x, -position.y)); } public function sum(otherVector:EuclideanVector):EuclideanVector { position.x += otherVector.position.x; position.y += otherVector.position.y; return this; } public function subtract(otherVector:EuclideanVector):EuclideanVector { position.x -= otherVector.position.x; position.y -= otherVector.position.y; return this; } public function multiply(number:Number):EuclideanVector { position.x *= number; position.y *= number; return this; } public function magnitude():Number { return Math.sqrt((position.x * position.x) + (position.y * position.y)); } public function angle():Number { var angle:Number = Math.atan2(position.y, position.x); if (angle < 0) { angle += Math.PI * 2; } return angle; } public function dot(otherVector:EuclideanVector):Number { return (position.x * otherVector.position.x) + (position.y * otherVector.position.y); } public function angleBetween(otherVector:EuclideanVector):Number { return Math.acos(dot(otherVector) / (magnitude() * otherVector.magnitude())); } public function rangedAngleBetween(otherVector:EuclideanVector):Number { var firstAngle:Number; var secondAngle:Number; var angle:Number; firstAngle = Math.atan2(otherVector.position.y, otherVector.position.x); secondAngle = Math.atan2(position.y, position.x); angle = secondAngle - firstAngle; while (angle > Math.PI) angle -= Math.PI * 2; while (angle < -Math.PI) angle += Math.PI * 2; return angle; } public function normalize():EuclideanVector { position.x /= magnitude(); position.y /= magnitude(); return this; } public function normalRight():EuclideanVector { return new EuclideanVector(new Point(-position.y, position.x)); } public function normalLeft():EuclideanVector { return new EuclideanVector(new Point(position.y, -position.x)); } public function rotate(angleInRadians:Number):EuclideanVector { var newPosX:Number = (position.x * Math.cos(angleInRadians)) - (position.y * Math.sin(angleInRadians)); var newPosY:Number = (position.x * Math.sin(angleInRadians)) + (position.y * Math.cos(angleInRadians)); position.x = newPosX; position.y = newPosY; return this; } } }

### OK, we've covered building the vector class, now let's take a took at utilising it.

## Step 15: Determining Whether a Point is Inside a Polygon

The action begins here. Determining whether a point lies inside a polygon or not is a very interesting topic, and there are many methods of achieving it. In this article I will present the three methods that are generally used:

- The
*crossing number*or*even-odd rule algorithm*, which determines whether a point is inside a polygon from the number of edges that a "ray" cast from the point to infinity crosses. - The
*winding number algorithm*, which gives the answer based on the sum of all angles formed between consecutive vertices of a polygon and the point to check. - The
*convex polygon algorithm*, which, as the name says, only works for convex polygons and is based on whether or not a point is on a certain "side" of every edge of the polygon.

All these algorithms will rely on the fact that you know the coordinates of the vertices (corners) that define the polygon.

## Step 16: The Crossing Number or Even-Odd Rule Algorithm

This algorithm can be used for any shape. This is what you read: any shape, have it holes or not, be it convex or not. It is based on the fact that any ray cast from the point you want to check out to infinity will cross an even number of edges if the point is outside the shape, or odd number of edges if the point is inside the shape. This can be proven by the Jordan curve theorem, which implies that you will have to cross a border between some region and other region if you want to move from one to other. In our case, our regions are "inside the shape" and "outside the shape".

The code for this algorithm is the following:

public function isPointInsideShape1(point:EuclideanVector, shapeVertices:Vector.<EuclideanVector>):Boolean { var numberOfSides:int = shapeVertices.length; var i:int = 0; var j:int = numberOfSides - 1; var oddNodes:Boolean = false; while (i < numberOfSides) { if ((shapeVertices[i].position.y < point.position.y && shapeVertices[j].position.y >= point.position.y) || (shapeVertices[j].position.y < point.position.y && shapeVertices[i].position.y >= point.position.y)) { if (shapeVertices[i].position.x + (((point.position.y - shapeVertices[i].position.y) / (shapeVertices[j].position.y - shapeVertices[i].position.y)) * (shapeVertices[j].position.x - shapeVertices[i].position.x)) < point.position.x) { oddNodes = !oddNodes; } } j = i; i++; } return oddNodes; }

It will return `false`

if the point is not inside the shape, or `true`

if the point is inside the shape.

## Step 17: The Winding Number Algorithm

The *winding number algorithm* use the sum of all the angles made between the point to check and each pair of points that define the polygon. If the sum is close to 2pi, then the point being checked is inside the vector. If it is close to 0 then the point is outside.

public function isPointInsideShape2(point:EuclideanVector, shapeVertices:Vector.<EuclideanVector>):Boolean { var numberOfSides:int = shapeVertices.length; var i:int = 0; var angle:Number = 0; var rawAngle:Number = 0; var firstVector:EuclideanVector; var secondVector:EuclideanVector; while(i < numberOfSides) { firstVector = new EuclideanVector(new Point(shapeVertices[i].position.x - point.position.x, shapeVertices[i].position.y - point.position.y)); secondVector = new EuclideanVector(new Point(shapeVertices[(i + 1) % numberOfSides].position.x - point.position.x, shapeVertices[(i + 1) % numberOfSides].position.y - point.position.y)); angle += secondVector.rangedAngleBetween(firstVector); i++; } if(Math.abs(angle) < Math.PI) return false; else return true; }

The code uses the ranged angle between vectors and gives space for imprecisions: notice how we are checking the results of the sum of all angles. We do not check if the angle is exactly zero or 2pi. Instead, we check if it is less than pi and higher than pi, a considerable median value.

## Step 18: The Concave Polygon Algorithm

The *concave polygon algorithm* relies on the fact that, for a concave polygon, a point inside it is always to the left of the edges (if we are looping through them in a counter-clockwise sense) or to the right of the edges (if we are looping through them in a clockwise sense).

Imagine standing in a room shaped like the image above, and walking around the edges of it with your left hand trailing along the wall. At the point along the wall where you are closest to the point you are interested in, if it's on your right then it must be inside the room; if it's on your left then it must be outside.

The problem lies in determining whether a point is to the left or right of an edge (which is basically a vector). This is done through the following formula:

That formula returns a number less than 0 for points to the right of the edge, and greater than 0 for points to the left of it. If the number is equal to 0, the point lies on the edge, and is considered inside the shape. The code is the following:

public function isPointInsideShape3(point:EuclideanVector, shapeVertices:Vector.<EuclideanVector>):Boolean { var numberOfSides:int = shapeVertices.length; var i:int = 0; var firstEdgePoint:EuclideanVector; var secondEdgePoint:EuclideanVector; var leftOrRightSide:Boolean; while(i < numberOfSides) { firstEdgePoint = shapeVertices[i]; secondEdgePoint = shapeVertices[(i + 1) % numberOfSides]; if(i == 0) { // Determining if the point is to the left or to the right of first edge // true for left, false for right leftOrRightSide = ((point.position.y - firstEdgePoint.position.y) * (secondEdgePoint.position.x - firstEdgePoint.position.x)) - ((point.position.x - firstEdgePoint.position.x) * (secondEdgePoint.position.y - firstEdgePoint.position.y)) > 0; } else { // Now all edges must be on the same side if(leftOrRightSide && ((point.position.y - firstEdgePoint.position.y) * (secondEdgePoint.position.x - firstEdgePoint.position.x)) - ((point.position.x - firstEdgePoint.position.x) * (secondEdgePoint.position.y - firstEdgePoint.position.y)) < 0) { // Not all edges are on the same side! return false; } else if(!leftOrRightSide && ((point.position.y - firstEdgePoint.position.y) * (secondEdgePoint.position.x - firstEdgePoint.position.x)) - ((point.position.x - firstEdgePoint.position.x) * (secondEdgePoint.position.y - firstEdgePoint.position.y)) > 0) { // Not all edges are on the same side! return false; } } i++; } // We looped through all vertices and didn't detect different sides return true; }

This code works regardless of whether you have the shape's vertices defined clockwise or counter-clockwise.

## Step 19: Ray Casting

Ray casting is a technique often used for collision detection and rendering. It consists of a ray that is cast from one point to another (or out to infinity). This ray is made of points or vectors, and generally stops when it hits an object or the edge of the screen. Similarly to the point-in-shape algorithms, there are many ways to cast rays, and we will see two of them in this post:

- The Bresenham's line algorithm, which is a very fast way to determine close points that would give an approximation of a line between them.
- The DDA (Digital Differential Analyzer) method, which is also used to create a line.

In the next two steps we will look into both methods. After that, we will see how to make our ray stop when it hits an object. This is very useful when you need to detect collision against fast moving objects.

## Step 20: The Bresenham's Line Algorithm

This algorithm is used very often in computer graphics, and depends on the convention that the line will always be created pointing to the right and downwards. (If a line has to be created to the up and left directions, everything is inverted later.) Let's go into the code:

public function createLineBresenham(startVector:EuclideanVector, endVector:EuclideanVector):Vector.<EuclideanVector> { var points:Vector.<EuclideanVector> = new Vector.<EuclideanVector>(); var steep:Boolean = Math.abs(endVector.position.y - startVector.position.y) > Math.abs(endVector.position.x - startVector.position.x); var swapped:Boolean = false; if (steep) { startVector = new EuclideanVector(new Point(startVector.position.y, startVector.position.x)); endVector = new EuclideanVector(new Point(endVector.position.y, endVector.position.x)); } // Making the line go downward if (startVector.position.x > endVector.position.x) { var temporary:Number = startVector.position.x; startVector.position.x = endVector.position.x; endVector.position.x = temporary; temporary = startVector.position.y; startVector.position.y = endVector.position.y endVector.position.y = temporary; swapped = true; } var deltaX:Number = endVector.position.x - startVector.position.x; var deltaY:Number = Math.abs(endVector.position.y - startVector.position.y); var error:Number = deltaX / 2; var currentY:Number = startVector.position.y; var step:int; if (startVector.position.y < endVector.position.y) { step = 1; } else { step = -1; } var iterator:int = startVector.position.x; while (iterator < endVector.position.x) { if (steep) { points.push(new EuclideanVector(new Point(currentY, iterator))); } else { points.push(new EuclideanVector(new Point(iterator, currentY))); } error -= deltaY; if (error < 0) { currentY += step; error += deltaX; } iterator++; } if (swapped) { points.reverse(); } return points; }

The code will produce an AS3 Vector of Euclidean vectors that will make the line. With this Vector, we can later check for collisions.

## Step 21: The DDA Method

An implementation of the *Digital Differential Analyzer* is used to interpolate variables between two points. Unlike the Bresenham's line algorithm, this method will only create vectors in integer positions for simplicity. Here's the code:

public function createLineDDA(startVector:EuclideanVector, endVector:EuclideanVector):Vector.<EuclideanVector> { var points:Vector.<EuclideanVector> = new Vector.<EuclideanVector>(); var dx:Number; var dy:Number; var _x:Number = startPoint.position.x; var _y:Number = startPoint.position.y; var m:Number; var i:int; dx = endPoint.position.x - startPoint.position.x; dy = endPoint.position.y - startPoint.position.y; if (Math.abs(dx) >= Math.abs(dy)) m = Math.abs(dx); else m = Math.abs(dy); points.push(new EuclideanVector(new Point(int(_x), int(_y)))); i = 1; while (i <= m) { _x += dx / m; _y += dy / m; points.push(new EuclideanVector(new Point(int(_x), int(_y)))); i++; } return points; }

This code will also return an AS3 Vector of Euclidean vectors.

## Step 22: Checking for Collisions Using Rays

Checking collision via rays is very simple. Since a ray consists of many vectors, we will check for collisions between each vector and a shape, until one is detected or the end of the ray is reached. In the following code, `shapeToCheck`

will be a shape just like the ones we have been using in Steps 13-16. Here's the code:

public function checkRayCollision(ray:Vector.<EuclideanVector>, shape:Vector.<EuclideanVector>):Boolean { var rayLength:int = ray.length; var i:int = 0; while(i < rayLength) { if(isPointInsideShape1(ray[i], shape)) { return true; } i++; } return false; }

You can use any point-inside-shape function you feel comfortable with, but pay attention to the limitations of the last one!

## Conclusion

You're ready to start using this knowledge everywhere now! It will be useful many times, and will save you a lot of extra calculations when trying to do more complex things in Flash.

Envato Tuts+ tutorials are translated into other languages by our community members—you can be involved too!

Translate this post