qzhou711/UAV-Coverage-Planner

# 无人机覆盖路径规划器 🤖 **无人机覆盖路径规划器** - 使用Boustrophedon分解法进行自主无人机路径规划 ## 📋 概述 本项目实现了**Boustrophedon分解算法**，用于为无人机（UAV）生成高效的覆盖路径。该算法广泛应用于农业喷洒、航空测绘、监控以及搜索与救援作业。 ### 什么是Boustrophedon分解？ Boustrophedon（希腊语：“牛转”）分解将一个多边形区域划分为多个单元格，并生成平行扫掠线，以最小化行驶距离覆盖整个区域。该术语源于牛耕作的方式——沿平行线移动，然后在末端转向以覆盖下一垄地。 ### 主要特性 ## 🚀 快速开始 ### 安装 ``` # 克隆存储库 git clone https://github.com/qzhou711/UAV-Coverage-Planner.git cd UAV-Coverage-Planner # 安装依赖项 pip install numpy shapely matplotlib ``` ### 基本用法 ``` from area_coverage import AreaPolygon, plot_coordinates, plot_boundary, plot_path import matplotlib.pyplot as plt # 定义多边形边界（五边形示例） exterior = [(0, 0), (4, 4), (0, 8), (-4, 4), (-9, 3)] # 为覆盖规划创建区域多边形 polygon = AreaPolygon( coordinates=exterior, initial_pos=(-5, 10), # Starting UAV position ft=0.5, # Path spacing (swath width) angle=30 # Path angle in degrees (None = auto-compute) ) # 生成覆盖路径 path = polygon.generate_coverage_path(origin=(0.0, 0.0)) # 可视化 fig, ax = plt.subplots() plt.plot(*polygon.rP.exterior.xy, 'b-', label='Coverage Area') plot_path(ax, path, color='red') plt.plot(*polygon.P.exterior.xy, 'g--', label='Original') plt.legend() plt.gca().set_aspect('equal') plt.show() ``` ### 命令行 ``` # 运行示例脚本 python area_coverage.py ``` ## 📁 项目结构 ``` UAV-Coverage-Planner/ ├── area_coverage.py # Main implementation ├── README.md # This file └── LICENSE # License file ``` ## 🔧 API 参考 ### AreaPolygon 类 ``` AreaPolygon( coordinates: List[Tuple[float, float]], # Outer boundary vertices initial_pos: Tuple[float, float], # Starting position interior: List[List[Tuple[float, float]]] = None, # Holes ft: float = 1.0, # Path spacing angle: Optional[float] = None # Path angle (None = auto) ) ``` #### 方法 - `generate_coverage_path(origin=None)` - 生成完整的覆盖路径 #### 属性 - `rtf.angle` - 计算得出的旋转角度（度） - `P` - 原始多边形（Shapely） - `rP` - 旋转后的多边形（Shapely） ### 可视化函数 ``` plot_coordinates(ax, geometry) # Plot point markers plot_boundary(ax, geometry) # Plot boundary points plot_path(ax, geometry, color='red', linewidth=3) # Plot path line ``` ## 📊 算法详情 ### 工作原理 1. **多边形输入**：将覆盖区域定义为一个多边形（可包含孔洞） 2. **角度优化**：根据最长边计算最佳扫掠方向 3. **旋转**：旋转多边形以对齐扫掠方向 4. **扫掠生成**：在多边形内按指定间距创建平行线 5. **路径排序**：使用最近邻算法对扫掠线进行排序以最小化行程 6. **坐标变换**：将路径旋转回原始坐标系 ### 参数 | 参数 | 类型 | 默认值 | 描述 | |------|------|--------|------| | `coordinates` | List[Tuple] | 必需 | 多边形顶点（逆时针顺序） | | `initial_pos` | Tuple | 必需 | 无人机起始位置 | | `interior` | List[List] | None | 孔洞多边形列表 | | `ft` | float | 1.0 | 路径间距（条带宽度） | | `angle` | float/None | None | 固定角度，或自动计算 | ### 输出 `generate_coverage_path()` 方法返回一个 **Shapely LineString**，其中包含作为航点序列的完整覆盖路径。 ``` # 访问路径点 path = polygon.generate_coverage_path() for i, (x, y) in enumerate(path.coords): print(f"Waypoint {i}: ({x:.2f}, {y:.2f})") # 路径长度 path_length = path.length print(f"Total path length: {path_length:.2f} meters") ``` ## 🧪 示例 ### 示例 1：简单多边形 ``` # 简单矩形区域 exterior = [(0, 0), (10, 0), (10, 5), (0, 5)] polygon = AreaPolygon(exterior, (-1, 2), ft=1.0) path = polygon.generate_coverage_path() ``` ### 示例 2：带孔洞的多边形 ``` # 带孔洞的多边形（中间障碍物） exterior = [(0, 0), (10, 0), (10, 10), (0, 10)] hole = [(4, 4), (6, 4), (6, 6), (4, 6)] # Square hole polygon = AreaPolygon( exterior, (-1, 5), interior=[hole], ft=0.5 ) path = polygon.generate_coverage_path() ``` ### 示例 3：自动角度计算 ``` # 让算法根据最长边计算最佳角度 polygon = AreaPolygon( exterior, initial_pos, ft=1.0, angle=None # Auto-compute ) print(f"Optimal angle: {polygon.rtf.angle:.1f}°") ``` ## 📈 性能 该算法的时间复杂度为 O(n log n)，其中 n 是多边形顶点的数量，主要源于路径排序中的排序操作。 ## 📧 联系方式 如有问题或建议，请在 GitHub 上提交 issue。 ## 📚 参考文献 1. Choset, H. (2001). Coverage of Known Spaces: The Boustrophedon Cellular Decomposition. Springer. 2. Acar, E.U., Choset, H., Rizzi, A.A., Atkar, P.N., and Hull, D. (2002). Exact cellular decompositions in terms of critical points of Morse functions. IEEE International Conference on Robotics and Automation. **注意**：本实现专为二维路径规划设计。对于三维应用（例如地形跟随），需要进行额外处理。

标签：Boustrophedon算法, Mutation, Python, 任务规划, 农业喷洒, 区域覆盖, 可视化, 图形处理, 搜索救援, 无人机, 无后门, 机器人控制, 监视, 算法实现, 网络调试, 自动化, 航空器, 航空测量, 覆盖路径, 计算几何, 路径规划, 逆向工具, 高效路径