判断点是否在任意多边形内(理论)
责任编辑:chjiegg     时间:2022-01-27     来源:转载于:CSDN
责任编辑:chjiegg
时间:2022-01-27  来源:转载于:CSDN
分类: 技术分享
浏览量: 381

判断点是否在任意多边形内

判断方法:

一. 射线判断

过目标点做一条直线(两条反方向的射线),每条射线与多边形边的交点数量都是奇数,则点在多边形内,否则在多边形外部;

二. 夹角判断

以目标点为顶点,与多边形一条边的两个端点(端点分先后顺序)组成一个夹角(计算出的夹角会有正负),所有夹角之和为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;

image.png
image.png
image.png
image.png




来源:转载于:CSDN

回复:

Copyright © 2021 .长沙麦涛网络科技有限公司 All rights reserved. 湘ICP备20015126号-2
联系我们