# Intersection.

One of the things that we can find useful about vectors is Intersection. we can find out at which point a vector intersection with the path of another vector. Although this is the sort of thing most programmers will consider useful since it can detect the exact point of collision in a dynamic way. It is not the only way and will not be the one we are going to concentrate on but for general purpose and for the sake of becoming familiar with it I will discuss it in a quick step here. for detail explanation the formula is explained here in detail.

For programming purposes lets establish a few rules. The first rule for a vector to intersect another the vector, the vectors must not be parallel.  Second a calculation must be performed for each vector to determine at what point in the path of the other vector did collision happened.  And third if a collision is to be determined, a collision test must be performed for each of the vectors.

Now lets work toward our example. Lest assume we have two vectors and lets say one is a wall(vector B) and one is a point moving at 100 pixels per frame(vector A). Something like this:

Notice that there is a vector ‘C’ this vector is created from the start of vector a to the start of vector b and is done like this:

C.vx = B.px – A.px
C.vy = B.py – A.py

vx and vy are the vector components, while px and py are the vector position. So far vector ‘C’ does not have a position and since it does not have any other use but to help us figure out the point of collision we are not going to bother with its position. The formula to find the point of collision goes like this.
First we find the perpendicular dot product of vector ‘A’ into vector ‘B’:

dp1 = B.vx * C.vy – B.vy * C.vx
dp2 = A.vx * B.vy – A.vy * B.vx
t = dp1/dp2

“t” in this case is a number that will tell us the exact point of collision. Its a ration that when multiplied by the source vector in this case vector ‘A’ will tell us at what point the collision happened.
to find the exact point of collision for vector ‘A’ to the path of vector ‘B’ the collision will have to be done like this:

p.x = A.px + A.vx * t
p.y = A.py + A.vy * t

One thing to note with this point of collision. is that even if the vector is not colliding with the wall there will still be a point of collision. As stated before ‘t’ is a ratio. The ratio can represent several things. First if ‘t’ is less than 0 then the collision happened in a previous frame. if the collision is greater than 1 then the collision will happen in another frame in the future. if ‘t’ is greater than or equal to 0 or ‘t’ is less than or equal to 1 then the collision happened in the current frame. now if ‘t’ is between 0 and 1 it does not necessarily mean that there is a collision with the wall. To find if there is a collision with the wall, we must check if the wall collides with the path of the point also and to solve that we need to do a reverse collision:

C.vx = A.px – B.px
C.vy = A.py – B.py

dp1 = C.vx * B.vy – C.vy * B.vx
dp2 = B.vx * A.vy – B.vy * A.vx

t2 = dp1/dp2

p.x = B.px + B.vx * t2
p.y = B.py + B.vy * t2

Ok, so now we can determine if there was an actual collision. If both t and t2 are both greater than or equal to 0 and both are less than or equal to 1 then there was an actual collision and p.x,p.y is the point of collision.

Note that due to floating point inaccuracies the p.x,p.y obtained from the second equations may or may not match the p.x,p.y from the first equations but should be pretty close and should be taken into consideration when solving this problem.

The above is the common way of finding the exact point of collision and usable as long as the vector does not have a relationship to an object. But what if one of the vector is the movement of a ball and the other is a wall? A couple of considerations have to be taken  such as the radius of the ball and where the actual ball hits the wall. Consider this illustration:

Lets explain what happens here. the diagram illustrate exactly what happens with in a specific period of time. In computer time this can be a frame and the vector represents how much the ball would move if there was no wall in its path during a single frame. Note that there are two points that represent collision and intersection and do not happen in the same spot. As can be seen the point of collision has very little to do with the vector point of intersection. Since the vector point of intersection is farther than, in this case, the ball radius, We need to find an alternative method to determine the object exact point of collision. There are several ways to do this. One is to move the wall toward the ball the amount of distance of the ball radius during the calculation. The problem with this is that depending from which side the ball is approaching the wall, we need to move the wall in that direction, which is quite a bit of calculations to do to get it right. The other is to move the ball instead of the wall but either way there are too many obstacles to overcome. This Third one, which is the one I like, is not as intensive and resolves the problem in a simpler way. Not  that much simpler but simpler none the less.

—– to be continued ——–

# Vector Examples

Below is a simple illustration on what a vector is and several of its properties. Use the mouse to drag the red dot to change the direction and length of the vector.

There are several things to consider here. Each of the properties is represented by a certain color. The green color is representative of the actual vector, the blue color is representative of the vector’s normal and is 1 unit length (I have stretched it to ten pixels length to make it noticeable) and the Red color is the Vector’s left normal and is also 1 unit length(also stretched to 10 pixels to make it noticeable).
notice how no matter how long the vectors becomes the normals stay the same as long as the vector does not change direction. Finally the left normal is the (y,-x) of the normal(x,y) and the normal(x,y) is vector “A” normalized as explained in the previous “Vector Tutorial – More basics” blog.

Below we have an example of Projection. Use the mouse to move the red dot around to see how the direction of one vector affects it’s projection on on the other vector.

Here vector ‘A’ is being projected into vector ‘B’. Notice that if both vectors are facing in the same direction(less than 90 degrees apart), The Dot Product is positive. If both vectors are facing opposite direction(greater than 90 degrees appart), the dot product is negative. Third, if both vectors are perpendicular(equals to 90 degrees), the Dot Product is “0″, That rule holds true for any vector projected into another vector with either vectors facing any direction. The final thing to note is that the Dot Product, with this conditions, is also the length of the projection. No need to calculate the distance with the Pythagoreans Theorem. That is why when you multiply the Dot Product with the normal you get the actual projection.

Can you guess how to project one vector into another vector’s left normal?

like this:

As can be seen, the left projection works the same as the regular projection with the exception that the projection is perpendicular to the destination vector(vector B). there are several things that we can conclude from this. First, if the dot product is positive, the projection is toward the left of vector ‘B’
if the dot product is negative the projections is toward the right of vector ‘B” and if its 0 its on the vector ‘B’ and third the absolute value of the dot product is the distance the end of vector ‘a’ is from vector b. This is going to become very useful to understand in future explanations. One useful way is if there is a point moving toward a line(vector) or away from it, one can determine how far the dot is from the line.

I hope this is becoming clearer as all of this examples are just illustrations of what has been discussed in earlier posts.

# Projection

A very important and useful part of using vectors is being able to project them. Projection is mainly used to find distances. Lets start defining it: To project a vector, two  vectors are need and always either vector can be projected into the other. Lets assume two vectors are connected by a common starting point(don’t have to be but that’s going to be our representation and is going to be easier to understand) and both vectors can be moving in any direction. lets use this example for ease of use:

first example:
vector C projected onto vector A. The projection is a vector from the start of vector A to a line perpendicular to vector A extending from the end point of Vector C

Second example:
Now lets Assume vector B is a line perpendicular to Vector A this creates an x,y Graph. For general purpose, one angle have to be at any degree while the second one has to be at 90 degrees from the first vector or visa versa to make the graph. While keeping that in mind (and it’s quite important to note), note that vector B is in the direction of Vector A left normal. Now lets project vector C onto Vector B. The projection is a vector from the start of vector B to a line perpendicular to vector B extending from the end point of vector C.

The equation to find the projection(or the new Projected Vector). from vector C into Vector A is done with a couple of equations. First we find the distance from the start of Vector A to the perpendicular line extended from the end of Vector C to the intersection point on Vector A. The equation is the dot Product between vector C and the normal of Vector A:

Remember that the normal of a vector is calculated like this; vector A components are A.vx and A.vy  to find its norma  first we find its length:

length = Sqrt(A.vx*A.vx+A.vy*A.vy)

then the normal(or unit vector):

A.dx = A.vx/length
A.dy = A.vy/length

Then to find the distance (or dotProduct in this special case) from the start of Vector A to its perpendicular line extending from the endpoint of vector C is done this way:

DotProduct = C.vx * A.dx + C.vy * A.dy

so the projection distance now is the DotProduct and to find the new vector all that needs to be done is multiply the DotProduct by “A” vector’s normal:

p1.vx = A.dx * DotProduct
p1.vy = A.dy * DotProduct

now p1 is the new Vector that’s along A vector. it is important to note that these formula, to find the projection, works with two vectors that are less than or equal to plus or minus 180 degrees of difference in direction.

now to find vector p2. For this note that vector p2 is perpendicular to vector A and is along Vector B we really don’t need vector B all we need is its normal. With this in mind it’s worth it  to remember that the vector B normal is the same as vector A perpendicular normal:

B.dx =  A.dy and is the same as P2.dx
B.dy = -A.dx and is the same as P2.dy

so to find the DotProduct(or length in this case) between Vector C and Vector A left normal it is done in this manner C.vx * A.dy + C.vy*(-A.dx) and is the same as this:

DotProduct = C.vx * A.dy – C.vy*A.dx

so the Dot product is the length of the new Vector p2 and to find its components:

p2.vx =  A.dy * DotProduct
p2.vy = -A.dx * DotProduct

Projection is very important to solve distance problems relating a point to a line and is going to be really useful for our vector object library soon to come but First I will post some examples for what we have learn so far also soon to come.