高德地图开发小记の如何判断点是否在折线上

高德地图开发中的一个问题解决小记

背景

最近使用高德地图 JavaScript API 开发地图应用,提炼了不少心得,故写点博文,做个系列总结一下,希望能帮助到 LBS 开发同胞们。

项目客户端使用高德地图 JavaScript API,主要业务为以区县为基础自由划分区域,并将划分好的区域存入数据库,以作后续操作。

开发之初便遇见一个问题,客户可以在城市区县范围内自由划分自己需要的区域,但是高德地图并未提供自定义区域的实现方法,所以只能借助 API 自造轮子。

经过讨论得出一个实现方法,初始加载城市区县区域后,自定义折线对象,然后在区域内通过鼠标点击画出折线,再将该折线对象和已有区域边界的路径值一起保存进数据库,便能够构成划分后的两个新区域了。

研究出实现方法后,遇见了一个难题,如何判断鼠标点击的点是否在折线上:

  • 画起点和终点时必须在原有区域线上,否则无法形成新的封闭空间。故需要判断鼠标点击的点是否在原有折线上,在就让其成为起点或终点,不在则让其重新点击。
  • 但是用户点击时无法保证完全点击在原有折线上,故需要允许一定的误差,在误差内则判断为点在折线上,误差外让其重新点击。
  • 判断为在误差内后,鼠标点终究不在折线上,此时需要在原折线上生成一个新的点(离该鼠标点最近的点)

初期方案

一开始希望通过判断折线上每两个相邻点与鼠标点三点共线则证明点在折线上,参阅《代码之美》后,发现了两种解决算法:

  • 一种是判断斜率相等,但是由于以下问题被《代码之美》否决,并提出了更加优化的方法。
    • 判断斜率相等存在多种特殊情况,如两点经度相等或者纬度相等时,代码实现过于繁琐。
    • 斜率使用除法计算为浮点数,存在一定误差。
  • 更优化的方法为三点可以组成一个三角形,当三角形面积接近于0时,则判断点在线上。具体细节可以参看《代码之美》第33章。在实际运用中,发现如果只存在三个点时,计算三角形面积毫无疑问是一个优秀的算法。

但是如前文提到的,鼠标点无法精确点击在折线上,故需要允许一定误差,也就是说三角形面积无法等于0,只能遍历折线每两个相邻点,计算鼠标点与两点组成的三角形面积,取出最小的面积,当其小于一个误差值时,点在折线上。

这样就可能会产生缺陷。一个折线对象存在着数以千计的相邻点,当鼠标点与折线上某两个相邻点组成的三角形面积最小时,却无法保证该点一定离这两个相邻点最近。

  • 理想情况下是这样的。

    理想情况示意图

    三角形面积最小,并且鼠标点离该两点组成的线段最近。

  • 而特殊情况下会是这样的.

    特殊情况示意图

    三角形面积同样最小,但鼠标点其实离线段较远。

他山之石

无奈只能另寻解决方法,然后在百度 LBS 开源库中发现几何运算类提供了判断线是否在折线上的方法 isPointOnPolyline(),大喜,赶紧研究一番,应用在项目中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* 判断点是否在矩形内
* @param {Point} point 点对象
* @param {Bounds} bounds 矩形边界对象
* @returns {Boolean} 点在矩形内返回true,否则返回false
*/
function isPointInRect(point, bounds) {
var sw = bounds.getSouthWest(); //西南脚点
var ne = bounds.getNorthEast(); //东北脚点
return (point.lng >= sw.lng && point.lng <= ne.lng && point.lat >= sw.lat && point.lat <= ne.lat);
}

/**
* 判断点是否在折线上
* @param {Point} point 点对象
* @param {Polyline} polyline 折线对象
* @returns {Boolean} 点在折线上返回true,否则返回false
*/
function isPointOnPolyline(point, polyline) {
//首先判断点是否在线的外包矩形内,如果在,则进一步判断,否则返回false
var lineBounds = polyline.getBounds();
if (!this.isPointInRect(point, lineBounds)) {
return false;
}
//判断点是否在线段上,设点为Q,线段为P1P2 ,
//判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0,且 Q 在以 P1,P2为对角顶点的矩形内
var pts = polyline.getPath();
for (var i = 0; i < pts.length - 1; i++) {
var curPt = pts[i];
var nextPt = pts[i + 1];
// 首先判断point是否在curPt和nextPt之间,即:此判断该点是否在该线段的外包矩形内,先判断离point最近的两个相邻点,再进行斜率计算,有效避免干扰
if (point.lng >= Math.min(curPt.lng, nextPt.lng) && point.lng <= Math.max(curPt.lng, nextPt.lng) &&
point.lat >= Math.min(curPt.lat, nextPt.lat) && point.lat <= Math.max(curPt.lat, nextPt.lat)) {
//判断点是否在直线上公式,此处使用减法计算两个斜率之差,有效地简化了特殊情况的判断
var precision = (curPt.lng - point.lng) * (nextPt.lat - point.lat) -
(nextPt.lng - point.lng) * (curPt.lat - point.lat);
if (precision < 2e-10 && precision > -2e-10) {//实质判断是否接近0
return true;
}
}
}
return false;
}

测一测项目,哈哈,可行,长舒一口气。正准备好好放松下,OMG!又遇见缺陷了。

  • 如下图北京西城区存在的一个情况:

    北京西城区缺陷演示

    此时折线上相邻两点的经度几乎相等。

  • 或者北京丰台区存在的情况:

    北京丰台区缺陷演示

    此时折线上相邻两点的纬度几乎相等。

由于方法优先判断鼠标点是否在折线某相邻两点的外包矩形内,但是上述两种情况下,相邻两点的外包矩形几乎为0,则鼠标点只有在精确点击到折线的情况下才会判断为true。这与实际开发中要求允许一定误差是相悖的,无奈只能另寻解决方法。

最终解决

皇天不负有心人,在两次推翻实现算法后,终于又找到一种解决方法。遍历折线对象取出所有相邻点,计算鼠标点到每两个相邻点组成的线段的最短距离,然后排序最短距离,取出其中最小的距离,如果小于误差范围,则判断点在折线上。如果需要闭合区间,则在折线上生成一个离鼠标点最近的折线点(一般取垂足经纬度)。实现代码如下(代码已分享至 github):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

/**
* 两点之间的距离
* @param x1 第一个点的经度
* @param y1 第一个点的纬度
* @param x2 第二个点的经度
* @param y2 第二个点的纬度
* @returns distance 两点之间的距离
*/
export function getPoToPoDis(x1, y1, x2, y2) {
return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
}

/**
* 点到折线上相邻两点组成的线段的最短距离
* @param point 点坐标
* @param curPt 折线点坐标
* @param nextPt 与 curPt 相邻的折线点坐标
* @returns distance 距离
*/
export function getPoToLineDis(point, curPt, nextPt) {
const { lng: xCur, lat: yCur } = curPt // 折线点经纬度,将此点记作 P1
const { lng: xNext, lat: yNext } = nextPt // 相邻折线点经纬度,将此点记作 P2
const { lng: xPoint, lat: yPoint } = point // 外点经纬度,将此点记作 P

const lengthCurToNext = getPoToPoDis(xCur, yCur, xNext, yNext); // P1 到 P2 的长度,记作 a 线段
const lengthCurToPo = getPoToPoDis(xCur, yCur, xPoint, yPoint); // P1 到 P 的长度,记作 b 线段
const lengthNextToPo = getPoToPoDis(xNext, yNext, xPoint, yPoint); // P2 到 P 的长度,记作 c 线段

let distance = 0
if (lengthNextToPo + lengthCurToPo === lengthCurToNext) {
// 当 b + c = a 时,P 在 P1 和 P2 组成的线段上
distance = 0
} else if (lengthNextToPo * lengthNextToPo >=
lengthCurToNext * lengthCurToNext + lengthCurToPo * lengthCurToPo) {
// 当 c * c >= a * a + b * b 时组成直角三角形或钝角三角形,投影在 P1 延长线上
distance = lengthCurToPo
} else if (lengthCurToPo * lengthCurToPo >=
lengthCurToNext * lengthCurToNext + lengthNextToPo * lengthNextToPo) {
// 当 b * b > c * c + a * a 时组成直角三角形或钝角三角形,投影在 p2 延长线上
distance = lengthNextToPo
} else {
// 其他情况组成锐角三角形,则求三角形的高
const p = (lengthCurToPo + lengthNextToPo + lengthCurToNext) / 2 // 半周长
const s = Math.sqrt(p * (p - lengthCurToNext) *
(p - lengthCurToPo) * (p - lengthNextToPo)) // 海伦公式求面积
distance = 2 * s / lengthCurToNext // 点到线的距离(利用三角形面积公式求高)
}

return distance
}

/**
* 判断点是否在矩形内
* @param point 点对象
* @param bounds 矩形边界对象
* @returns 点在矩形内返回 true,否则返回 false
*/
export function isPointInRect(point, bounds) {
const sw = bounds.getSouthWest() // 西南脚点
const ne = bounds.getNorthEast() // 东北脚点

return (point.lng >= sw.lng && point.lng <= ne.lng && point.lat >= sw.lat && point.lat <= ne.lat)
}

/**
* 得到离鼠标点最近的折线点坐标
* @param point 鼠标点
* @param curPt,nextPt 折线上相邻两点
* @param precision 误差,默认 2e-4
* @returns { polyLng, polyLat } 折线点经纬度
*/
export function genPointOnPolyline(point, curPt, nextPt, precision = 2e-4) {
let pointLng, pointLat
const precisionLng = curPt.lng - nextPt.lng
const precisionLat = curPt.lat - nextPt.lat

if (precisionLng < precision && precisionLng > -precision) {
// 当折线上两点经度几乎相同时(存在一定误差)
pointLng = curPt.lng
pointLat = point.lat
// 创建生成点对象
return { pointLng, pointLat }
} else if (precisionLat < 2e-6 && precisionLat > -2e-6) {
// 当折线上两点纬度相同时(存在一定误差)
pointLat = curPt.lat
pointLng = point.lng
return { pointLng, pointLat }
}

// 其他情况,求得点到折线的垂足坐标
const k = (nextPt.lat - curPt.lat) / (nextPt.lng - curPt.lng)
// 求得该点到线段的垂足坐标
// 设线段的两端点为 pt1 和 pt2,斜率为:k = (pt2.y - pt1.y) / (pt2.x - pt1.x);
// 该直线方程为:y = k * (x - pt1.x) + pt1.y。其垂线的斜率为 - 1 / k,
// 垂线方程为:y = (-1 / k) * (x - point.x) + point.y
const pointLng2 = (k * k * curPt.lng + k * (point.lat - curPt.lat) + point.lng) / (k * k + 1)
const pointLat2 = k * (pointLng2 - curPt.lng) + curPt.lat
return { pointLng2, pointLat2 }
}

/**
* 判断点在一定误差范围内是否在折线上
* @param point 鼠标点
* @param polygon 区域多边形对象
* @param precision 误差范围, 默认 2e-4
* @returns 如果判断点不在折线上则返回false,否则返回true
*/
export function isPointOnPloyline(point, polygon, precision = 2e-4) {
// 首先判断点是否在线的外包矩形内,如果在,则进一步判断,否则返回false
if (!isPointInRect(point, polygon.getBounds())) {
return false
}

const distances = [] // 点到折线每相邻两点的最短距离
const pts = polygon.getPath() // 折线路径点数组
pts.forEach((p, i) => {
distances.push(getPoToLineDis(point, pts[i], pts[i + 1]))
distances.sort()
})

const minDistance = distances[0]
if (minDistance < precision && minDistance > -precision) {
// 当最短距离小于误差值时,判断鼠标点在折线上
return true
}

return false
}

/**
* 如果点到折线最短距离在误差范围内,则得到离该点最近的折线点坐标,否则返回鼠标点坐标
* @param point 鼠标点
* @param polygon 区域多边形对象
* @param precision 误差,默认 2e-4
* @returns 如果判断点不在折线上则返回该点(point),如果判断点在折线上则返回计算出的折线最近点(
* 因为鼠标点选很难精确点在折线上,要允许一定误差,故需得到一个折线上的最近点)
*/
export function genMinDisPoint(point, polygon, precision) {
if (!isPointInRect(point, polygon.getBounds())) {
return false
}

let curPt, nextPt
const distances = [] // 点到折线每相邻两点的最短距离
const points = [] // 折线相邻点
const pts = polygon.getPath() // 折线路径点数组
pts.forEach((p, i) => {
curPt = pts[i]
nextPt = pts[i + 1]
const distance = getPoToLineDis(point, curPt, nextPt)
// 先将存储最短距离的数组排序,如果该两个相邻点与鼠标点计算出的最短距离与数组中最小距离相等,则存储该两点
distances.push(distance)
distances.sort()
if (distance === distances[0]) {
points.concat([curPt, nextPt])
}
})

// 取得 points 最后两项,即最短距离最小时鼠标点两侧的折线点
curPt = points[points.length - 2]
nextPt = points[points.length - 1]
const minDistance = distances[0]
if (minDistance < precision && minDistance > -precision) {
// 当最短距离小于误差值时,判断鼠标点在折线上,通过鼠标点和两侧相邻点,得到折线上的最近点
return genPointOnPolyline(point, curPt, nextPt)
}

return point
}

测试一番,终于解决了缺陷,能够正常判断点是否在折线上,并生成构建自定义区域及一个闭合区域所需要的最近折线点。

总结

可以发现随着缺陷的不断解决,代码量却越来越多。毫无疑问,保持代码整洁,简化实现逻辑是一名开发人员应有的意识。不过在过度简化实现逻辑的过程中,我们是否会忽略许多用户实际使用时将会遭遇的错误呢。

回顾该功能跌宕的开发流程,就会发现:

  • 如果折线不是一个闭合空间,而仅仅是较少点组成的几段线段时,三角形面积的算法遇见的缺陷没有出现的机会,将是最适合的算法。
  • 如果折线点较多,但是其中不存在经度或纬度几乎相等的相邻点时,百度提供的算法又将是最适合的算法。
  • 如果折线点较多,且情况复杂时,采用最后“较重”的算法,才能避免缺陷,成为一枚正常运转的齿轮。

所以“因地制宜”是一种非常重要的思想,不同的数据结构有不同的优劣势,同样不能因为怕某种框架太“轻”,覆盖面窄就避免使用,也不能因为框架太“重”就回避它。整日争辩哪种技术最好是没有意义的,我们需要做的是了解一种技术的最适使用场景,遇见该场景时使用它,享受技术开发者奉献给使用者的那份便捷。

坚持原创技术分享,您的支持将鼓励我继续创作!