Intersection Points Between a Line and a Circle

Most of the time people want to know if a circle is colliding with a line or not (you can do that by finding the shortest distance and check if it's equal or less to the width of the radius). But what if you need to know exactly where the line is intersecting the circle?

First we need to take into account the equation of the line and the circle:

y = m x + b

(x - C_x)² + (y - C_y)² = r²

But before replacing the Y in the circle equation we're going to expand it, using this formula:

(a - b)²  =  a² - 2ab + b²

So:

(x - C_x)² + (y - C_y)² = r²  <=>  x² - 2xC_x + C_x² + y² - 2yC_y + C_y² = r²

And by replacing the Y we get this:

x² - 2xC_x + C_x² + (m x + b)² - 2(m x + b) C_y + C_y² = r²

x² - 2xC_x + C_x² + (m x)² + 2mxb + b² - 2mxC_y - 2bC_y + C_y² = r²

Instead of trying to make the equation equal to X, we can use the quadratic equation instead:

ax² + bx + c = 0

x =  -b ± √(b² - 4ac) 
                 2a

So the quadratic equation for our intersection will be:

x² + (m x)² - 2xC_x + 2mxb - 2mxC_y + C_x² + b² - 2bC_y + C_y² - r² = 0

(m² + 1)x² + (-2C_x +2mb - 2mC_y)x + (C_x² + b² - 2bC_y + C_y² - r²) = 0

From here we just need to replace the values with the ones in the quadratic equation to find the Xs and then use those values in the line equation to determine the Y coordinate of the intersection points.

But what if the line isn't intersecting the circle? Or if the intersection point is actually a tangent?
There's a simple way to check which of the 3 situations is occurring before calculating the coordinates of the points.

If we take into account this section of the quadratic equation:

Δ = b² - 4ac

if ( Δ < 0 ) {
     // The line isn't intersecting the circle
}

if ( Δ == 0 ) {
     // The line is tangent to the circle
}

if ( Δ > 0 ) {
     // The line intersects the circle
}

Read more...

Polygon Collision Detection

Detecting collisions for regular polygons is relatively simple.
A square will always have 4 sides, a pentagon will always have an internal angle of 108º and so on. Their shapes and properties are always the same, no matter their size or position.

But what if we're dealing with irregular polygons?
They can assume an infinite number of shapes, sides and angles. They're impossible to predict!

The first thing we need to learn is how we tell if a point is inside a polygon or not. There are several techniques, but I'm going to use the Jordan Curve Theorem.

This theorem basically says that a closed shape divides the space in an "inside" and an "outside" areas. And if a point is inside the shape, when you cast a ray it will always have an odd number of intersections with the shape's boundaries.
There is one exception however. If the point is inside, but the ray passes through exactly at one of the vertices, the number of intersections is even, not odd.

So if we have a point (p) and the list of points that define the polygon, the first thing we need to do is define a line that passes through the point. Personally I always define a vertical line, to make the next calculations easier.

x = p_x

The next thing we need to do is loop through the polygon points and find the equation of the line for each edge. Then we just need to replace the X with the value of the vertical line to find the intersection point of both lines (and check if it's within the edge's boundaries).

y = m p_x + b

But since we're dealing with a full line and not a semi-straight line passing through the point, we need to count the amount of intersections that are occurring below and above the point.

if ( y < p_y ){
     // The intersection is below the point
}

if ( y > p_y ){
     // The intersection is above the point
}

As for detecting the collision between 2 polygons, finding out if the vertices of one polygon is inside the other isn't enough, because it can be only the edges that are colliding.
So we need to loop between the vertices of both polygons, define the lines and find out if the they're intersecting each other, as it's explained here.

Read more...

Finding a Point in the Line at a Specific Distance

Imagine that you have a line, a point (p1) belonging to that line and you need to find a 2nd point (p2), also belonging to the line, that's at a specific distance (d) from the 1st point.
We could try to find the circle that has p1 as the center and d as the radius and check where the circle intersects with the line. But I want to try a different method that uses the line's slope and trigonometry.

First we have to take into account the equation that define the slope (m) of a line:

m =  y₂ - y₁ 
        x₂ - x₁

If we take a closer look, and remember how the trigonometric functions are tied to finding the projections of a line, we see that the slope is in fact this:

m = tan α

This means we can use the other 2 trigonometric equations that define the projections from the line to find the coordinates of the 2nd point:

sen α =  y₂ - y₁   <=> y₂ = d sen α + y₁
                d

cos α =  x₂ - x₁   <=> x₂ = d cos α + x₁
                 d

And to find how much the angle is we just need to used this:

m = tan α  <=>  α = arctan (m)

Read more...

Shortest Distance Between a Point and a Line

Knowing if 2 objects are touching each other is only a part of collision detection. There are occasions when knowing how far each object is from each other is just as important.

Finding the shortest distance between 2 points is done with the Distance Formula. And the same goes for finding the distance between a point and a circle (you just need to check the distance between the point and the center and subtract the radius).
But the distance between a point and a line (or between other polygons defined with straight lines) is found through a different method.

We can draw an infinite number of lines starting from a single point, but only one of them is the shortest distance between that point and another line that doesn't pass through it (if it did the distance would be zero). That said line is the perpendicular!

The perpendicular line has a very interesting property. If the slope of the other line is m, then (in order to make the 90º angle) the slope of the perpendicular is:

_   1  
     m

Knowing that all we need is to find the y-intercept (b) to finish the equation of the perpendicular line. And we can do that because we have the coordinates of point to replace the X and Y and reach the final value.
So starting from the line equation, the formula will be like this:

y = m x + b  <=>  b = y - m x

Once we have the equation for the perpendicular line determined, all we need to do is to find the intersection point between the 2 lines and calculate the distance between both points with the Distance Formula.

But there's an extra step we need to do if the other line is a line segment and not an infinite line. After finding the intersection point, we need to check if it's within the segment's boundaries, like shown here. If it's not then we just need to check the distance between the point and the line edges and see which one is the shortest.

Another thing we need to pay attention is if we're dealing with vertical or horizontal lines.
This is the only situation where the distance is being projected on a single axis, so the calculation is really straight-forward:

Vertical line:
distance = L_x - p_x

Horizontal line:
distance = L_y - p_y

Read more...

Simple Line Collision Detection

It might not be obvious at first, but Line Intersections are actually very handy.
For example, you can use them to define complex polygon shapes (octagons, stars, etc) and from there calculate the collision between them!

But in order to determine where the lines collide with each other, we first need the equation of a straight line:

y = m x + b

m =  y₁ - y₂  
        x₁ - x₂

So to determine any given point of a line we need to know its slope (m) and its y-intercept (b). Then all we need to do is give a X coordinate to obtain the corresponding Y coordinate of the point.

As for determining if a point belongs to a line, all we need to do is to use the point's X coordinate and check if the resulting Y matches the point's.

There are 2 exceptions we have to keep in mind however, vertical and horizontal lines. These follow special equations, where b is a constant value:

x = b

y = b

Now unless 2 lines have the same slope (which makes them parallel), they will intersect at some point, even if it's far off in space.
So the first thing we need is the equation of both lines. Each has its own slope and y-intercept, but because we're trying to find the point they have in common, the X and Y coordinate is the same for both:

y = m₁ x + b₁
y = m₂ x + b₂

From there all we need to do is to replace the Y to make the equations equal to each other and find the X value. Then we just need to replace the X value in either of the equations to get the Y, like in this example.
Just in case it's ever needed, this is how the equation solved to X looks like (it doesn't work for vertical or horizontal lines though):

 x =   b₂ - b₁  
        m₁ - m₂

Now there's only one thing missing. The equations we've used so far stretch into infinity, but what happens when we're dealing with line segments?
The computer would say the red and green lines are colliding, even though we can see the green line ends before it touches the red one.

So once we have the intersection point, we need to find out if it's within the boundaries of both segments:

flag_line1 = false
flag_line2 = false

if ( ( P_x >= L1_x1 AND P_x <= L1_x2 ) OR ( P_x <= L1_x1 AND P_x >= L1_x2 ) OR
     ( P_y >= L1_y1 AND P_y <= L1_y2 ) OR ( P_y <= L1_y1 AND P_y >= L1_y2 ) ) {

     flag_line1 = true
}

if ( ( P_x >= L2_x1 AND P_x <= L2_x2 ) OR ( P_x <= L2_x1 AND P_x >= L2_x2 ) OR
     ( P_y >= L2_y1 AND P_y <= L2_y2 ) OR ( P_y <= L2_y1 AND P_y >= L2_y2 ) ) {

     flag_line2 = true
}

if (flag_line1 == true AND flag_line2 == true ) {

      // The line segments collide
}

Read more...

Simple Circle Collision Detection

Circle are pretty popular. From basketballs and billiard balls to bullseye targets and frisbees, there are plenty of games where circles play an important role.
But unless we're dealing with soap bubbles, we need a way to tell the computer when the circles are colliding.

If we take the Equation of the Circle (with "r" being the radius and "C" the center of the circle) we can easily determine if a point (P) is inside the circle:

( P_x - C_x )² + ( P_y - C_y )² <= r²

But if we want to detect the collision between 2 circles, it's more intuitive to calculate the distance between the centers (C1 and C2) first and then check if it's smaller than the sum of the radius (r1 and r2):

distance = √(( C2_x - C1_x)² + ( C2_y - C1_y)²)

if (  distance  <=  r1 + r2 ){
     // The circles are colliding
}

Read more...

Simple Rectangle Collision Detection

We use collision detection all the time. Grabbing a cup of coffee, scratching our nose, sitting on a chair... even when walking our body detects the presence of other objects and surfaces outside of its own.
For computers it's a bit different. They can't detect anything unless we tell them how.

(Unrotated) rectangle collision is one of the simplest ones. If any point (P) isn't between the coordinates of both axis of the rectangle (R), then it's not colliding:

if ( P_x >= R1_x  AND  P_x <= R2_x  AND
     P_y >= R1_y  AND  P_y <= R2_y){

     // The point is inside the rectangle
}
else{
     // The point is outside the rectangle
}

With 2 rectangles (R1 and R2) we need to check, on both axis, if the coordinates of the edges of the 1st rectangle is between the coordinates of the 2nd:

if ( R1_x2 > R2_x1 AND R1_x1 < R2_x2 AND
     R1_y2 > R2_y1 AND R1_y1 < R2_y2 ){

     // The rectangles collided
}

Read more...

Finding the length of a line (Distance Formula)

I've once heard a story on how Pythagoras came across his Pythagorean Theorem.

One day he was walking on a tiled floor, much like the image above. As he was looking at the pattern it formed, he noticed something amazing. The sum of the squares of the cathetus was equal to the square of the hypotenuse!

Or in mathematical terms: 

a² + b² = c²

But how is this tied to finding the length of a line?
This formula applies to all right-angled triangles, the same type of triangles drawn by the Cartesian coordinate system.

So if we have the length of the X and Y we calculate the length of the line like this:

h² = x² + y²  <=>  h = √( x² + y²)

But if we consider: 

x = x2 - x1

y = y2 - y1

Then the equation can be read like this (which is the distance formula):

 distance = √(( x2 - x1)² + ( y2 - y1)²)

Read more...

Finding the X and Y projections of a line

The traditional screen is like a sheet of paper.
You can draw things in perspective and give the illusion of depth, but ultimately everything is represented in a 2D plane. If you tried to move your head around to see behind an object on screen, the image would remain the same.

The computer uses Cartesian coordinates to describe the positions of the objects along an X and Y axis, like in this example (the direction of the Y-axis is reversed though).

But what if we have a line of a specific length and at a certain angle? How do we know the X and Y coordinates of both ends of the line?

That's possible with trigonometric functions. They relate the angle with the length of the sides of the triangle, which is the shape formed between the line and its X and Y projections.

The equations are basically like this:

sin α =   y    <=>  y = h * sin α
             h

cos α =   x    <=>  x = h * cos α
              h

The h (hypotenuse) is the length of the line, while α is the angle.

And so having calculated the X and Y projections of the line, all you have to do to draw it on the screen is to tell the computer the coordinates of the starting point and add the projections to obtain the coordinates of the ending point.

Read more...

Converting Radians into Degrees and vice-versa

We use angles all the time. How high the sun is in the sky, how much a wheel turns, how much our arm rotates or how much we turn our head...
If it wasn't for that measurement of the circular motion, we wouldn't be able to understand how the stars move or predict their positions during the course of the year (imagine how many people who would get their horoscopes wrong).

We're more used to measure angles in degrees. Pretty much everyone knows if you spin around yourself you make a 360º turn to return to the original position. Or if you stretch out your arms perpendicularly they make a 90º angle.
But in science and engineering radians are much more commonly used. I'm not going on the detail of why, but this site explains both of them quite well.

So when you need to tell a computer, for example, how many degrees it needs to rotate an image when it only accepts values in radians, this is the equations you should use: 

radians = degrees  x  π
                     180

degrees = radians x 180
                        π

Read more...