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;
}