# 避障路径规划

**Repository Path**: GalaxyPw/Obstacle-avoidance-path-planning

## Basic Information

- **Project Name**: 避障路径规划
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2024-05-14
- **Last Updated**: 2024-07-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README





### 使用方式：

​		使用自己的高德地图的key

​		在这里拾取新坐标，注意顺时针和凸多边形[坐标拾取器 | 高德地图API (amap.com)](https://lbs.amap.com/tools/picker)

​		添加起点终点之后，点击设定完成，再显示最短路径；每次使用完一次之后需要刷新一次浏览器。

### 注意事项：

使用Go和HTTP时候，要去查看http-request

可使用高德地图API：

注意：

​	有些楼块 可以做一些切除操作 切成 凸多边形

​	湖水不属于楼块，这是左边湖轮廓（湖是凹多边形，怎么办）

```
pathLake:[[114.617114,30.457107],
    [114.618012,30.457105],
    [114.618012,30.456917],
    [114.617957,30.456918],
    [114.617551,30.456816],
    [114.617324,30.456721],
    [114.617239,30.456583],
    [114.617086,30.456464],
    [114.616865,30.456439],
    [114.616625,30.456592],
    [114.616587,30.4567],
    [114.616656,30.45688],
    [114.616795,30.45703]]
```

·点标记：

​		设置点拖拽效果，可以返回position，后续可以转为图形坐标方便计算

### 目录描述

-font //前端 可在contralMap.js中添加其他建筑 保证是凸多边形 注意命名规范

-src\

​		--api.go //处理get 和 post 请求

​		--main.go

​		--ready.go //地图信息加载 和 主体逻辑

​		--shortPathAlo\

​				---shortPathTest.go //单元测试，测试最短路径算法 正确性，

​				--shortPath.go //可视图最短路径 D 后续可添加其他最短路径算法

​		--minBox\

​				---celltest.go //单元测试，测试最小包围盒 算法正确性，

​				---geoCalcu.go //最小包围盒使用的数据结构和几何算法

​				--surroundBox.go //最小四边形包围盒算法

-go.mod //添加外部依赖



### 前后端交互

前端需要得到： 画出折线的坐标

后端需要： 地图信息，起点终点坐标


需要获取每个结点的所有坐标（类似于经纬度的信息）可以试着由前端传（还有鼠标两次点击的位置，作为起始点和结束点），然后后端需要给前端传（最短路径 路径上的所有坐标）这是可能的前后端交互方式，可以尝试使用高德地图API，里面有获取坐标的接口，可以尝试获取每个建筑的轮廓座标（大多是多边形顶点，圆）。

### 最短路径需要定义的数据：

class Point{

​	float64 X,Y;

}

class Building{

​	vector < Point >

}

class Map{

​	vector < Building >

}

#### 最短路径计算后的数据：

vector < Point > result





### 一 . 包围盒算法

#### ·定理 7.1 

​	记过角内部一定点的直线与角两边相交成的三角形为 Rx。当过定点的直

线被角两边所截得的线段是以定点为中点时，所围成的三角形记为 R0。R0是 Rx 中面

积最小的三角形

#### ·定理 7.2 

最小四边形包围盒不存在零共点边。

#### ·定理 7.3 

如果最小四边形包围盒有两边平行，则它的另两条边应是多共点边

​	推论 7.1 如果最小四边形包围盒是平行四边形，那么平行四边形的边全部是多共

点边。

​	推论 7.2 最小平行四边形包围盒有相邻的两边是多共点边。

#### ·定理 7.4 

最小四边形包围盒各边中点落在凸多边形边上

包围盒是四边形：

​		情形一：三个多共点边，一个单共点边；

​		情形二：四个都是多共点边；

------------------------------

结论：凸多边形最小四边形包围盒要么四边都是多共点边，要么有三边是多共点

​	边而另一边的中点落在凸多边形的某个顶点上。

## 二 . 最短路径规划

### 1.定义和定理理解

### 2 .G的成本矩阵C的计算

v ：是G中的一个障碍物

p:  v中的点，所以文中有顶点的顶点的说法

k,l：表示不同的两个v的序号

#### 情形一: 

计算两个不同v之间的最短距离 。

##### 	·步骤一：

​		文中描述通俗易懂；

##### 	·步骤二：

​		和步骤一一样，步骤一是pk,i到pl,j之间没有障碍，同时还要验证 pl,j和pk,i。要相互验证

##### 	·步骤三：

​		较复杂，要遍历除了k,l之外的所有v，来验证pl,j和pk,i之间是否存在障碍，若无障碍直接计算直线距离即可；

#### 情形二：

计算一个v中不同顶点，pl,i和pl,j，比较简单，两点若相邻或重合则直接是两点之间边的长度，否则不存在。





### 3.算法原理和分析

#### a.

先找到G‘的成本矩阵Ccost，就是G的成本矩阵取四个元素（就是k,l这两个结点有关的元素）

然后由动态规划原理求G’每对顶点间最短路径