Efficient Detection of Collision between Ellipse and Many Squares

isTokenInRegion.ts

/**
 * Creates a corner rect.
 *
 * `Rect` has slightly different semantics and isn't as suitable for inclusive
 * `GridPoint` rectangles like were dealing with here.
 */
function createGridAlignedRect(
    position: GridPoint,
    width: number,
    height: number
): PlainCornerRect<GridPoint> {
    return {
        topLeft: floorCoordinates(position),
        bottomRight: superFloorCoordinates(
            addCoordinates(position, [width, height])
        ),
    };
}

/**
 * Check if a rect (with integer grid points) is in the region.
 *
 * The left and right edges of the rect are inclusive.
 */
function isGridAlignedRectInRegion(
    rect: PlainCornerRect<GridPoint>,
    test: (x: number, y: number) => boolean
): boolean {
    for (let ix = rect.topLeft[0]; ix <= rect.bottomRight[0]; ++ix) {
        for (let iy = rect.topLeft[1]; iy <= rect.bottomRight[1]; ++iy) {
            if (test(ix, iy)) {
                return true;
            }
        }
    }

    return false;
}

/**
 * Determines if a token is in a grid-aligned region.
 *
 * `test` will always be given integer coordinates. These will be the grid
 * cells that the token is within. It should return `true` if that point is
 * within the test region.
 */
export default function isTokenInRegion(
    token: Token,
    test: (x: number, y: number) => boolean
): boolean {
    const width = token.width ?? 1;
    const height = token.height ?? 1;

    if (
        (width < 6 || height < 6) &&
        Number.isInteger(token.position[0]) &&
        Number.isInteger(token.position[1])
    ) {
        const rect = createGridAlignedRect(token.position, width, height);
        return isGridAlignedRectInRegion(rect, test);
    } else {
        const a = width / 2;
        const b = height / 2;

        const tokenCenterX = token.position[0] + a;
        const tokenCenterY = token.position[1] + b;

        // If the token was centered on the origin, (-rx, ry) would be the top
        // left corner of the largest rect that token could contain, and
        // (rx, -ry) would be the bottom right corner. We'll call this rect
        // the inscribed rect.
        // https://www.desmos.com/calculator/ysmb2bxdw2
        const rx = a / Math.SQRT2;
        const ry = b / Math.SQRT2;

        // The inscribed rect is easy and fast to check, so do that first
        const inscribedRect = createGridAlignedRect(
            [tokenCenterX - rx, tokenCenterY - ry],
            rx * 2,
            ry * 2
        );
        if (isGridAlignedRectInRegion(inscribedRect, test)) {
            return true;
        }

        for (
            let xu = inscribedRect.topLeft[0];
            xu <= inscribedRect.bottomRight[0];
            ++xu
        ) {
            // Transform the untransformed xu so we're once again dealing with
            // the token as if it was centered on the origin.
            const x = xu - tokenCenterX;

            // yd is maximized when abs(x) is minimized. So we'll
            // find the smallest abs(x) within the column (ie: in [x, x+1]).
            let minX: number;
            if (x < 0 && x + 1 > 0) {
                // 0 is within this column, and nothing's smaller than 0
                minX = 0;
            } else if (Math.abs(x) < Math.abs(x + 1)) {
                minX = x;
            } else {
                minX = x + 1;
            }

            // Calculate y delta. This is the distance between the x-axis and
            // the top edge of the ellipse.
            const yd = (b * Math.sqrt(a * a - minX * minX)) / a;
            if (Number.isNaN(yd)) {
                // We're outside the bounds of the ellipse
                continue;
            }

            for (
                let iy = Math.floor(tokenCenterY - yd);
                iy < inscribedRect.topLeft[1];
                ++iy
            ) {
                if (test(xu, iy)) {
                    return true;
                }
            }

            for (
                let iy = superFloor(tokenCenterY + yd);
                iy > inscribedRect.bottomRight[1];
                --iy
            ) {
                if (test(xu, iy)) {
                    return true;
                }
            }
        }

        // Do the same thing we did for columns, for rows.
        for (
            let yu = inscribedRect.topLeft[1];
            yu <= inscribedRect.bottomRight[1];
            ++yu
        ) {
            const y = yu - tokenCenterY;

            let minY: number;
            if (y < 0 && y + 1 > 0) {
                minY = 0;
            } else if (Math.abs(y) < Math.abs(y + 1)) {
                minY = y;
            } else {
                minY = y + 1;
            }

            const xd = (a * Math.sqrt(b * b - minY * minY)) / b;
            if (Number.isNaN(xd)) {
                continue;
            }

            for (
                let ix = Math.floor(tokenCenterX - xd);
                ix < inscribedRect.topLeft[0];
                ++ix
            ) {
                if (test(ix, yu)) {
                    return true;
                }
            }

            for (
                let ix = superFloor(tokenCenterX + xd);
                ix > inscribedRect.bottomRight[0];
                --ix
            ) {
                if (test(ix, yu)) {
                    return true;
                }
            }
        }

        return false;
    }
}