高德地图API开发二三事(二)如何判断点是否在折线上及引申思考

由于高德地图并未提供点是否在折线上的判断方法,所以只能自造轮子。

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

一种是判断斜率相等,但是由于一下问题被《代码之美》否决,并提出了更加优化的方法。

在实际运用中,发现如果只存在三个点时,计算三角形面积毫无疑问是一个优秀的算法。

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

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

理想情况下是这样的,

三角形面积最小,并且鼠标点离该两点组成的线段最近。而特殊情况下会是这样的,

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

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

/*** 判断点是否在矩形内* @param {Point} point 点对象* @param {Bounds} bounds 矩形边界对象* @returns {Boolean} 点在矩形内返回true,否则返回false*/{(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*/{//首先判断点是否在线的外包矩形内,如果在,则进一步判断,否则返回falsevar lineBounds = polyline.getBounds();if(!this.isPointInRect(point, lineBounds)){return false;}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);;}}}return false;}

测一测项目,哈哈,可行,长舒一口气。正准备好好放松下,OMG!又遇见缺陷了,如下图北京西城区存在的一个情况,

此时折线上相邻两点的经度几乎相等,或者北京丰台区存在的情况,

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

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

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

/*************判断用户鼠标点击的点是否在折线上********************************//***主要实现算法为计算鼠标点到折线上每相邻两点组成的线段的最短距离,如果最小的最短距离小于误差值,*则判断点在折线上。*然后通过该相邻两点取得折线上离鼠标点最近的点。*//** * 计算两点之间的距离 * @param x1 第一个点的经度 * @param y1 第一个点的纬度 * @param x2 第二个点的经度 * @param y1 第二个点的纬度 * @returns lineLength 两点之间的距离 */{var lineLength = 0;lineLength = Math.sqrt((x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2));return lineLength;}/** * 计算鼠标点到折线上相邻两点组成的线段的最短距离 * @param point 鼠标点 * @param curPt 折线点 * @param nextPt 与curPt相邻的折线点 * @returns dis 最短距离 */{yCur = curPt.lat;var xNext = nextPt.lng; //与上一个取点相邻的折线点的经纬度,将该点记作P2var yNext = nextPt.lat;var xPoint = point.lng; //鼠标点的经纬度,将该点记作Pvar yPoint = point.lat;lengthCurToNext = lineDis(xCur, yCur, xNext, yNext); //P1到P2的长度,记作a线段if (lengthNextToPo + lengthCurToPo == lengthCurToNext) {//当b+c=a时,P在P1和P2组成的线段上dis = 0;return dis;} else if (lengthNextToPo * lengthNextToPo >= lengthCurToNext * lengthCurToNext + lengthCurToPo * lengthCurToPo) {//当c*c>=a*a+b*b时组成直角三角形或钝角三角形,投影在P1延长线上 dis = lengthCurToPo;return dis;} else if (lengthCurToPo * lengthCurToPo >= lengthCurToNext * lengthCurToNext + lengthNextToPo * lengthNextToPo) {//当b*b>c*c+a*a时组成直角三角形或钝角三角形,投影在p2延长线上dis = lengthNextToPo;return dis;} else {s = Math.sqrt(p * (p – lengthCurToNext) * (p – lengthCurToPo) * (p – lengthNextToPo)); // 海伦公式求面积 dis = 2 * s / lengthCurToNext; // 返回点到线的距离(利用三角形面积公式求高) return dis;}}/** * 判断点是否在矩形内 * @param point 点对象 * @param bounds 矩形边界对象 * @returns 点在矩形内返回true,否则返回false */{(point.lng >= sw.lng && point.lng <= ne.lng && point.lat >= sw.lat && point.lat <= ne.lat);}/** * 判断点是否在折线上,如果需要在折线上生成最近点,则可注释该方法,使用下一个方法 * @param point 鼠标点 * @param polygon 区域多边形对象 * @returns 如果判断点不在折线上则返回false,否则返回true */{// 首先判断点是否在线的外包矩形内,如果在,则进一步判断,否则返回falsevar lineBounds = polygon.getBounds();if (!isPointInRect(point, lineBounds)) {return false;}pts = polygon.getPath();var curPt = null; //折线的两个相邻点var nextPt = null;for (var i = 0; i < pts.length – 1; i++) {curPt = pts[i];nextPt = pts[i + 1];//计算鼠标点到该两个相邻点组成的线段的最短距离var dis = countDisPoToLine(point, curPt, nextPt);//先将存储最短距离的数组排序disArray.push(dis);disArray.sort();};}return false;}/** * 判断点是否在折线上,如果判断为真则在折线上生成离该点最近的点 * @param point 鼠标点 * @param polygon 区域多边形对象 * @returns 如果判断点不在折线上则返回该点(point),如果判断点在折线上则返回计算出的折线最近点( 因为鼠标点选很难精确点在折线上,要允许一定误差,故需生成一个折线上的最近点), 返回该最近点(pointPoly)。function isPointOnPloylineTest(point, polygon) {// 首先判断点是否在线的外包矩形内,如果在,则进一步判断,否则返回falsevar lineBounds = polygon.getBounds();if (!isPointInRect(point, lineBounds)) {return point;}var disArray = new Array(); //存储最短距离var pointArray = new Array(); //存储折线相邻点var pts = polygon.getPath();var curPt = null; //折线的两个相邻点var nextPt = null;for (var i = 0; i < pts.length – 1; i++) {curPt = pts[i];nextPt = pts[i + 1];//计算鼠标点到该两个相邻点组成的线段的最短距离var dis = countDisPoToLine(point, curPt, nextPt);//先将存储最短距离的数组排序,如果该两个相邻点与鼠标点计算出的最短距离与数组中最小距离相等,则存储该两点disArray.push(dis);disArray.sort();if (dis == disArray[0]) {pointArray.push(curPt);pointArray.push(nextPt);}}curPt = pointArray[pointArray.length – 2]; //取得数组最后两项,即为当最短距离最小时鼠标点两侧的折线点nextPt = pointArray[pointArray.length – 1];var disMin = disArray[0]; //取得数组中最小的最短距离if (disMin < 2e-4 && disMin > -2e-4) { //当最短距离小于误差值时,判断鼠标点在折线上(误差值可根据需要更改)var pointPoly = getPointOnPolyline(point, curPt, nextPt); //通过鼠标点和两侧相邻点,在折线上生成一个距离鼠标点最近的点return pointPoly;}return point;}/** * 如果点离折线上某两点组成的线段最近,则在折线上生成与鼠标点最近的折线点 * @param point 鼠标点 * @param curPt,,nextPt 折线上相邻两点 * @returns pointPoly 生成点function getPointOnPolyline(point, curPt, nextPt) {var pointLng; // 取得点的经度var pointLat; // 取得点的纬度var precisionLng = curPt.lng – nextPt.lng;var precisionLat = curPt.lat – nextPt.lat;if (precisionLng < 2e-6 && precisionLng > -2e-6) {// 当折线上两点经度几乎相同时(存在一定误差)pointLng = curPt.lng;pointLat = point.lat;//创建生成点对象var pointPoly = new AMap.LngLat(curPt.lng, pointLat);} else if (precisionLat < 2e-6 && precisionLat > -2e-6) {//当折线上两点纬度相同时(存在一定误差)pointLat = curPt.lat;pointLng = point.lng;var pointPoly = new AMap.LngLat(pointLng, curPt.lat);} else {//其他情况,求得点到折线的垂足坐标var 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.yvar pointLng_02 = (k * k * curPt.lng + k * (point.lat – curPt.lat) + point.lng) / (k * k + 1);var pointLat_02 = k * (pointLng_02 – curPt.lng) + curPt.lat;var pointPoly = new AMap.LngLat(pointLng_02, pointLat_02);}return pointPoly;}*//****************************************************************************/

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

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

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

代替你主持夕阳的葬礼。

高德地图API开发二三事(二)如何判断点是否在折线上及引申思考

相关文章:

你感兴趣的文章:

标签云: