Cardinal directions

27 Nov 2018

https://gamedev.stackexchange.com/questions/49290/whats-the-best-way-of-transforming-a-2d-vector-into-the-closest-8-way-compass-d^[1]

I adapted the answers and plotted the results:

Ilmari Karonen’s answer based on atan2:

function octant1(vector) {
    let angle = Math.atan2(vector.y, vector.x);
    let octant = Math.round(8 * angle / (2*Math.PI) + 8) % 8;
    return octant;
}

Lars Viklund’s answer based on dot products:

let candidates = [];
for (let octant = 0; octant < 8; octant++) {
    candidates.push({x: Math.cos(Math.PI * octant/4), y: Math.sin(Math.PI * octant/4)});
}

function octant2(vector) {
    function dot(a, b) { return a.x * b.x + a.y * b.y; }

    let bestOctant = 0, bestDotProduct = 0.0;
    for (let octant = 0; octant < 8; octant++) {
        let dotProduct = dot(vector, candidates[octant]);
        if (dotProduct > bestDotProduct) {
            bestOctant = octant;
            bestDotProduct = dotProduct;
        }
    }
    return bestOctant;
}

ChrisC’s answer based on complex numbers (although it seems the same as if you had used vectors):

function octant3(vector) {
    const quadrantToOctant = [5, 6, 7, 4, 0, 0, 3, 2, 1];
    let scale = Math.max(1e-6, Math.max(Math.abs(vector.x), Math.abs(vector.y)));
    let xDirection = Math.round(vector.x / scale);
    let yDirection = Math.round(vector.y / scale);
    let quadrant = (yDirection+1)*3 + (xDirection+1);
    return quadrantToOctant[quadrant];
}

As pointed out in the comments by izb, this fails! It switches octants at the wrong angle. It switches when the ratio vector.x / vector.y crosses 0.5, which causes the rounded value go switch from 0 to 1. That’s arctan(0.5) which is 26.565°. So it’s clever but it doesn’t quite work like the others. Let’s try to fix it.

With complex numbers, multiplication involves rotation. If you start with East and multiply it by 1/8th of a circle rotation (call this M), you end up in the next octant. Each time you multiply, you move one quadrant. So one way to think about this is to ask how many rotations does it take to go from East to where we are now? Equivalently, how many multiplications does it take?

where we are now V = East * M * M * M * … (N times)

where we are now V = East * M^N

N = logarithm(base M) of V

So we need a logarithm in complex number space^[2]. This involves arctangent. So we are back to arctangents! A logarithm in base M is log(V)/log(M), which means atan2(V.y, V.x) / atan2(M.y, M.x). Since M is 1/8th of a circle this ends up being 8 * atan2(V.y, V.x). This is the same solution as at the top of the page.

1 Appendix: drawing code#

All the code for this page is displayed on this page. Here’s the rest:

function fillCanvas(canvas, calculateOctant) {
    const octantToColor = [
        [180, 130, 50], [150, 180, 50], [50, 180, 50], [50, 180, 150],
        [50, 130, 180], [80, 50, 180], [180, 50, 180], [180, 50, 80],
    ];
    const ctx = canvas.getContext('2d');
    const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
    const pixels = imageData.data;

    for (let x = 0; x < canvas.width; x++) {
        for (let y = 0; y < canvas.height; y++) {
            let start = 4 * (y * canvas.width + x);
            let octant = calculateOctant({x: 3*(x/canvas.width - 0.5),
                                          y: 3*(y/canvas.height - 0.5)});
            for (let channel = 0; channel < 3; channel++) {
                pixels[start+channel] = octantToColor[octant][channel];
            }
            pixels[start+3] = 255;
        }
    }
    ctx.putImageData(imageData, 0, 0);
}

fillCanvas(document.getElementById('octant1'), octant1);
fillCanvas(document.getElementById('octant2'), octant2);
fillCanvas(document.getElementById('octant3'), octant3);

1 Appendix: drawing code#

Endnotes