"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.splitPathAtIntersection = void 0;
// Helper function to check if a point is inside a polygon
/**
* Determines if a given point is inside a polygon.
*
* This function uses the ray-casting algorithm to determine if the point is inside the polygon.
* It works by drawing a horizontal line from the point to the outside of the polygon and counting
* how many times the line intersects with the edges of the polygon. If the number of intersections
* is odd, the point is inside the polygon. If even, the point is outside.
*
* @param point - The point to check, represented as a tuple [x, y].
* @param polygon - The polygon to check against, represented as an array of paths, where each path is an array of points [x, y].
* The first path in the array is considered the outer boundary of the polygon.
* @returns `true` if the point is inside the polygon, `false` otherwise.
*/
const isPointInsidePolygon = (point, polygon) => {
const [px, py] = point;
const path = polygon[0];
let inside = false;
for (let i = 0, j = path.length - 1; i < path.length; j = i++) {
const [x1, y1] = path[i];
const [x2, y2] = path[j];
const intersect = ((y1 > py) !== (y2 > py)) && (px < (x2 - x1) * (py - y1) / (y2 - y1) + x1);
if (intersect)
inside = !inside;
}
return inside;
};
// Helper function to check if two line segments intersect
/**
* Determines if two line segments intersect and returns the intersection point if they do.
*
* @param p1 - The starting position of the first line segment as a tuple [x, y].
* @param p2 - The ending position of the first line segment as a tuple [x, y].
* @param q1 - The starting position of the second line segment as a tuple [x, y].
* @param q2 - The ending position of the second line segment as a tuple [x, y].
* @returns The intersection point as a tuple [x, y] if the segments intersect within their bounds, otherwise `null`.
*/
const doSegmentsIntersect = (p1, p2, q1, q2) => {
const [x1, y1] = p1;
const [x2, y2] = p2;
const [x3, y3] = q1;
const [x4, y4] = q2;
const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
if (denom === 0)
return null; // No intersection, lines are parallel
const intersectX = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / denom;
const intersectY = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / denom;
// Check if the intersection point is within the bounds of both segments
if ((Math.min(x1, x2) <= intersectX && intersectX <= Math.max(x1, x2)) &&
(Math.min(y1, y2) <= intersectY && intersectY <= Math.max(y1, y2)) &&
(Math.min(x3, x4) <= intersectX && intersectX <= Math.max(x3, x4)) &&
(Math.min(y3, y4) <= intersectY && intersectY <= Math.max(y3, y4))) {
return [intersectX, intersectY];
}
return null; // No intersection within the segment bounds
};
// Function to split paths at the intersection between two polygons
/**
* Splits the path of the first polygon at intersections with the second polygon and merges the resulting paths.
*
* @param polygon1 - The first polygon represented as an array of arrays of positions (coordinates).
* @param polygon2 - The second polygon represented as an array of arrays of positions (coordinates).
* @returns An array containing the merged paths after splitting at intersections.
*
* The function works as follows:
* 1. Initializes an empty array `splitPaths` to store the resulting paths.
* 2. Extracts the first path from each polygon (`path1` and `path2`).
* 3. Iterates through each segment of the first polygon (`path1`).
* 4. For each segment, checks if the start point is inside the second polygon (`polygon2`).
* 5. Checks for intersections between the current segment of the first polygon and all edges of the second polygon.
* 6. If an intersection is found, starts a new path from the intersection point.
* 7. Adds the end point of the current segment to the current path if it is inside the second polygon.
* 8. Ensures no duplicate points are added by checking the last point in the current path.
* 9. Merges the resulting paths and returns the merged path.
*/
const splitPathAtIntersection = (polygon1, polygon2) => {
const splitPaths = [];
const path1 = polygon1[0];
const path2 = polygon2[0];
let currentPath = [];
// Loop through each segment in the first polygon
for (let i = 0; i < path1.length - 1; i++) {
const start1 = path1[i];
const end1 = path1[i + 1];
// Check if the start point is inside the second polygon
if (isPointInsidePolygon(start1, polygon2)) {
currentPath.push(start1); // Add point if inside the second polygon
}
// Check for intersections with all edges of the second polygon
for (let j = 0; j < path2.length - 1; j++) {
const start2 = path2[j];
const end2 = path2[j + 1];
const intersection = doSegmentsIntersect(start1, end1, start2, end2);
if (intersection) {
if (currentPath.length > 0) {
splitPaths.push(currentPath);
}
currentPath = [intersection]; // Start a new path from the intersection
}
}
// Add the last point in the current path
if (isPointInsidePolygon(end1, polygon2)) {
// Check if the last point is equal to the previous point (same coordinates)
if (currentPath.length > 0 && currentPath[currentPath.length - 1][0] === end1[0] && currentPath[currentPath.length - 1][1] === end1[1]) {
// Remove the last index (duplicate point)
currentPath.pop();
// Replace it with a dynamic point from the second polygon (path2)
const uniquePoint = path2.find(p => p[0] !== end1[0] || p[1] !== end1[1]);
if (uniquePoint) {
currentPath.push(uniquePoint); // Add the new unique point from path2
}
}
else {
currentPath.push(end1); // Add the point as usual
}
}
}
if (currentPath.length > 0) {
splitPaths.push(currentPath);
}
const mergedPaths = splitPaths[0]
.slice(0, splitPaths[0].length - 1)
.concat(splitPaths[1]);
return [mergedPaths];
};
exports.splitPathAtIntersection = splitPathAtIntersection;