SOURCE

/**
 * 点对象
 * @typedef {Object} Point
 * @property {number} x - X坐标
 * @property {number} y - Y坐标
 */

/**
 * 生成航线点
 * @param {Point[]} polygon - 多边形顶点数组，按顺时针或逆时针顺序
 * @param {number} spacing - 航线间隔距离
 * @param {number} [angle=0] - 航线角度（弧度），默认为0（水平航线）
 * @returns {Point[]} 生成的航线点数组
 */
function generateFlightPath(polygon, spacing, angle = 0) {
    console.log('ops',polygon,spacing,angle)
    // 1. 计算多边形的边界框（考虑旋转后的坐标系）
    const bounds = getRotatedBounds(polygon, angle);
    
    // 2. 在旋转后的坐标系中生成扫描线
    const lines = generateScanLines(bounds, spacing);
    
    // 3. 对每条扫描线与多边形求交
    const rotatedPoints = [];
    const cosAngle = Math.cos(-angle);
    const sinAngle = Math.sin(-angle);
    
    lines.forEach(y => {
        const intersections = getPolygonIntersections(polygon, y, angle);
        
        // 对交点按x坐标排序
        intersections.sort((a, b) => a.x - b.x);
        
        // 生成航线点（每隔一个交点取一个点）
        for (let i = 0; i < intersections.length; i += 2) {
            if (i + 1 < intersections.length) {
                const start = intersections[i];
                const end = intersections[i + 1];
                
                // 在起点和终点之间按间距生成点
                const distance = Math.sqrt(Math.pow(end.x - start.x, 2) + Math.pow(end.y - start.y, 2));
                const pointsCount = Math.floor(distance / spacing);
                
                for (let j = 0; j <= pointsCount; j++) {
                    const t = j / pointsCount;
                    const x = start.x + t * (end.x - start.x);
                    const y = start.y + t * (end.y - start.y);
                    rotatedPoints.push({x, y});
                }
            }
        }
    });
    
    // 4. 将点旋转回原始坐标系
    return rotatedPoints.map(p => ({
        x: p.x * cosAngle - p.y * sinAngle,
        y: p.x * sinAngle + p.y * cosAngle
    }));
}

/**
 * 获取多边形在旋转后的边界框
 * @param {Point[]} polygon - 多边形顶点数组
 * @param {number} angle - 旋转角度（弧度）
 * @returns {Object} 边界框 {minX, maxX, minY, maxY}
 */
function getRotatedBounds(polygon, angle) {
    const cosAngle = Math.cos(angle);
    const sinAngle = Math.sin(angle);
    
    let minX = Infinity, maxX = -Infinity, minY = Infinity, maxY = -Infinity;
    
    polygon.forEach(p => {
        // 旋转点
        const x = p.x * cosAngle + p.y * sinAngle;
        const y = -p.x * sinAngle + p.y * cosAngle;
        
        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x);
        minY = Math.min(minY, y);
        maxY = Math.max(maxY, y);
    });
    
    return {minX, maxX, minY, maxY};
}

/**
 * 生成扫描线
 * @param {Object} bounds - 边界框 {minX, maxX, minY, maxY}
 * @param {number} spacing - 线间距
 * @returns {number[]} 扫描线的y坐标数组
 */
function generateScanLines(bounds, spacing) {
    const lines = [];
    // 从minY开始，每隔spacing生成一条线，直到maxY
    for (let y = bounds.minY; y <= bounds.maxY; y += spacing) {
        lines.push(y);
    }
    return lines;
}

/**
 * 获取多边形与水平扫描线的交点
 * @param {Point[]} polygon - 多边形顶点数组
 * @param {number} y - 扫描线y坐标（在旋转后的坐标系中）
 * @param {number} angle - 旋转角度（弧度）
 * @returns {Point[]} 交点数组
 */
function getPolygonIntersections(polygon, y, angle) {
    const intersections = [];
    const cosAngle = Math.cos(angle);
    const sinAngle = Math.sin(angle);
    
    // 将多边形旋转到水平位置
    const rotatedPolygon = polygon.map(p => ({
        x: p.x * cosAngle + p.y * sinAngle,
        y: -p.x * sinAngle + p.y * cosAngle
    }));
    
    // 检查每条边与扫描线的交点
    for (let i = 0; i < rotatedPolygon.length; i++) {
        const p1 = rotatedPolygon[i];
        const p2 = rotatedPolygon[(i + 1) % rotatedPolygon.length];
        
        // 忽略水平边
        if (Math.abs(p1.y - p2.y) < 1e-6) continue;
        
        // 检查边是否跨越扫描线
        if ((p1.y <= y && p2.y > y) || (p2.y <= y && p1.y > y)) {
            // 计算交点
            const t = (y - p1.y) / (p2.y - p1.y);
            const x = p1.x + t * (p2.x - p1.x);
            
            // 旋转交点回原始坐标系
            intersections.push({
                x: x * cosAngle - y * sinAngle,
                y: x * sinAngle + y * cosAngle
            });
        }
    }
    
    return intersections;
}

// 示例用法
const polygon = [
    {x: 0, y: 0},
    {x: 100, y: 0},
    {x: 100, y: 50},
    {x: 50, y: 100},
    {x: 0, y: 50}
];

const spacing = 10;
const angle = Math.PI / 4; // 45度

const flightPath = generateFlightPath(polygon, spacing, angle);
console.log(flightPath);