本文共 8178 字，大约阅读时间需要 27 分钟。
业务场景举例：快递选择收获区域、车辆电子围栏、运动轨迹路线、地理位置信息检测范围和地图等过滤等等。
比方说地图上有一块区域(抽象成多边形)，然后里面每一个位置点(像素点)都有对应的GPS的经纬度坐标值，题目要求的就是判断任意点(用户输入的信息)与多边形的位置关系(是否在里面还是在图形区域外面)。
具体有一个需求为：每一个店维护多个可配送的地址，配送地址为地图中的多边形区域，用户选择收货地址的时候需要判断该收货地址在不在多边形区域内。(给定一个点的坐标以及一个多边形的所有顶点坐标。要求能够判断这个点是在多边形内，还是在多边形外？)
验证地址：Map Polygon/Polyline Tool https://www.keene.edu/campus/maps/tool/
以上的ABCDE,分别是以下数组里面的数据
[java] view plain
copy
Point[] ps =newPoint[] {newPoint(120.2043,30.2795),newPoint(120.2030,30.2511),newPoint(120.1810,30.2543),newPoint(120.1798,30.2781),newPoint(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
if (point.equals(boundaryPoints[i])) {
return true;
}
}
/**
* 基本思想是利用X轴射线法，计算射线与多边形各边的交点，如果是偶数，则点在多边形外，否则在多边形内。还会考虑一些特殊情况，如点在多边形顶点上
* ， 点在多边形边上等特殊情况。
*/
// X轴射线与多边形的交点数
int intersectPointCount = 0;
// X轴射线与多边形的交点权值
float intersectPointWeights = 0;
// 浮点类型计算时候与0比较时候的容差
double precision = 2e-10;
// 边P1P2的两个端点
BmapPoint point1 = boundaryPoints[0], point2;
// 循环判断所有的边
for (int i = 1; i <= pointCount; i++) {
point2 = boundaryPoints[i % pointCount];
/**
* 如果点的y坐标在边P1P2的y坐标开区间范围之外，那么不相交。
*/
if (point.getLat()
|| point.getLat() > Math.max(point1.getLat(), point2.getLat())) {
point1 = point2;
continue;
}
/**
* 此处判断射线与边相交
*/
if (point.getLat() > Math.min(point1.getLat(), point2.getLat())
&& point.getLat() // 如果点的y坐标在边P1P2的y坐标开区间内
if (point1.getLng() == point2.getLng()) {// 若边P1P2是垂直的
if (point.getLng() == point1.getLng()) {
// 若点在垂直的边P1P2上，则点在多边形内
return true;
} else if (point.getLng()
// 若点在在垂直的边P1P2左边，则点与该边必然有交点
++intersectPointCount;
}
} else {// 若边P1P2是斜线
if (point.getLng() <= Math.min(point1.getLng(), point2.getLng())) {// 点point的x坐标在点P1和P2的左侧
++intersectPointCount;
} else if (point.getLng() > Math.min(point1.getLng(), point2.getLng())
&& point.getLng() // 点point的x坐标在点P1和P2的x坐标中间
double slopeDiff = 0.0d;
if (point1.getLat() > point2.getLat()) {
slopeDiff = (point.getLat() - point2.getLat()) / (point.getLng() - point2.getLng())
- (point1.getLat() - point2.getLat()) / (point1.getLng() - point2.getLng());
} else {
slopeDiff = (point.getLat() - point1.getLat()) / (point.getLng() - point1.getLng())
- (point2.getLat() - point1.getLat()) / (point2.getLng() - point1.getLng());
}
if (slopeDiff > 0) {
if (slopeDiff // 由于double精度在计算时会有损失，故匹配一定的容差。经试验，坐标经度可以达到0.0001
// 点在斜线P1P2上
return true;
} else {
// 点与斜线P1P2有交点
intersectPointCount++;
}
}
}
}
} else {
// 边P1P2水平
if (point1.getLat() == point2.getLat()) {
if (point.getLng() <= Math.max(point1.getLng(), point2.getLng())
&& point.getLng() >= Math.min(point1.getLng(), point2.getLng())) {
// 若点在水平的边P1P2上，则点在多边形内
return true;
}
}
/**
* 判断点通过多边形顶点
*/
if (((point.getLat() == point1.getLat() && point.getLng()
|| (point.getLat() == point2.getLat() && point.getLng()
if (point2.getLat()
intersectPointWeights += -0.5;
} else if (point2.getLat() > point1.getLat()) {
intersectPointWeights += 0.5;
}
}
}
point1 = point2;
}
if ((intersectPointCount + Math.abs(intersectPointWeights)) % 2 == 0) {// 偶数在多边形外
return false;
} else { // 奇数在多边形内
return true;
}
}
/**
* 判断点是否在矩形内在矩形边界上，也算在矩形内(根据这些点，构造一个外包矩形)
*
* @param point
* 点对象
* @param boundaryPoints
* 矩形边界点
* @return
*/
public static boolean isPointInRectangle(BmapPoint point, BmapPoint[] boundaryPoints) {
BmapPoint southWestPoint = getSouthWestPoint(boundaryPoints); // 西南角点
BmapPoint northEastPoint = getNorthEastPoint(boundaryPoints); // 东北角点
return (point.getLng() >= southWestPoint.getLng() && point.getLng() <= northEastPoint.getLng()
&& point.getLat() >= southWestPoint.getLat() && point.getLat() <= northEastPoint.getLat());
}
/**
* 根据这组坐标，画一个矩形，然后得到这个矩形西南角的顶点坐标
*
* @param vertexs
* @return
*/
private static BmapPoint getSouthWestPoint(BmapPoint[] vertexs) {
double minLng = vertexs[0].getLng(), minLat = vertexs[0].getLat();
for (BmapPoint bmapPoint : vertexs) {
double lng = bmapPoint.getLng();
double lat = bmapPoint.getLat();
if (lng
minLng = lng;
}
if (lat
minLat = lat;
}
}
return new BmapPoint(minLng, minLat);
}
/**
* 根据这组坐标，画一个矩形，然后得到这个矩形东北角的顶点坐标
*
* @param vertexs
* @return
*/
private static BmapPoint getNorthEastPoint(BmapPoint[] vertexs) {
double maxLng = 0.0d, maxLat = 0.0d;
for (BmapPoint bmapPoint : vertexs) {
double lng = bmapPoint.getLng();
double lat = bmapPoint.getLat();
if (lng > maxLng) {
maxLng = lng;
}
if (lat > maxLat) {
maxLat = lat;
}
}
return new BmapPoint(maxLng, maxLat);
}
}
【关于3D地图图形请参考】
IOS高德3D地图画多边形，以及判断某一经纬度是否在该多边形内 - 简书 https://www.jianshu.com/p/fb1177cac1ec
翻看了一下高德提供的技术文档，没找到3D地图下该怎么完成此功能。无奈自己翻找高德的SDK，发现了这两个类：MAPolygon MAOverlayRenderer
MAPolygon用于定义一个由多个点组成的闭合多边形,点与点之间按顺序尾部相连,第一个点与最后一个点相连,通常MAPolygon是MAPolygonView的model
MAOverlayRenderer是地图覆盖物Renderer的基类,提供绘制overlay的接口但并无实际的实现(render相关方法只能在重写后的glRender方法中使用)
【参考文献】1、两条直线的关系http://www.cnblogs.com/devymex/archive/2010/08/19/1803885.html2、点与多边形的关系
http://wenku.baidu.com/view/5e3913a2b0717fd5360cdccf.html?qq-pf-to=pcqq.c2c
3、https://en.wikipedia.org/wiki/Haversine_formula
4、百度map js代码 https://www.cnblogs.com/relax/p/3507014.html
5、关于经纬度得到的多边形面积。 https://www.cnblogs.com/JeffController/p/5618742.html
【附录坐标轴函数公式图】
直接上代码(两个点)半正矢公式 计算(Haversine formula)：因为难度大暂时不考虑此类算法。
关于指定的经纬度是否落在多边形内 - https://blog.csdn.net/qq_22929803/article/details/46818009