/**
 * 检查两条线段是否相交
 * @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;
}