/**
|
* 检查两条线段是否相交
|
* @param {Array} a1 线段1起点 [x, y]
|
* @param {Array} a2 线段1终点 [x, y]
|
* @param {Array} b1 线段2起点 [x, y]
|
* @param {Array} b2 线段2终点 [x, y]
|
* @returns {boolean} 是否相交
|
*/
|
function doLinesIntersect(a1, a2, b1, b2) {
|
// 计算向量叉积
|
const ccw = (p1, p2, p3) => (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
|
|
// 检查线段 a1a2 和 b1b2 是否跨立
|
const ccw1 = ccw(a1, a2, b1);
|
const ccw2 = ccw(a1, a2, b2);
|
const ccw3 = ccw(b1, b2, a1);
|
const ccw4 = ccw(b1, b2, a2);
|
|
// 跨立实验 + 共线检查
|
if (
|
(ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0) || // 一般情况：跨立
|
(ccw1 === 0 && isPointOnSegment(a1, a2, b1)) || // 共线情况
|
(ccw2 === 0 && isPointOnSegment(a1, a2, b2)) ||
|
(ccw3 === 0 && isPointOnSegment(b1, b2, a1)) ||
|
(ccw4 === 0 && isPointOnSegment(b1, b2, a2))
|
) {
|
//console.log("doLinesIntersect ccw", ccw1, ccw2, ccw3, ccw4)
|
return true;
|
}
|
return false;
|
}
|
|
/**
|
* 检查点是否在线段上（共线时使用）
|
*/
|
function isPointOnSegment(p1, p2, p) {
|
const minX = Math.min(p1[0], p2[0]);
|
const maxX = Math.max(p1[0], p2[0]);
|
const minY = Math.min(p1[1], p2[1]);
|
const maxY = Math.max(p1[1], p2[1]);
|
return (
|
p[0] >= minX && p[0] <= maxX &&
|
p[1] >= minY && p[1] <= maxY
|
);
|
}
|
|
/**
|
* 检查路径是否自相交
|
* @param {Array} points 路径点数组 [[x1, y1], [x2, y2], ...]
|
* @returns {boolean} 是否自相交
|
*/
|
export function hasSelfIntersection(points) {
|
const len = points.length -1
|
if (len < 3) return false; // 至少 4 个点才可能自相交
|
|
for (let i = 0; i < len; i++) {
|
//console.log("point", i, points[i])
|
for (let j = i + 2; j < len; j++) {
|
// 跳过相邻线段（相邻线段只会在端点相交，不算自相交）
|
//console.log("point2", j, points[j])
|
if (i === (j + 1) % len|| j === (i + 1) % len) continue;
|
|
const a1 = points[i];
|
const a2 = points[i + 1];
|
const b1 = points[j];
|
const b2 = points[j + 1];
|
// console.log("doLinesIntersect", a1, a2, b1, b2)
|
if (doLinesIntersect(a1, a2, b1, b2)) {
|
return true;
|
}
|
}
|
}
|
return false;
|
}
|
