如何判断一个指定的位置点坐标(GPS上的经纬度)是否落在一个多边形区域内? |
您所在的位置:网站首页 › 怎样判断经纬网上的位置 › 如何判断一个指定的位置点坐标(GPS上的经纬度)是否落在一个多边形区域内? |
业务场景举例:快递选择收获区域、车辆电子围栏、运动轨迹路线、地理位置信息检测范围和地图等过滤等等。 比方说地图上有一块区域(抽象成多边形),然后里面每一个位置点(像素点)都有对应的GPS的经纬度坐标值,题目要求的就是判断任意点(用户输入的信息)与多边形的位置关系(是否在里面还是在图形区域外面)。 具体有一个需求为:每一个店维护多个可配送的地址,配送地址为地图中的多边形区域,用户选择收货地址的时候需要判断该收货地址在不在多边形区域内。(给定一个点的坐标以及一个多边形的所有顶点坐标。要求能够判断这个点是在多边形内,还是在多边形外? ) 验证地址:Map Polygon/Polyline Tool https://www.keene.edu/campus/maps/tool/ 以上的ABCDE,分别是以下数组里面的数据 [java] view plain copy Point[] ps = new Point[] { new Point(120.2043 , 30.2795), new Point(120.2030 , 30.2511), new Point(120.1810 , 30.2543), new Point(120.1798 , 30.2781), new Point(120.1926,30.2752) };那么问题来了:如何判断一个指定的经纬度点是否落在一个多边形区域内? 这个是算法和判断的依据也是解答本题的关键。(保证准确率和速度的关键) 网络上有很多算法和第三库来实现这类功能,但本文着重讲原理和自己实现写程序。 话不多说,直接抛出写程序通常用的流程模型图,如下; 经过在网上的一番搜索, 发现目前比较通用的就是射线法和坐标轴法,而我采用的就是X轴射线法。 主要理论来源于西安交大的一篇论文(即参考文献的第二条) 判断一个点向左的射线跟一个多边形的交叉点有几个,如果结果为奇数的话那么说明这个点落在多边形中,反之则不在。 1、理论支持:如果从需要判断的点出发的一条射线与该多边形的焦点个数为奇数,则该点在此多边形内,否则该点在此多边形外。(射线不能与多边形顶点相交)2、编程思路:该程序的思路是从A点出发向左做一条水平射线(平行于x轴,向X轴的反方向),判断与各边是否有焦点。dLon1, dLon2, dLat1, dLat2分别表示边的起点和终点的经度和纬度(x轴和y轴)。先判断A点是否在边的两端点d1和d2的水平平行线之间,不在则不可能有交点,继续判断下一条边。在之间则说明可能与A点向左的射线有交点,接下来利用几何方法得到A点的水平直线与该边交点的x坐标。然后判断交点的x坐标在A点的左侧还是右侧,左侧则总交点数加一,右侧则不在A点左射线上,继续判断下一条边。 代码讲解: 主要的类有两个↓↓一个是坐标点的抽象类(点的坐标位置),另一个是位置关系判断工具类(判断点和多边形的关系)。 因为坐标描点要涉及到坐标以及小数点的经纬关系,故要用到浮点型运算,也就是要使用到double双精度。而地图涉及到很多个像素点构成的图形区域,故要用到list数组。结果要展示需要用到js代码。 def IsPtInPoly(aLon, aLat, pointList): ''''' :param aLon: double 经度 :param aLat: double 纬度 :param pointList: list [(lon, lat)...] 多边形点的顺序需根据顺时针或逆时针,不能乱 ''' iSum = 0 iCount = len(pointList) if(iCount < 3): return False for i in range(iCount): pLon1 = pointList[i][0] pLat1 = pointList[i][1] if(i == iCount - 1): pLon2 = pointList[0][0] pLat2 = pointList[0][1] else: pLon2 = pointList[i + 1][0] pLat2 = pointList[i + 1][1] if ((aLat >= pLat1) and (aLat < pLat2)) or ((aLat>=pLat2) and (aLat < pLat1)): if (abs(pLat1 - pLat2) > 0): pLon = pLon1 - ((pLon1 - pLon2) * (pLat1 - aLat)) / (pLat1 - pLat2); if(pLon < aLon): iSum += 1 if(iSum % 2 != 0): return True else: return False 1、是坐标点的抽象类 Java代码 package com.niux.crm.core.common.bmap; /** * 用于构造百度地图中的经纬度点 * * @author zhengtian * @date 2013-8-5 下午02:54:41 */ public class BmapPoint { private double lng;// 经度 private double lat;// 纬度 public BmapPoint() { } public BmapPoint(double lng, double lat) { this.lng = lng; this.lat = lat; } @Override public boolean equals(Object obj) { if (obj instanceof BmapPoint) { BmapPoint bmapPoint = (BmapPoint) obj; return (bmapPoint.getLng() == lng && bmapPoint.getLat() == lat) ? true : false; } else { return false; } } public double getLng() { return lng; } public void setLng(double lng) { this.lng = lng; } public double getLat() { return lat; } public void setLat(double lat) { this.lat = lat; } } 2、位置关系判断工具类 点与多边形的位置关系的判定规则:1、,根据多边形的坐标,虚拟出一个外包矩形,主要是为了提前过滤不相关的点,减少运算量。2、然后判断是否有重合的点。3、判断点与斜线的交点。4、判断点过顶点的情况。5、判断点与边重合的情况。6、判断点在边上的情况。 其中点过顶点,以及点与边重合的情况,主要采用了加权边的思想,论文与代码中有注释。 Java代码 package com.niux.crm.core.common.bmap; import java.util.Arrays; /** * 用于点与多边形位置关系的判断 * * @author zhengtian * @date 2013-8-5 上午11:59:35 */ public class GraphUtils { /** * 判断点是否在多边形内(基本思路是用交点法) * * @param point * @param boundaryPoints * @return */ public static boolean isPointInPolygon(BmapPoint point, BmapPoint[] boundaryPoints) { // 防止第一个点与最后一个点相同 if (boundaryPoints != null && boundaryPoints.length > 0 && boundaryPoints[boundaryPoints.length - 1].equals(boundaryPoints[0])) { boundaryPoints = Arrays.copyOf(boundaryPoints, boundaryPoints.length - 1); } int pointCount = boundaryPoints.length; // 首先判断点是否在多边形的外包矩形内,如果在,则进一步判断,否则返回false if (!isPointInRectangle(point, boundaryPoints)) { return false; } // 如果点与多边形的其中一个顶点重合,那么直接返回true for (int i = 0; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |