Description Quicksort is a very fast, very efficient "divide and conquer" sorting algorithm invented by Tony Hoare in 1960 in Moscow State University. The algorithm works this way: First, a pivot is chosen (for this example, we will use the low index. A more efficient pivot would be the median of the first, middle and last values, but we'll keep it simple for this example). Then, the elements of the array are compared Read More

Description The Insertion sort is a sorting algorithm that takes each item and places it into the sorted list. The algorithm works this way: It iterates through the array once. It will take the current element and compare it with the previous element, if it's smaller, then it will keep comparing it with elements down the list until it finds the place to insert it and then move to the next element. This Read More

Description The Gnome sort is a very basic sorting algorithm that combines the Insertion sort and the Bubble sort. The code size is very small and easy to understand, uses only one loop and it's a stable algorithm. Unfortunately, it's not very fast compared to other algorithms. It was invented by Hamid Sarbazi-Azad in 2000. The algorithm works this way: It iterates through the array, comparing the current element with the previous one. If it Read More

Intro: The main part of the project I’m currently working on is about traveling around little planets. For some calculations, we needed to know the distance between two objects standing on the planet, so, we had to do some research on how to find the spherical distance between two points. The “great-circle distance” formula required latitudes and longitudes and contained square roots, divisions, and many trigonometric functions, which are not really something Read More

Our previous moving sphere to sphere function works for when the moving sphere starts outside the static sphere sphere, but for when the moving sphere is inside the static sphere, it automatically says there was a collision. In the case we have a smaller moving sphere starting inside a bigger static sphere and we want to check for when it collides with the containing sphere’s edge, we will need to tweak Read More

A moving sphere to a static sphere test is basically a slightly modified ray to sphere test. First, we expand the static sphere’s radius by the moving sphere’s radius. Then, we call our ray to sphere function, sending the normalized velocity vector as the ray’s direction. Then, we just need to check if the collision point is actually within the boundaries of the line created by the trajectory, so we check if Read More

In our previous ray to sphere test, we just checked if the ray collided with the sphere. Sometimes, however, we need to check the time value in which this collision happens. The test is similar, however, some things need to be added. The distance between a point ‘P’ on the very edge of the sphere to the center of the sphere would be equals to the radius of the sphere. So, if we Read More

This function will allow us to check if a sphere is colliding with a plane. Our half space test helped us see if a point was in front of a plane, on a plane or behind a plane, so, we can base ourselves on that one and, after editing it a little, transform it into a sphere to plane check. First, we make a vector from a point on the plane Read More

This test can be used for when testing the collision between a ray or a line segment against a sphere. First, we need the direction of the ray. If we were checking against a line segment, we will then just use the normalized vector from the beginning of the line segment to the end. We create a new vector from the ray’s beginning point to the center of the sphere, and we Read More

The half-space test allows us to see the position of a point respective to a plane. We can determine if this point is in front of the plane, behind the plane or on the plane. This is a very useful test, as it is used in many types of collision detection functions, especially when testing against triangles. Depending on whether or not we have a point on the plane we’re testing against, Read More