判断点在多边形|圆形内的方实现方式分析及代码实现
Author：zhoulujun Date：
判断点是否在圆内
判断点是否在圆内，其实比较简单
套用小学的数学的几何知识：圆内的所有点与圆心的距离都小于的圆的半径
/**
* 判断一个点是否在圆的内部
* @param {[number,number]} point 测试点坐标
* @param {[number,number]} circle 圆心坐标
* @param {number} r 圆半径
* 返回true为真，false为假
* */
function pointInsideCircle(point, circle, r) {
if (r === 0) return false;
const dx = circle[0] - point[0];
const dy = circle[1] - point[1];
//求点到圆心的距离，用到了勾股定理
return (dx * dx) + (dy * dy) <= r * r;
}判断点是否在圆内则需要判断点到圆心的距离：
若大于圆半径，点在圆外；
若等于圆半径，点在圆上；
若小于圆半径，点在圆内；
根据圆心坐标求出圆上的点坐标，同样假设圆心坐标为(a,b)，圆半径为r，圆上坐标为(x,y)，且圆上的点位针对顺时针水平方向应该是有个偏转角度的，设为α，则：
x = a + Math.cos(2 * Math.PI / 360 * α) * r; //Math.cos(0)=1 y = b + Math.sin(2 * Math.PI / 360 * α) * r; //Math.sin(0)=0
同样可以判断点是否在园内
判断点是否在多边形内
判断点与多边形的关系，是计算几何的经典问题，点与多边形的关系可以分为：点在多边形内（inside）、点在多边形外（outside）以及点在多边形的边上（onside）三种。具体方法 ezhchai 写的很好，但是还招搬一份备份。
判断一个点是否在多边形内部的典型方法：
向量积 值判断发：多边形可看做从某点出发的闭合回路，内部的点永远在回路的同一边。实现以上思想的直接方法就是通过向量积的概念
面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。
夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。
光线投射法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。
向量积
首先可回顾一下《向量积》，
在如上图所示多边形中，需要判断点O在多边形内，首先看顶点A和B组成的边AB可看作是一条向量，A指向B，则O在AB的右侧，按照右手定则，向量AO与向量AB的向量积的数值为正，顺时针方向，可以看出向量BO与向量BC的向量积数值为正。以此类推，多边形所有的边与O点按此规律组成的向量积数值都为正。如果按逆时针方向，所有向量积数值均为负。当点在多边形外时，顺次进行向量积计算，符号会出现正负交替。如果向量积为0，说明该点在多边形的这条边上。
参考代码：
int InPolygon_CP(const CZPolygon& polygon, CZPoint_t pt){
int itNumPt = polygon.size();
CZPoint_t pt_1, pt_2;
double duCP_pre = 0.0;
for (int i=0; i<(itNumPt-1); i++){
pt_1 = polygon[i];
//pt_2 = polygon[(i + 1) % itNumPt];
pt_2 = polygon[i + 1];
double duCP = CrossProduct(&pt_1, &pt, &pt_2);
if(0.0 == duCP)
return ONSIDE;
if (0 == i)
duCP_pre = duCP;
else
if (duCP*duCP_pre < 0)
return OUTSIDE;
}
return INSIDE;
}面积法
判断点和多边形关系的另一个思路是：多边形内的点与多边形各个顶点的连线，组成的三角形的面积和等于多边形的面积。
图例说明，如下图所示：
O点在多边形之内时，其与多边形所有顶点的连线，组成6个三角形，显而易见，这6个三角形的面积之和与多边形的面积相等。这一特性对多边形边上的点也适用。
P点在多边形之外，其与多边形所有顶点的连线，组成6个三角形，显而易见，这6个三角形的面积之和与多边形的面积不相等。确切的说，是三角形面积之和大于多边形面积。
至于求多边形与三角形的面积，也使用向量积。
参考代码:
int InPolygon_Area(const CZPolygon& polygon, CZPoint_t pt){
double duPloyArea = CalPolygonArea(polygon);
int itNumPt = polygon.size();
CZPoint_t pt_1, pt_2;
double duArea = 0.0;
for (int i=0; i<(itNumPt-1); i++){
pt_1 = polygon[i];
pt_2 = polygon[i + 1];
double duTriArea = ABS(CrossProduct(&pt_1, &pt, &pt_2));
if(0.0 == duTriArea)
return ONSIDE;
duArea += 0.5 * duTriArea;
}
return ABS(duPloyArea-duArea)<EPS? INSIDE: OUTSIDE;
}
————————————————
版权声明：本文为CSDN博主「ezhchai」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ezhchai/article/details/78866694角度和法
“角度和法”的思路是：多边形内的点，与所有顶点顺次连接形成向量的夹角之和为2π。
图例说明，如下图所示：
O点在多边形之内，其与多边形所有顶点的连线，组成6个向量，顺次形成6个向量夹角，显而易见，这6个夹角之和为2π。
P点在多边形之外，其与多边形所有顶点的连线，组成6个向量，顺次形成6个向量夹角，显而易见，这6个夹角之和不等于2π。确切的说是小于2π。
计算夹角的方法可按如下公式实现：
1、a=(x1,y1,z1)，b=(x2,y2,z2)。a*b=x1*x2+y1*y2+z1*z2
2、|a|=√(x1^2+y1^2+z1^2)，|b|=√(x2^2+y2^2+z2^2)
3、cosθ=a*b/(|a|*|b|)，角θ=arccosθ。
公式中，a和b就是组成夹角的两个向量，在反余弦函数括号中，分子部分为两个向量的点乘，分子部分为两个向量各自的2范数相乘。在这里要说明一下，如果要判断的点就是多边形顶点之一，则a和b其中之一的2范数为0，需要特别处理；如果点在多边形的边上，则有存在一个夹角为π的情况。这两种情况均可以认为该点在多边形的边上。
此方法和之前谈到的向量积法、面积法一样，可以直接适用于凸多边形，至于凹多边形，也可以用，不过要将凹的部分可能重复计算夹角的地方调整坐标在集合中的顺序后计算夹角。另外一个问题和面积法相似，就是计算角度存在一定的舍入误差，影响计算的精度。
int InPolygon_Angle(const CZPolygon& polygon, CZPoint_t pt){
int itNumPt = polygon.size();
CZPoint_t pt_1, pt_2;
double duAngleAll = 0.0;
for (int i = 0; i < (itNumPt - 1); i++) {
pt_1 = polygon[i];
pt_2 = polygon[i + 1];
double duA = Angle(&pt, &pt_1, &pt_2);
if ((NOANGLE == duA) || (ABS(duA - PI) < EPS))
return ONSIDE;
duAngleAll += duA;
}
return ABS(duAngleAll - 2*PI)<EPS ? INSIDE : OUTSIDE;
}终极大招来了，射线法是解决这一问题的最优方法，其他方法仅具有理论意义，如果工程应用的话，知道这个方法就够了。
光线投射法
“判断一个点是否在一个多边形里”，一开始以为是个挺难的问题，但Google了一下之后发现其实蛮简单，所用到的算法叫做“Ray-casting Algorithm”，中文应该叫“光线投射算法”，这是维基百科的描述：维基百科
从点P出发，任意引一条射线（模拟光线）。
记录该条射线与多边形A的边相交点的个数。
判断交点的个数，若为偶数表示在图形外，若为奇数表示在图像内。
射线法的思想是：以目标点为端点引一条射线，计算这条射线和多边形所有边的交点数目。如果交点个数为奇数，则点在多边形部，反之则在多边形外部。
如下图所示：
所谓射线法，关键在于单向发射，为简化问题，以水平线为例，程序实现中也是这么处理的。O点向右发出射线，与多边形的交点是B、C、D，向左发出射线，交点是A，均为奇数个。P点在多边形外，无论想哪方向发出摄像，都有2个交点。
简单地说可以这么判断：从这个点引出一根“射线”，与多边形的任意若干条边相交，累计相交的边的数目，如果是奇数，那么点就在多边形内，否则点就在多边形外。
如图，A点引一条射线，与多边形3条边相交，奇数，所以A点在多边形内，而从B点引一条射线，与多边形的2条边相交，偶数，所以B点在多边形外。
把这个算法用于判断地图上所在的位置是否在一个范围之内，可先用鼠标在地图上绘制出一个多边形区域，然后再用这个方法判断一个坐标是否在这个多边形范围内
嗯？怎么五角星居然中间没被镂空？这是怎么回事？经过研究，我发现高德地图的鼠标工具的多边形填充用的是另外一套规则，叫做“None Zero Mode”，判断一个点是否在多边形内的规则就变成了：从这个点引出一根“射线”，与多边形的任意若干条边相交，计数初始化为0，若相交处被多边形的边从左到右切过，计数+1，若相交处被多边形的边从右到左切过，计数-1，最后检查计数，如果是0，点在多边形外，如果非0，点在多边形内。回到五角星的例子，这次要注意多边形线条描绘的方向：
从C点引出一条射线，与这条射线相交的两条多边形的边均是从左向右切过，总计数是2，因此C点在多边形内。用个更形象点的方式描述就是：从C点出发，一直朝一个方向走，遇到两条单行道，都是从自己的左边切至右边的方向，计数+1，计数+1，总计数所以是2。
算法实现起来居然很简单，几行代码即可，真的是几行代码，我用的是C#，大家可以轻轻松松改成别的。
C#实现
public static class RayCastingAlgorithm {
public static bool IsWithin(Point pt, IList<Point> polygon, bool noneZeroMode) {
int ptNum = polygon.Count();
if (ptNum < 3) {
return false;
}
int j = ptNum - 1;
bool oddNodes = false;
int zeroState = 0;
for (int k = 0; k < ptNum; k++) {
Point ptK = polygon[k];
Point ptJ = polygon[j];
if (((ptK.Y > pt.Y) != (ptJ.Y > pt.Y)) && (pt.X < (ptJ.X - ptK.X) * (pt.Y - ptK.Y) / (ptJ.Y - ptK.Y) + ptK.X)) {
oddNodes = !oddNodes;
if (ptK.Y > ptJ.Y) {
zeroState++;
}
else {
zeroState--;
}
}
j = k;
}
return noneZeroMode?zeroState!=0:oddNodes;
}
}光线投射法【升级版】
从点P出发，任意引一条射线（模拟光线）。
该条射线与多边形A的边相交时，若射线从边的左侧贯穿记录leftCount加1，若射线从边的右侧贯穿记录rightCount加1。
若leftCount-rightCount等于0表示在图形外部，若不等于0表示图形内部。
/**
* @param dot {{x,y}} 需要判断的点
* @param coordinates {{x,y}[]} 多边形点坐标的数组，为保证图形能够闭合，起点和终点必须相等。
* 比如三角形需要四个点表示，第一个点和最后一个点必须相同。 * @param noneZeroMode 对不规则图形进行判断
* @param noneZeroMode {number}
*/
function judge(dot,coordinates,noneZeroMode) {
// 默认启动none zero mode
noneZeroMode=noneZeroMode||1;
var x = dot.x,y=dot.y;
var crossNum = 0;
// 点在线段的左侧数目
var leftCount = 0;
// 点在线段的右侧数目
var rightCount = 0;
for(var i=0;i<coordinates.length-1;i++){
var start = coordinates[i];
var end = coordinates[i+1];
// 起点、终点斜率不存在的情况
if(start.x===end.x) {
// 因为射线向右水平，此处说明不相交
if(x>start.x) continue;
// 从左侧贯穿
if((end.y>start.y&&y>=start.y && y<=end.y)){
leftCount++;
crossNum++;
}
// 从右侧贯穿
if((end.y<start.y&&y>=end.y && y<=start.y)) {
rightCount++;
crossNum++;
}
continue;
}
// 斜率存在的情况，计算斜率
var k=(end.y-start.y)/(end.x-start.x);
// 交点的x坐标
var x0 = (y-start.y)/k+start.x;
// 因为射线向右水平，此处说明不相交
if(x>x0) continue;
if((end.x>start.x&&x0>=start.x && x0<=end.x)){
crossNum++;
if(k>=0) leftCount++;
else rightCount++;
}
if((end.x<start.x&&x0>=end.x && x0<=start.x)) {
crossNum++;
if(k>=0) rightCount++;
else leftCount++;
}
}
return noneZeroMode===1?leftCount-rightCount!==0:crossNum%2===1;
},参考文章：
判断点与多边形的关系（1）：向量积法 https://blog.csdn.net/ezhchai/article/details/78864336
判断点与多边形的关系（2）：面积法 https://blog.csdn.net/ezhchai/article/details/78866694
判断点与多边形的关系（3）：角度和法 https://blog.csdn.net/ezhchai/article/details/78866923
判断点与多边形的关系（4）：射线法 https://blog.csdn.net/ezhchai/article/details/78867367
判断一个点是否在一个多边形里 https://www.cnblogs.com/guogangj/p/5127527.html
canvas上，用javascript如何判断一个点位是否在某个圆内？ https://blog.csdn.net/hi_lemon/article/details/88568688
前端小功能: 绘制多边形，并判断某个点是否在区域内 https://www.cnblogs.com/bore/p/11427860.html
转载本站文章《判断点在多边形|圆形内的方实现方式分析及代码实现》,
请注明出处：https://www.zhoulujun.cn/html/theory/Mathematics/Geometry/8608.html