0dot77-comfyui-annotations/web/modules/hitTesting.js

/**
 * Hit Testing Module
 *
 * Provides efficient hit-testing for stroke detection.
 * Used by the eraser tool to determine which strokes to remove.
 *
 * ## Hit-Testing Strategy: Whole Stroke Removal
 *
 * For v1, we use whole-stroke removal (simpler, more performant):
 * - When eraser touches any part of a stroke, the entire stroke is removed
 * - This avoids complex stroke splitting and segment management
 * - Performance: O(n * m) where n = strokes, m = points per stroke
 *
 * ## Optimization Techniques
 *
 * 1. Bounding Box Pre-filter: Skip strokes whose bounding box doesn't
 *    intersect with the eraser area
 * 2. Early Exit: Stop checking a stroke once a hit is found
 * 3. Distance Squared: Avoid sqrt() calls by comparing squared distances
 *
 * ## Future Improvements (v2)
 *
 * - Spatial indexing (quadtree) for large numbers of strokes
 * - Segment-level erasing (split strokes at intersection points)
 * - Stroke thickness consideration in hit detection
 */

/**
 * Calculates the squared distance from a point to a line segment.
 * Using squared distance avoids expensive sqrt() calls.
 *
 * @param {number} px - Point X
 * @param {number} py - Point Y
 * @param {number} x1 - Segment start X
 * @param {number} y1 - Segment start Y
 * @param {number} x2 - Segment end X
 * @param {number} y2 - Segment end Y
 * @returns {number} Squared distance from point to segment
 */
export function pointToSegmentDistanceSquared(px, py, x1, y1, x2, y2) {
    const dx = x2 - x1;
    const dy = y2 - y1;
    const lengthSquared = dx * dx + dy * dy;

    if (lengthSquared === 0) {
        // Segment is a point
        const dpx = px - x1;
        const dpy = py - y1;
        return dpx * dpx + dpy * dpy;
    }

    // Project point onto line, clamped to segment
    let t = ((px - x1) * dx + (py - y1) * dy) / lengthSquared;
    t = Math.max(0, Math.min(1, t));

    // Find closest point on segment
    const closestX = x1 + t * dx;
    const closestY = y1 + t * dy;

    // Return squared distance
    const distX = px - closestX;
    const distY = py - closestY;
    return distX * distX + distY * distY;
}

/**
 * Calculates the bounding box of a stroke.
 *
 * @param {Object} stroke - Stroke object with points array
 * @returns {{ minX: number, minY: number, maxX: number, maxY: number } | null}
 */
export function getStrokeBoundingBox(stroke) {
    if (!stroke.points || stroke.points.length === 0) {
        return null;
    }

    let minX = Infinity, minY = Infinity;
    let maxX = -Infinity, maxY = -Infinity;

    for (const point of stroke.points) {
        if (point.x < minX) minX = point.x;
        if (point.y < minY) minY = point.y;
        if (point.x > maxX) maxX = point.x;
        if (point.y > maxY) maxY = point.y;
    }

    return { minX, minY, maxX, maxY };
}

/**
 * Checks if a circle (eraser) intersects with a bounding box.
 * Used as a quick pre-filter before detailed hit testing.
 *
 * @param {number} cx - Circle center X
 * @param {number} cy - Circle center Y
 * @param {number} radius - Circle radius
 * @param {{ minX: number, minY: number, maxX: number, maxY: number }} box
 * @returns {boolean}
 */
export function circleIntersectsBox(cx, cy, radius, box) {
    // Find the closest point on the box to the circle center
    const closestX = Math.max(box.minX, Math.min(cx, box.maxX));
    const closestY = Math.max(box.minY, Math.min(cy, box.maxY));

    // Check if that point is within the circle
    const dx = cx - closestX;
    const dy = cy - closestY;
    return (dx * dx + dy * dy) <= (radius * radius);
}

/**
 * Tests if an eraser circle hits a stroke.
 * Uses bounding box pre-filter and segment distance checking.
 *
 * @param {number} eraserX - Eraser center X (canvas coordinates)
 * @param {number} eraserY - Eraser center Y (canvas coordinates)
 * @param {number} eraserRadius - Eraser radius (canvas coordinates)
 * @param {Object} stroke - Stroke object with points array
 * @returns {boolean} True if eraser hits the stroke
 */
export function eraserHitsStroke(eraserX, eraserY, eraserRadius, stroke) {
    if (!stroke.points || stroke.points.length < 2) {
        return false;
    }

    // Get bounding box (with padding for stroke thickness)
    const strokeRadius = (stroke.size || 4) / 2;
    const box = getStrokeBoundingBox(stroke);
    if (!box) return false;

    // Expand box by stroke thickness
    box.minX -= strokeRadius;
    box.minY -= strokeRadius;
    box.maxX += strokeRadius;
    box.maxY += strokeRadius;

    // Quick rejection: bounding box test
    if (!circleIntersectsBox(eraserX, eraserY, eraserRadius, box)) {
        return false;
    }

    // Detailed test: check distance to each segment
    const radiusSquared = eraserRadius * eraserRadius;
    const points = stroke.points;

    for (let i = 0; i < points.length - 1; i++) {
        const p1 = points[i];
        const p2 = points[i + 1];

        const distSquared = pointToSegmentDistanceSquared(
            eraserX, eraserY,
            p1.x, p1.y,
            p2.x, p2.y
        );

        // Account for stroke thickness in hit detection
        const effectiveRadiusSquared = (eraserRadius + strokeRadius) * (eraserRadius + strokeRadius);

        if (distSquared <= effectiveRadiusSquared) {
            return true;  // Hit found, early exit
        }
    }

    return false;
}

/**
 * Finds all strokes that the eraser hits.
 *
 * @param {number} eraserX - Eraser center X (canvas coordinates)
 * @param {number} eraserY - Eraser center Y (canvas coordinates)
 * @param {number} eraserRadius - Eraser radius (canvas coordinates)
 * @param {Array} strokes - Array of stroke objects
 * @returns {Array} Array of stroke IDs that were hit
 */
export function findHitStrokes(eraserX, eraserY, eraserRadius, strokes) {
    const hitIds = [];

    for (const stroke of strokes) {
        if (eraserHitsStroke(eraserX, eraserY, eraserRadius, stroke)) {
            hitIds.push(stroke.id);
        }
    }

    return hitIds;
}

/**
 * Removes strokes by their IDs from an array.
 * Returns a new array without the removed strokes.
 *
 * @param {Array} strokes - Original strokes array
 * @param {Array} idsToRemove - Array of stroke IDs to remove
 * @returns {Array} New array with strokes removed
 */
export function removeStrokesById(strokes, idsToRemove) {
    if (idsToRemove.length === 0) {
        return strokes;
    }

    const idSet = new Set(idsToRemove);
    return strokes.filter(stroke => !idSet.has(stroke.id));
}