责任编辑:
chjiegg
时间:2022-01-27
来源:转载于:CSDN
责任编辑:
chjiegg
时间:2022-01-27
来源:转载于:CSDN
判断点是否在任意多边形内
判断方法:
一. 射线判断
过目标点做一条直线(两条反方向的射线),每条射线与多边形边的交点数量都是奇数,则点在多边形内,否则在多边形外部;
二. 夹角判断
以目标点为顶点,与多边形一条边的两个端点(端点分先后顺序)组成一个夹角(计算出的夹角会有正负),所有夹角之和为360度;
三. 面积判断
目标点与多边形每条边组成的三角形,面积之和等于多边形面积则在内部,否则在外部(原理与判断夹角类似,面积计算量更大)。
详细说明一下射线判断:
// 射线判断
// 过目标点做一条直线(两条反方向的射线),每条射线与多边形边的交点(射线穿过多边形的边)数量都是奇数,则点在多边形内,否则在多边形外部;
//1. 射线方向可以是任意,为了方便计算取水平或竖直方向;
//2. 可以通过不断缩小判断范围,省略每次判断不必要的计算量:
//2.1 根据多边形顶点信息,找到坐标X的最大、最小值,Y的最大、最小值,如果目标点不在该范围内,则在多边形外,不需要进行后续计算,返回结果;
//2.2 如果目标点与多边形端点重合(点重合),则在多边形上,返回结果;
//2.3 如果目标点在多边形的边上(点在线段上)(包含2.2情况,即目标点与线段端点重合),则在多边形上,返回结果;
//2.4 判断目标点在多边形内部或外部。
//3. 判断目标点在多边形内部或外部:
//3.1 目标点左右两个方向的两条射线,任意一条与多边形边的交点数量为0,则在外部,返回结果;
//3.2 两条射线与多边形边的交点数量均为奇数,则在内部,返回结果;
//3.3 其余结果均为点在多边形外部。
//3.4 特殊情况处理:
//3.4.1 经过顶点如何计算?算一个交点or两个交点?
// 一个顶点连接两条边,经过顶点时,如果两条边都在该射线的同一方向,则视为射线没有穿过多边形,交点数为0,如果两条边分别在射线的不同方向,视为射线穿过了多边形,交点数为1;
//3.4.2 射线与多边形边重叠,交点个数?
// 射线经过多边形的一条边,与经过顶点同理,重叠边的两条相邻边,如果两条边都在该射线的同一方向,则视为射线没有穿过多边形,交点数为0,如果两条边分别在射线的不同方向,视为射线穿过了多边形,交点数为1;