Triangulator

This is a tool for triangulating a set of points in a space of arbitrary dimensions. THis has various purposes, like finding someone's base in Minecraft using arrow knockback trajectories.

Use it here

Number of dimensions: 2

Start of Location 1
End of Location 1
Start of Location 2
End of Location 2

Explanation

Given the two pairs of points, the tool creates a vector for each point, , , , and .

To calculate a line crossing two points, and , given as the direction vector, we can use the following parametric equation:

Since the direction can be expressed as the difference between the two points, i.e. , we can simplify the equation to:

So we create two of these parametric equations, one for each pair of points, and expand them into the vector form:

Note that I use 0-based indexing for notating elements of the vectors because it's closer to how the code is written. We can then set these two equations equal to each other:

Expand the parametric equation so that it becomes a system of equations:

Only two of them are needed to solve for and , so we can pick any two. Let's pick the first and second equations:

For the sake of simplicity, let's define the following variables for the coefficients and the constants:

Hence, the system of equations becomes:

We will need to solve for and . Two methods are shown below, one using substitution and the other using Cramer's rule. Other methods, like the Row Reduction (Gaussian Elimination) Method, can also be used.

Click to expand for the derivation using substitution

We can express in terms of in the first equation:

Then, we can substitute this into the second equation, after which we can solve for :

Finally, we can substitute this back into the first equation to solve for , which gives us the following:

Click to expand for the derivation using Cramer's rule

The Cramer's rule allows us to solve systems of equations using determinants. Generally, for a system with two variables:

The solution can be expressed as follows:

Where:

• is the determinant of the coefficient matrix,
• is the determinant obtained by replacing the first column of the coefficient matrix with the column vector on the right side, and
• is the determinant obtained by replacing the second column.

To apply this to our system of equations, we can first rearrange our system of equations as follows:

In this case, the coefficient matrix is:

And the column vectors are:

Hence, the determinants are:

Therefore, the solution is:

Solving for and gives us the following:

info

By the way, if you put the values for to back into the system of equations, you'll get this absolute monstrosity of an equation:

Now that we have and , we can finally start doing this inside code. I made a utility file called intersection.ts with the following code:

src/utilities/intersection.ts

import numeric from "numeric";

type Point = number[];
type IntersectionResult = {
    point: Point | null;
    t1: number;
    t2: number;
};

export function findIntersectionPoint(p1: Point, q1: Point, p2: Point, q2: Point): IntersectionResult {
    const a = p1[0];
    const b = q1[0] - p1[0];
    const c = p2[0];
    const d = q2[0] - p2[0];

    const e = p1[1];
    const f = q1[1] - p1[1];
    const g = p2[1];
    const h = q2[1] - p2[1];

    const t2 = (b * (g - e) - f * (c - a)) / (d * f - b * h);
    const t1 = (c - a + d * t2) / b;

    const r1 = numeric.add(p1, numeric.mul(t1, numeric.sub(q1, p1)));
    const r2 = numeric.add(p2, numeric.mul(t2, numeric.sub(q2, p2)));

    return {
        point: numeric.eq(r1, r2) ? r1 : null,
        t1,
        t2,
    };
}

• The numeric package is used for vector operations.
• The findIntersectionPoint takes in two pairs of points and returns the intersection point, if it exists, and the values of and .

That's it. Now we can use this to find the intersection point of two lines created by two pairs of points in any number of dimensions.