Algorithms & Equations

Table of Contents

  1. Project a point from 3D into 2D
  2. Vector reflection
  3. Intersection of two ellipses
  4. Calculate angle between two points
  5. Intersection between two line segments
  6. Calculate length of a line segment (Distance between two points)
  7. Distance of a point from a line
  8. Intersection of a circle and a line
  9. Intersection of an ellipse and a line
  10. Detect if a point lies inside a capsule
  11. Detect if a point lies inside a triangle
  12. Calculate distance of a point from a plane
  13. Projectile Motion


  1. Projection of 3D into 2D

    A - Point in 3D space to be projected
    B - 2D projection of A
    C - Location of camera in 3D space
    D - Translation of A into coordinate system as defined by C
    E - Viewer position in camera space
    R - Rotation of camera

    D.x = cos(R.y) * [sin(R.z)*(A.y-C.y) + cos(R.z) * (A.x-C.x)] - sin(R.y)*(A.z-C.z)

    D.y = sin(R.x) * [cos(R.y)*(A.z-C.z) + sin(R.y) * [sin(R.z)*(A.y-C.y) + cos(R.z)*(A.x-C.x)]] + cos(R.x)*[cos(R.z)*(A.y-C.y)-sin(R.z)*(A.x-C.x)]

    D.z = cos(R.x) * [cos(R.y)*(A.z-C.z) + sin(R.y) * [sin(R.z)*(A.y-C.y) + cos(R.z)*(A.x-C.x)]] - sin(R.x)*[cos(R.z)*(A.y-C.y)-sin(R.z)*(A.x-C.x)]

    B.x = (D.x - E.x) * (E.z / D.z)
    B.y = (D.y - E.y) * (E.z / D.z)

  2. Reflection

    Calculate the reflection of a vector from a surface.
    I - Incoming source, vector to be reflected (normalized)
    N - Normal of impacted surface (normalized)
    R - Reflected vector

    R = 2N*(N · I) - I

  3. Intersection of 2 ellipses

    Easiest way to test for this intersection is to convert the ellipses into circles. Convert one ellipse into a unit circle (circle with a radius of 1) then convert the other ellipse using the same transformation.

    A - ellipse A
    A.x, A.y - ellipse center
    A.rx, A.ry - radii of ellipse on X and Y axis, respectively
    B = ellipse B
    tA = transformed ellipse A
    tB = transformed ellipse B

    tA.x = A.x / A.rx
    tA.y = A.y / A.ry
    tB.x = B.x / A.rx
    tB.y = B.y / A.ry
    tB.rx = B.rx / A.rx
    tB.ry = B.ry / A.ry
    Now find the point on ellipse B nearest to the unit circle(ellipse A)

    angle# = atanfull(tA.x-tB.x, tA.y-tB.y)
    x# = tB.x + sin(angle#)*tB.rx
    y# = tB.y + cos(angle#)*tB.ry

    Finally, check the distance. If the center of transformed ellipse A and point [x,y] is less than or equal to 1 then the ellipses intersect.

    if (tA.x-x#)^2 + (tA.y-y#)^2 <= 1.0 then TRUE

  4. Angle between two points

    In regards to the equations above, if you don't know what atanfull does or the language you're using doesn't have such a function, it calculates the angle between two points. You can review SOHCAHTOA to understand how this works, but here is the function broken down:

    if x <> 0
        angle = 90 - atan(y / x)
    else
        if y < 0 then angle = 180
        if y > 0 then angle = 0
    endif
    if x < 0 then angle = 180 + angle

    This can be useful for determining which direction an object should face towards a given point.

  5. Intersection of 2 line segments

    Finds the intersection time t of line[A,B] through line[C,D]. If line segments intersect, time value will be in set [0,1]. If value is outside of this range, the lines may intersect, but the segments do not.

    n = [(D.x-C.x) * (A.y-C.y)] - [(D.y-C.y) * (A.x-C.x)]
    d = [(D.y-C.y) * (B.x-A.x)] - [(D.x-C.x) * (B.y-A.y)]
    t = n / d

    Repeat the above calculation but flip the order of the two lines to find the intersection time in relation to the other line segment and also check it's range is within 0 and 1. If both are in range, then the segments do indeed intersect.

    To find the point of intersection, I:

    I.x = A.x + (B.x - A.x)*t
    I.y = A.y + (B.y - A.y)*t

    The intersection you would only need to calculate once, but to determine

  6. Length of a line

    Finds the length of line[A,B] (distance from A to B).

    x = B.x - A.x
    y = B.y - A.y
    length = sqrt(x^2, y^2)

  7. Distance of a point from a line

    Finds the distance of point P from line[A,B].

    x = B.x - A.X
    y = B.y - A.y
    n = [(P.x - A.x) * x] + [(P.y - A.y) * y]
    d = x^2 + y^2
    u = n / d

    If u is in the range [0,1] the point P is within the endpoints of the line segment. If you're only concerned about the distance between the point and an infinite line then you can ignore that check.
    Point I is the closest point on the line to point P. So to find the distance of P from [AB], calculate the length of line [IP].
    I.x = A.x + (B.x - A.x)*u
    I.y = A.y + (B.y - A.y)*u
    e = P.x - I.x
    f = P.y - I.y
    distance = sqrt(e^2, f^2)

  8. Intersection of a circle and a line

    To determine if a line and a circle intersect, simply calculate the distance from the circle's center point to the line. If the distance is less than or equal to the circle's radius, then the two intersect.

  9. Intersection of an ellipse and a line

    Nearly identical to the above method, but with an extra step. Transform the ellipse into a circle and transform the remaining coordinates used in the problem into the same space as used to transform the ellipse.
    Given ellipse E and line L with endpoints [A,B] and [C,D], transform the ellipse into circle C with a radius of 1:

    L.ax = L.ax / E.rx
    L.ay = L.ay / E.ry
    L.bx = L.bx / E.rx
    L.by = L.by / E.ry
    C.x = E.x / E.rx
    C.y = E.y / E.ry
    C.r = 1

    Now find the distance from point [C.x,C.y] from the transformed line L. If the distance is less than or equal to 1 then the ellipse and line intersect.

  10. Point in a capsule

    Another simple problem solved by finding the distance of a point from a line. Assuming you can define your capsule using the endpoints of a line segment [A,B] and radius r:

    If the distance of point P from line segment [A,B] is less than or equal to the radius r of the capsule, then the point is inside the boundaries of the capsule.

    Note: If you would like to check between a circle rather than a point on a line, use the circle's center coordinates as point P and find the distance from the line making up the capsule. If the distance is less than the combined size of the capsule's radius and the circle's radius, the circle and capsule intersect. Using an ellipse instead only requires you to convert the ellipse into a circle with a radius of 1 and tranforming the capsule according to the same spacial proportions.

  11. Point in a 2D triangle

    Determine if point P is inside triangle[A,B,C].
    First, you need to know the order of the vertices. Next, if any of the statements in the function below hold true then the point is outside of the triangle and we can exit the function early. If all statements are false then the point is inside the triangle and we can return true.
    Essentially, what is being done is determining which side the point lies in relation to the line segments making up the triangle, which is why knowing the order of the vertices is so important.

    		function pointInTriangle(P, A, B, C)
			v = B.x - A.x
			q = B.y - A.y
			r = C.x - B.x
			t = C.y - B.y

			// if vertices are clockwise
			if (v*t - q*r) < 0
				if v*(P.y-A.y) >= q*(P.x-A.x) then exitfunction 0
				if r*(P.y-B.y) >= t*(P.x-B.x) then exitfunction 0
				if (A.x-C.x)*(P.y-C.y) >= (A.y-C.y)*(P.x-C.x) then exitfunction 0
			// vertices are counter-clockwise
			else
				if v*(P.y-A.y) < q*(P.x-A.x) then exitfunction 0
				if r*(P.y-B.y) < t*(P.x-B.x) then exitfunction 0
				if (A.x-C.x)*(P.y-C.y) < (A.y-C.y)*(P.x-C.x) then exitfunction 0
			endif
		endfunction 1

  12. Distance of a point from a plane

    R is any point on the plane and N is the normal of the plane. The following will calculate the distance of point P from the described plane.

    a = [N.x * (P.x - R.x)] + [N.y * (P.y-R.y)] + [N.z * (P.z-R.z)]
    b = sqrt(N.x^2 + N.y^2 + N.z^2)
    distance = a / b

  13. Projectile Motion

    P = initial starting point
    t = time index
    V = velocity vector
    g = gravity

    x = P.x + V.x*t
    y = P.y + V.y*t
    z = P.z + V.z*t - 0.5*g*t^2

    You can determine the time at which the projectile reaches its maximum height using the following equation:
    t = V.z / g

    To calculate the maximum height, use the following:
    h = P.z + (V.z^2 / 2g)

    The maximum horizontal distance a projectile will travel (its range) takes twice the time it takes to reach its maximum height, as describe in this equation:
    t = (2 * V.z) / g

    And to calculate that range across a horizontal x-z plane lying at P.y:
    r = (2 * V.x * V.z) / g

    Note: To determine the components of the velocity vector where the initial speed is 50m/s shot at an angle of 65 degrees from the horizontal x-z plane and rotated along the Y-axis at 108 degrees:

    d = 50 * cos(65)
    V.x = d * sin(108)
    V.y = 50 * sin(65)
    V.z = d * cos(108)



Back to top