Eraser Tool

// Utility functions for geometric intersection detection
 
type Point = [number, number];
type Rectangle = { x: number; y: number; width: number; height: number };
 
// Check if two line segments intersect
function lineSegmentsIntersect(p1: Point, p2: Point, p3: Point, p4: Point): boolean {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  const [x3, y3] = p3;
  const [x4, y4] = p4;
 
  const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
  if (Math.abs(denom) < 1e-10) {
    return false; // Lines are parallel
  }
 
  const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
  const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom;
 
  return t >= 0 && t <= 1 && u >= 0 && u <= 1;
}
 
// Check if a point is inside a rectangle
function pointInRectangle(point: Point, rect: Rectangle): boolean {
  const [x, y] = point;
  return x >= rect.x && x <= rect.x + rect.width && y >= rect.y && y <= rect.y + rect.height;
}
 
// Get the four edges of a rectangle as line segments
function getRectangleEdges(rect: Rectangle): [Point, Point][] {
  const { x, y, width, height } = rect;
  return [
    [[x, y], [x + width, y]], // top edge
    [[x + width, y], [x + width, y + height]], // right edge
    [[x + width, y + height], [x, y + height]], // bottom edge
    [[x, y + height], [x, y]], // left edge
  ];
}
 
// Check if a polyline (series of connected line segments) intersects with a rectangle
export function polylineIntersectsRectangle(points: Point[], rect: Rectangle): boolean {
  if (points.length < 2) {
    return false;
  }
 
  // Early return if any point is inside the rectangle
  for (const point of points) {
    if (pointInRectangle(point, rect)) {
      return true;
    }
  }
 
  // Check if any line segment intersects with rectangle edges
  const rectEdges = getRectangleEdges(rect);
 
  for (let i = 0; i < points.length - 1; i++) {
    const lineStart = points[i];
    const lineEnd = points[i + 1];
 
    for (const [edgeStart, edgeEnd] of rectEdges) {
      if (lineSegmentsIntersect(lineStart, lineEnd, edgeStart, edgeEnd)) {
        return true;
      }
    }
  }
 
  return false;
}
 
// Calculate distance between two points
function distanceBetweenPoints(p1: Point, p2: Point): number {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  return Math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2);
}
 
// Calculate the closest point on a line segment to a given point
function closestPointOnSegment(point: Point, segmentStart: Point, segmentEnd: Point): Point {
  const [px, py] = point;
  const [x1, y1] = segmentStart;
  const [x2, y2] = segmentEnd;
 
  const dx = x2 - x1;
  const dy = y2 - y1;
  const lengthSquared = dx * dx + dy * dy;
 
  if (lengthSquared === 0) {
    return segmentStart; // Segment is a point
  }
 
  const t = Math.max(0, Math.min(1, ((px - x1) * dx + (py - y1) * dy) / lengthSquared));
  return [x1 + t * dx, y1 + t * dy];
}
 
// Check if two paths intersect using a more efficient approach
export function pathsIntersect(path1: Point[], path2: Point[], threshold = 1): boolean {
  if (path1.length < 2 || path2.length < 2) {
    return false;
  }
 
  // First, do the more precise line segment intersection check
  for (let i = 0; i < path1.length - 1; i++) {
    for (let j = 0; j < path2.length - 1; j++) {
      if (lineSegmentsIntersect(path1[i], path1[i + 1], path2[j], path2[j + 1])) {
        return true;
      }
    }
  }
 
  // If no exact intersection, check for proximity based on threshold
  if (threshold > 0) {
    for (let i = 0; i < path1.length - 1; i++) {
      const segment1Start = path1[i];
      const segment1End = path1[i + 1];
 
      for (let j = 0; j < path2.length - 1; j++) {
        const segment2Start = path2[j];
        const segment2End = path2[j + 1];
 
        // Check distance between segment endpoints and closest points
        const distances = [
          distanceBetweenPoints(segment1Start, closestPointOnSegment(segment1Start, segment2Start, segment2End)),
          distanceBetweenPoints(segment1End, closestPointOnSegment(segment1End, segment2Start, segment2End)),
          distanceBetweenPoints(segment2Start, closestPointOnSegment(segment2Start, segment1Start, segment1End)),
          distanceBetweenPoints(segment2End, closestPointOnSegment(segment2End, segment1Start, segment1End)),
        ];
 
        if (Math.min(...distances) <= threshold) {
          return true;
        }
      }
    }
  }
 
  return false;
}