如何用p5.js在多边形屋顶内放置最多非重叠且不碰边界的太阳能板

需求明确 #

你需要在动态多边形屋顶内放置最多固定宽高的矩形太阳能板，要求：

• 太阳能板不能重叠
• 太阳能板不能触碰多边形边界
• 用p5.js完成实现

适合的入门算法：网格填充法 #

作为p5.js新手，网格填充法是最容易上手且效果不错的启发式方案——通过在多边形的有效区域内生成规则网格，逐一验证每个网格位置是否可放置太阳能板，最终得到近似最优的放置数量。如果后续需要更优解，可再尝试回溯法或遗传算法，但网格法足够应对大多数场景。

实现步骤 #

1. 内缩边界处理：确保太阳能板完全处于多边形内部，与边界保持安全距离（避免边缘触碰）。
2. 点/矩形在多边形内的判断：实现射线法判断点是否在多边形内，进而验证太阳能板的四个顶点是否都在内部。
3. 网格遍历与放置：在多边形的轴对齐包围盒内生成网格，逐个尝试放置，跳过已占用位置。

完整p5.js代码示例 #

function setup() {
    createCanvas(800, 500);
    background(220);
    noLoop();
}

// 射线法：判断点是否在多边形内部
function pointInPolygon(point, polygon) {
    let inside = false;
    const x = point.x, y = point.y;
    // 遍历多边形每条边
    for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
        const xi = polygon[i].x, yi = polygon[i].y;
        const xj = polygon[j].x, yj = polygon[j].y;
        
        // 判断点是否在边的垂直范围内，且射线与边相交
        const intersect = ((yi > y) !== (yj > y)) 
            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
        if (intersect) inside = !inside;
    }
    return inside;
}

// 判断矩形是否可放置：完全在多边形内 + 不与已放置板重叠
function canPlacePanel(panelX, panelY, panelW, panelH, polygon, placedPanels) {
    // 矩形四个顶点
    const points = [
        {x: panelX, y: panelY},
        {x: panelX + panelW, y: panelY},
        {x: panelX + panelW, y: panelY + panelH},
        {x: panelX, y: panelY + panelH}
    ];
    
    // 检查所有顶点是否在多边形内部
    for (let p of points) {
        if (!pointInPolygon(p, polygon)) return false;
    }
    
    // 检查是否与已放置板重叠
    for (let panel of placedPanels) {
        if (panelX < panel.x + panel.w && 
            panelX + panelW > panel.x && 
            panelY < panel.y + panel.h && 
            panelY + panelH > panel.y) {
            return false;
        }
    }
    
    return true;
}
  
function draw() {
    // 定义屋顶多边形顶点（转为对象数组方便处理）
    const roofPolygon = [
        {x:50, y:50},
        {x:750, y:50},
        {x:750, y:450},
        {x:500, y:450},
        {x:500, y:200},
        {x:350, y:200},
        {x:350, y:450},
        {x:50, y:450}
    ];
    
    // 绘制屋顶
    fill(237, 34, 93);
    beginShape();
    roofPolygon.forEach(v => vertex(v.x, v.y));
    endShape(CLOSE);

    // 太阳能板参数
    const solarPanel = {
        width: 40,
        height: 40,
        padding: 2 // 安全距离，避免触碰边界
    };
    
    const placedPanels = [];
    const panelW = solarPanel.width;
    const panelH = solarPanel.height;
    const padding = solarPanel.padding;
    
    // 计算多边形的轴对齐包围盒，缩小遍历范围
    let minX = Infinity, maxX = -Infinity;
    let minY = Infinity, maxY = -Infinity;
    roofPolygon.forEach(v => {
        minX = min(minX, v.x);
        maxX = max(maxX, v.x);
        minY = min(minY, v.y);
        maxY = max(maxY, v.y);
    });
    
    // 从内缩后的起始位置遍历网格
    for (let y = minY + padding; y + panelH + padding <= maxY; y += panelH) {
        for (let x = minX + padding; x + panelW + padding <= maxX; x += panelW) {
            if (canPlacePanel(x, y, panelW, panelH, roofPolygon, placedPanels)) {
                // 绘制并记录已放置的太阳能板
                fill(76, 201, 240);
                rect(x, y, panelW, panelH);
                placedPanels.push({x, y, w: panelW, h: panelH});
            }
        }
    }
    
    // 控制台输出可安装数量
    console.log(`可安装太阳能板数量：${placedPanels.length}`);
}

关键细节说明 #

• 射线法函数：pointInPolygon是判断点是否在多边形内的核心算法，适用于任意简单多边形。
• 碰撞检测：canPlacePanel同时验证矩形的合法性（在多边形内）和非重叠性。
• 内缩处理：通过padding参数和缩小遍历范围，严格避免太阳能板触碰屋顶边界。

进阶优化方向 #

如果需要更优的放置数量，可尝试：

• 旋转太阳能板：允许旋转90度，遍历两种方向的网格，选择数量更多的方案。
• 贪心优化：优先填充空间利用率更高的连续区域。
• 遗传算法：模拟进化寻找近似最优解，适合复杂多边形，但实现难度较高。

内容的提问来源于stack exchange，提问作者Jumbo