get shortest path between 2 points on a cube surface

geo.ts

export type V3D = [number, number, number]
export type V2D = [number, number]

// degree should be multiply of 90
// axis: 0 = x, 1 = y, 2 = z
function rotatePoint(point:V3D, axis: number, degree: number) : V3D {
    const [x, y, z] = point
    const d = (degree % 360 + 360) % 360 // 0, 90, 180, 270
    const s = d === 90? 1 : (d === 270? -1 : 0)
    const c = d === 0? 1 : (d === 180? -1 : 0)
    const matrixMap = [
        [1, 0, 0, 0, c, -s, 0, s, c],
        [c, 0, s, 0, 1, 0, -s, 0, c],
        [c, -s, 0, s, c, 0, 0, 0, 1]
    ]
    const v = matrixMap[axis]
    return [
        v[0] * x + v[1] * y + v[2] * z,
        v[3] * x + v[4] * y + v[5] * z,
        v[6] * x + v[7] * y + v[8] * z,
    ]
}

function pointRotateRight90(x0: number, y0: number, x: number, y: number) {
    return [x0 + y - y0, y0 - x + x0] as V2D
}
function pointRotateLeft90(x0: number, y0: number, x: number, y: number) {
    return [x0 - y + y0, y0 + x - x0] as V2D
}
function pointRotate180(x0: number, y0: number, x: number, y: number) {
    return [x0 - x + x0, y0 - y + y0] as V2D
}
function offset(p: V2D, dx: number, dy: number) {
    return [p[0] + dx, p[1] + dy] as V2D
}

function getLineIntersect(p1: V2D, p2: V2D, p3: V2D, p4: V2D) {
    const a = p2[1] - p1[1]
    const b = p1[0] - p2[0]
    const e = p1[0] * a + p1[1] * b
    const c = p4[1] - p3[1]
    const d = p3[0] - p4[0]
    const f = p3[0] * c + p3[1] * d
    const H = a * d - b * c
    if (H == 0) return p1 as V2D // <- this means the two lines are the same, return p1 for better handling of corner cases
    return [(e * d - f * b) / H, (a * f - c * e) / H] as V2D
}

function shortestPathOnRegulatedCubeSurface(l: number, ufl: V3D, p1: V3D, p2: V3D): V3D[] {
    const m = l / 2
    // rotate so that p1 is at front
    let r1 = [0, 0]
    if (p1[0] === m) r1 = [1, -90]
    if (p1[0] === -m) r1 = [1, 90]
    if (p1[1] === m) r1 = [0, 90]
    if (p1[1] === -m) r1 = [0, -90]
    if (p1[2] === m) r1 = [2, 0]
    if (p1[2] === -m) r1 = [0, 180]
    p1 = rotatePoint(p1, r1[0], r1[1])
    p2 = rotatePoint(p2, r1[0], r1[1])

    // if p2 is at back
    if (p2[2] === -m) {
        const path = shortestPathOnOppositeCubeSurface(l, ufl, p1, p2)
        return path.map(p => rotatePoint(p, r1[0], -r1[1]))
    }

    // if p2 is at front
    if (p2[2] === m) return []

    // otherwise, rotate so that p2 is at top
    let r2 = [2, 0]
    if (p2[0] === m) r2 = [2, 90]
    if (p2[0] === -m) r2 = [2, -90]
    if (p2[1] === -m) r2 = [2, 180]
    p1 = rotatePoint(p1, r2[0], r2[1])
    p2 = rotatePoint(p2, r2[0], r2[1])
    const path = shortestPathOnAdjCubeSurface(l, ufl, p1, p2)
    return path.map(p => rotatePoint(p, r2[0], -r2[1])).map(p => rotatePoint(p, r1[0], -r1[1]))
}

function shortestPathOnAdjCubeSurface(l: number, ufl: V3D, pf: V3D, pu: V3D): V3D[] {
    if (l <= 0 || pf[2] !== ufl[2] || pu[1] !== ufl[1] ||
        pf[0] < ufl[0] || pf[0] > ufl[0] + l ||
        pf[1] > ufl[1] || pf[1] < ufl[1] - l ||
        pu[0] < ufl[0] || pu[0] > ufl[0] + l ||
        pu[2] > ufl[2] || pu[2] < ufl[2] - l) {
            throw new Error('invalid arguments')
    }
    
    const [psx, psy] = [ufl[0], ufl[1]]
    const [pex, pey] = [ufl[0] + l, ufl[1]]
    const [p1x, p1y] = [pf[0], pf[1]]
    const [p2x, p2y] = [pu[0], ufl[1] + ufl[2] - pu[2]]

    if (p2y === p1y) return []

    const cx = (psx + pex) / 2
    const cy = psy + l / 2

    const p2L = offset(pointRotateLeft90(cx, cy, p2x, p2y), -l, 0)
    const p2R = offset(pointRotateRight90(cx, cy, p2x, p2y), l, 0)
    const d2 = (x1: number, y1: number, x2: number, y2: number) => (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) 
    const l1 = d2(p1x, p1y, p2x, p2y)
    const l2 = d2(p1x, p1y, ...p2L)
    const l3 = d2(p1x, p1y, ...p2R)
    const minValue = Math.min(l1, l2, l3)
    
    if (minValue === l1) {
        const p = getLineIntersect([psx, psy], [pex, pey], [p1x, p1y], [p2x, p2y])
        return [
            [p[0], psy, ufl[2]]
        ]
    } else if (minValue === l2) {
        const p1 = getLineIntersect([psx, psy], [psx, psy + 1], [p1x, p1y], p2L)
        const p2 = getLineIntersect([psx, psy], [pex, pey], [p1x, p1y], p2L)
        return [
            [psx, p1[1], ufl[2]], [psx, psy, ufl[2] - (psx - p2[0])]
        ]
    } else if (minValue === l3) {
        const p1 = getLineIntersect([pex, pey], [pex, pey + 1], [p1x, p1y], p2R)
        const p2 = getLineIntersect([psx, psy], [pex, pey], [p1x, p1y], p2R)
        return [
            [pex, p1[1], ufl[2]], [pex, pey, ufl[2] - (p2[0] - pex)]
        ]
    }
    return []
}

function pathsOppositeFU(l: number, ufl: V3D, pf: V3D, pb: V3D) {
    const [psx, psy, psz] = ufl
    const [pex, pey, pez] = [psx + l, psy, psz]
    const [p1x, p1y] = [pf[0], pf[1]]
    const [p2x, p2y] = [pb[0], ufl[1] + l + psy - pb[1]]
    const p1 = [p1x, p1y] as V2D
    const p2 = [p2x, p2y] as V2D
    const ps = [psx, psy] as V2D
    const pe = [pex, pey] as V2D

    const cx = (psx + pex) / 2
    const cy = psy + l + l / 2
    const p2L = offset(pointRotateLeft90(cx, cy, p2x, p2y), -l, 0)
    const p2R = offset(pointRotateRight90(cx, cy, p2x, p2y), l, 0)
    const d2 = (x1: number, y1: number, x2: number, y2: number) => (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)
    return [
        {
            distance: d2(...p1, ...p2L),
            pathFunc: () => {
                const ip1 = getLineIntersect(p1, p2L, ps, pe)
                const ip2 = getLineIntersect(p1, p2L, ps, [psx, psy+1])
                const ip3 = getLineIntersect(p1, p2L, [psx, psy+l], [pex, pey+l])
                return [
                    [ip1[0], psy, psz], 
                    [psx, psy, psz - (ip2[1] - psy)], 
                    [psx, psy - (psx - ip3[0]), psz - l]
                ] as V3D[]
            }
        },
        {
            distance: d2(...p1, ...p2),
            pathFunc: () => {
                const ip1 = getLineIntersect(p1, p2, ps, pe)
                const ip2 = getLineIntersect(p1, p2, [psx, psy+l], [pex, pey+l])
                return [
                    [ip1[0], psy, psz],
                    [ip2[0], psy, psz - l]
                ] as V3D[]
            }
        },
        {
            distance: d2(...p1, ...p2R),
            pathFunc: () => {
                const ip1 = getLineIntersect(p1, p2R, ps, pe)
                const ip2 = getLineIntersect(p1, p2R, pe, [pex, pey+1])
                const ip3 = getLineIntersect(p1, p2R, [psx, psy+l], [pex, pey+l])
                return [
                    [ip1[0], pey, pez], 
                    [pex, pey, pez - (ip2[1] - pey)], 
                    [pex, pey - (ip3[0] - pex), pez - l]
                ] as V3D[]
            }
        }
    ]
}

function shortestPathOnOppositeCubeSurface(l: number, uflr: V3D, pfr: V3D, pbr: V3D): V3D[] {
    const allPaths = [
        ...pathsOppositeFU(l, uflr, pfr, pbr),
        ...pathsOppositeFU(l, uflr, rotatePoint(pfr, 2, 90), rotatePoint(pbr, 2, 90)),
        ...pathsOppositeFU(l, uflr, rotatePoint(pfr, 2, 180), rotatePoint(pbr, 2, 180)),
        ...pathsOppositeFU(l, uflr, rotatePoint(pfr, 2, 270), rotatePoint(pbr, 2, 270)),
    ]

    const minValue = Math.min(...allPaths.map(v => v.distance))
    const index = allPaths.findIndex(v => v.distance === minValue)
    const path = allPaths[index].pathFunc().map(p => rotatePoint(p, 2, -90 * (~~(index / 3))))

    return path
}

/**
 * find shortest path over cube
 * @param l cube size
 * @param ufl the position of upper front left corner of the cube
 * @param p1 the start point on cube surface
 * @param p2 the end point on cube surface
 * @returns the shortest path on the cube surface, not including the start and end points
 */
export function shortestPathOnCubeSurface(l: number, ufl: V3D, p1: V3D, p2: V3D): V3D[] {
    // regulate offset, so that the center of the cube is at [0, 0, 0], this makes rotations easier
    const [offx, offy, offz] = [ufl[0] - -l/2, ufl[1] - l/2, ufl[2] - l/2]
    const [uflr, p1r, p2r] = [ufl, p1, p2].map(v => [v[0] - offx, v[1] - offy, v[2] - offz] as V3D)
        
    const path = shortestPathOnRegulatedCubeSurface(l, uflr, p1r, p2r)
    
    // redo offset
    return path.map(p => [p[0] + offx, p[1] + offy, p[2] + offz] as V3D)
}

console.log(shortestPathOnCubeSurface(2, [0, 2, 2], [0.1, 0.2, 2], [0.2, 0.1, 0]))
result:

[
  [ 0, 0.18181818181818177, 2 ],
  [ 0, 0, 1.0000000000000004 ],
  [ 0.18181818181818188, 0, 0 ]
]