- 排除路径中连续重复的点
if points[i] == points[i-1] {
// 排除
continue
}
- 将路径中所有点的经纬度都*1000000,转换为整数
经纬度6位小数可以精确到1米,满足需求不需要更高精度
- 从坐标点集中找到边界点,即最小经度、最大经度、最小纬度、最大纬度,构建一个最小的矩形,并将经纬度转化为相对于矩形的坐标
// 从坐标点集中找到边界点
// maxX, minX, maxY, minY 组成一个矩形,可以包含所有的坐标点
var (
maxX = -90000000
minX = 90000000
maxY = -180000000
minY = 180000000
)
for _, p := range pathPoint {
if p.X > maxX {
maxX = p.X
}
if p.X < minX {
minX = p.X
}
if p.Y > maxY {
maxY = p.Y
}
if p.Y < minY {
minY = p.Y
}
}
// 适配maxX, minX, maxY, minY 组成的矩形,使坐标可以包含在一个矩形中
for i := 0; i < len(pathPoint); i++ {
pathPoint[i].X = pathPoint[i].X - minX
pathPoint[i].Y = pathPoint[i].Y - minY
}
- 获取拐点
两点之间的距离采用欧式距离,即两点之间的直线距离
math.Sqrt(math.Pow(float64(p1.X-p2.X), 2) + math.Pow(float64(p1.Y-p2.Y), 2))
判断三点是否直线
var isLine = func(p1, p2, p3 int) bool {
// 临边
d0 := getEuclideanDistance(sp.p[p1], sp.p[p2])
d1 := getEuclideanDistance(sp.p[p2], sp.p[p3])
// 斜边
d2 := getEuclideanDistance(sp.p[p1], sp.p[p3])
// 计算三角形三边的比例
criticalValue := 0.999 // 值越大,越敏感
return d2/(d0+d1) > criticalValue
}
计算拐点
从第二个点开始,依次遍历坐标集
遍历具有两种模式,一种是验证模式,一种是正常模式
验证模式:当遇到拐点时,需要验证多次,验证多次后,才能证明这个点是真的拐点。验证成功后,将回溯至拐点继续正常模式
正常模式:正常判断三点是否直线,如果是直线,则将当前点设置为上一个点,继续遍历
三点:取线段的开始点、上一个点(若当前是验证模式,则取当前线段最后一个点)、当前点,判断是否直线
// 用来找拐点的方法
// p 所有的坐标集合
// needRecallCount 需要验证的次数(需要经历多少个点才能证明这个点是真的拐点)
var recall = func(p []*PathPoint, needRecallCount int) {
var (
recallCount = 0 // 验证次数
lineStart = 0 // 直线的起点index
prevPointIndex = 1 // 上一个点的index(遇到拐角时,这个就等于拐角的index)
)
// 从第三个点开始遍历坐标集合
for i := 2; i < len(p); i++ {
// 判断是否是直线
isline := isLine(lineStart, prevPointIndex, i)
if isline {
prevPointIndex = i // 设置当前index为prevPointIndex
recallCount = 0 // 验证次数清零
} else {
if recallCount >= needRecallCount {
fmt.Println("corner", prevPointIndex)
lineStart = prevPointIndex
corner = append(corner, prevPointIndex)
prevPointIndex, i = prevPointIndex+1, prevPointIndex+1
recallCount = -1
}
recallCount++
}
}
}
for i := 1; i < len(corner); i++ {
// todo 根据经纬度的距离判断
// 若两个拐点之间的个数较小,但距离较大的话,当前判断方式会将其分在一组,存在问题
if corner[i]-corner[i-1] < 4 {
for j := corner[i-1] + 1; j <= corner[i]; j++ {
g = append(g, j)
}
} else {
// todo 根据曲率判断是否真的是拐点 - 防止噪音
if len(g) >= 2 {
// 拐点的个数大于等于2个,才能分组,否则当作噪音去掉
group = append(group, g)
}
g = []int{corner[i]}
}
}
if len(g) >= 2 {
group = append(group, g)
}
- 从拐点分组的结果中找到正确的补给点位置
假设拐点存在且只存在路径的两侧,并且按照规则一边一个依次排列
func (sp *supplyPoint) GetSupplyPoint(cornerGroup [][]int, referenceValue int) [][]int {
// 取单数
var (
cornerGroupNew [][]int
whichSide = 0 // 假设拐点存在且只存在路径的两侧,并且按照规则一边一个依次排列(【cornerGroupIndex%2 == whichSide】)
)
if referenceValue >= 0 {
// 寻找距离最近的点
var (
minDistance = getEuclideanDistance(
&PathPoint{
X: 0,
Y: 0,
},
&PathPoint{
X: sp.maxX - sp.minX,
Y: sp.maxY - sp.minY,
},
)
minDistanceIndex = 0
)
for i := 0; i < len(cornerGroup); i++ {
d := getEuclideanDistance(sp.p[cornerGroup[i][0]], sp.p[referenceValue])
if d < minDistance {
minDistance = d
minDistanceIndex = i
}
}
whichSide = minDistanceIndex % 2
}
// todo 判断是否是按照规则一边一个依次排列,将异常的cornerGroup去掉
for i := 0; i < len(cornerGroup); i++ {
if i%2 == whichSide {
cornerGroupNew = append(cornerGroupNew, cornerGroup[i])
}
}
return cornerGroupNew
}