supply_point

README

• 路径预处理

1. 排除路径中连续重复的点

if points[i] == points[i-1] { 
	// 排除
	continue
}

1. 将路径中所有点的经纬度都*1000000，转换为整数
   经纬度6位小数可以精确到1米，满足需求不需要更高精度
2. 从坐标点集中找到边界点，即最小经度、最大经度、最小纬度、最大纬度，构建一个最小的矩形,并将经纬度转化为相对于矩形的坐标

// 从坐标点集中找到边界点
	// 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
}

Documentation

Index

• func NewSupplyPoint(csv []byte) *supplyPoint
• type PathPoint
• type Putpixel

Functions

func NewSupplyPoint

func NewSupplyPoint(csv []byte) *supplyPoint

Types

type PathPoint

type PathPoint struct {
	X, Y     int
	Lat, Lng float64
}

type Putpixel

type Putpixel func(x, y int)