INFO

👉 演示 Demo

在无人机协同作业场景中，如何将一个大区域合理划分为多个子任务区域是提升作业效率的关键问题。传统的手动划分方式效率低下且难以保证公平性，而简单的几何划分方法在非规则区域上表现不佳。本文介绍一种基于K-means聚类和Voronoi图的智能区域划分算法，实现了无人机任务区域的自动优化分割。

算法核心思想

传统方法的局限性

最初的划分思路采用极坐标划分法：以区域中心为原点，将360度按任务数量 $n$ 等分，然后进行射线划分。这种方法虽然简单，但存在明显缺陷：

1. 对区域形状敏感：仅在对称的凸多边形上效果较好
2. 面积不均问题：中心点到边界距离差异大时，划分结果面积悬殊
3. 适应性差：无法适应复杂形状的区域

新算法的优势

新算法通过五个关键步骤实现智能划分：

随机点生成 → K-means聚类 → 中心点计算 → Voronoi图生成 → 多边形裁剪

这种数据驱动的划分方式能够自动适应区域形状，保证各子区域面积相对均衡。

算法实现细节

步骤一：随机点生成

const randomPointsStep = () => {
    points = turf.randomPoint(1000, { bbox: polygonBbox })
    // 筛选落在多边形内的点
    points.features = points.features.filter((feature) => {
        return turf.booleanPointInPolygon(feature, polygon.toGeoJSON())
    })
}

技术要点：

• 使用Turf.js库生成边界框内的随机点
• 通过点包容性测试确保所有点都在目标多边形内
• 点密度影响划分精度，1000个点在大多数场景下已足够

步骤二：K-means聚类

const clusterStep = () => {
    clustered = turf.clustersKmeans(points, {
        numberOfClusters: numberOfClusters
    })
}

算法原理：

• K-means将点集划分为 $n$ 个簇，使得同一簇内点距离最小化
• 聚类结果自然形成数据密度相似的区域分组
• 簇的数量等于最终要划分的区域数量

步骤三：聚类中心计算

const centroidsStep = () => {
    Object.keys(clusterGroups).forEach((i) => {
        const centroid = turf.centroid({
            type: 'FeatureCollection',
            features: clusterGroups[i]
        })
        centroids.push(centroid)
    })
}

关键作用：

• 每个簇的中心点将作为Voronoi图的生成点
• 中心点的分布反映了原始区域的点密度特征

步骤四：Voronoi图生成

const voronoiStep = () => {
    voronoiPolygons = turf.voronoi(
        {
            type: 'FeatureCollection',
            features: centroids
        },
        { bbox: polygonBbox }
    )
}

数学基础：

• Voronoi图将平面划分为多个区域，每个区域包含距离特定生成点最近的所有点
• 生成点即为上一步得到的聚类中心

步骤五：多边形裁剪

const voronoiClipStep = () => {
    const clipped = voronoiPolygons.features.map((feature) => {
        return turf.intersect(feature.geometry, polygon.toGeoJSON())
    })
}

必要性：

• 原始Voronoi图可能超出目标多边形边界
• 通过几何求交运算，确保最终划分结果完全在目标区域内
• 保留有效的任务子区域，去除无效的外部部分

算法性能分析

时间复杂度分析

1. 随机点生成： $O(m)$ ，其中 $m$ 为生成点数量（固定1000）
2. K-means聚类： $O(m\cdot n\cdot i)$ ，其中 $n$ 为簇数量， $i$ 为迭代次数
3. 中心点计算： $O(m)$
4. Voronoi图生成： $O(n\log n)$
5. 多边形裁剪： $O(n\cdot v)$ ，其中 $v$ 为多边形平均顶点数

总体复杂度：在固定点数量情况下，主要取决于聚类数量 $n$ ，属于可接受范围。

空间复杂度

算法需要存储中间结果，但所有数据结构规模与点数量和多边形复杂度成正比，在典型应用场景下内存消耗可控。

实际性能表现

• 小规模任务（ $n\le 10$ ）：响应时间在毫秒级，用户无感知延迟
• 中等规模（ $10<n\le 50$ ）：划分过程在秒级完成，满足交互需求
• 大规模划分（ $n>50$ ）：需要考虑优化策略，如减少随机点数量

应用价值与改进方向

实际应用优势

1. 自动化程度高：减少人工规划工作量80%以上
2. 划分结果均衡：各子区域面积差异控制在合理范围内
3. 适应性强：适用于各种凸多边形区域
4. 可扩展性好：算法模块化，易于集成到现有系统

局限性及改进空间

1. 非凸多边形支持：当前算法对凹陷区域处理效果有限
2. 动态权重考虑：未考虑区域内的任务密度差异
3. 实时性优化：对于超大规模划分需要进一步优化

演示

TIP

左键添加点，右键结束多边形绘制

聚类数量:

随机点数:

已添加 0 个点