已被阅读 2870 次 | 文章分类:gis随笔 | 2022-05-21 00:42
射线法一般情况思路: 从目标点出发朝x轴正方向引一条射线,计算这条射线和多边形所有边的交点数目。如果交点个数为奇数,则目标点在多边形内部;如果交点个数为偶数,则目标点在多边形外部
1 射线法原理
射线法一般情况思路:
从目标点出发朝x轴正方向引一条射线,计算这条射线和多边形所有边的交点数目。
如果交点个数为奇数,则目标点在多边形内部;
如果交点个数为偶数,则目标点在多边形外部
演示如下:
2 算法解释
全部的代码如下
function isPointInPolygon(pt, pts) {
// 交点个数
var counter = 0;
// 水平射线和多边形边的交点x坐标
var xinters;
// 线段起点和终点
var p1, p2;
// for循环
for (let i = 0; i < pts.length; i++) {
p1=pts[i]
p2 = pts[(i+1) % pts.length];// 最后一个点等于起点pts[0]
if (pt[1] > Math.min(p1[1], p2[1]) &&pt[1] <= Math.max(p1[1], p2[1])) {
xinters =
(pt[1] - p1[1]) *
(p2[0] - p1[0]) /
(p2[1] - p1[1]) +
p1[0];
if (p1[1] == p2[1] || pt[0] <= xinters) {
counter++;
}
}
}
if (counter % 2 == 0) {
return false;
} else {
return true;
}
}
算法中核心有两步;
以多边形的P1P2线段为例,其他的线段道理一样,遍历计算即可
1 确定P点在两条虚线中间;
2 判断P点在G点左侧或者右侧
图示如下;
(1) 根据y值限定范围
代码一:pt[1] > Math.min(p1[1], p2[1]) &&pt[1] <= Math.max(p1[1], p2[1])
上面代码表示:如果P点的y0值在两条虚线y1和y2内,则算法继续执行;即如果大于最大虚线或者小于最小虚线,那么过P点的射线不可能和线段有交点,直接返回false即可
(2)确定是否有交点/strong>
代码:pt[0] <= (pt[1] - p1[1]) *(p2[0] - p1[0]) /(p2[1] - p1[1]) +p1[0]
上面代码表示:计算水平射线和线段的交点x坐标;因为是朝向x轴正方向的射线,如果交点x在目标点p的右侧,即可判断有交点;count+1;
原理就是先确定P1P2的直线方程(y-y1)/(y2-y1)=(x-x1)/(x2-x1) ;然后将y=y0代入即可求出G点的x0坐标;
(3)最后验证/strong>
打开geojson.io网址
拾取如下的多边形和三个点位的坐标;用上面的函数测试
QQ:3410192267 | 技术支持 微信:popstarqqsmall
Copyright ©2017 xiaobaigis.com . 版权所有 鲁ICP备17027716号