当前位置：网站首页>如何判断一个点在多边形内

如何判断一个点在多边形内

2022-08-07 12:47:00 【qq_42987967】

一、从三角形开始说起---怎么判断一个点在三角形内

三角形是最简单的多边形了。先说说三角形有哪些判断方法。

参考自：判断一个点是否在三角形内部 - 知乎

几种方法判断平面点在三角形内_独L无二的博客-CSDN博客_判断点在三角形内

先假设有 $\Delta ABC$ ，平面上某点为P。

下面只给出简述，具体实现还得去看参考链接：

1.面积法

简述：将P点与三角形的三个顶点A、B、C连接，分割成三个小三角形 $\Delta PAB$ 、 $\Delta PAC$ 、 $\Delta PBC$ ，这三个小三角形面积之和等于 $\Delta ABC$ 面积之和则说明P在三角形内。

2.叉积法

简述：对三角形逆时针取向量，那么P点必然在这三个向量的左侧。依照这个特性进行叉积判断叉积后的方向是否指向同一个位置可判断是否在三角形内。

3.重心坐标法(斜坐标系法)

可参考这个链接辅助理解：三角形重心坐标 - 知乎

本质上是以三角形的边建立一个坐标系.

以上三种方法应该是最经典的三种方法了。

二、怎么判断一个点在多边形内

参考自：

判断点是否在多边形内部_致守的博客-CSDN博客_判断点是否在多边形内部的方法

详谈判断点在多边形内的七种方法（最全面） hdu1756 hrbust1429 为例_WilliamSun0122的博客-CSDN博客_判断点在多边形内算法

点是否在多边形内的判定方法

三角形重心坐标 - 知乎

假设为判断某点P是否在多边形A1A2A3A...内。

1.面积和判断法

同上面三角形的判断方法一样，可以将点P与多边形所有顶点连线构成子三角形，判断这些子三角形的面积之和是否等于多边形面积之和。

2.叉积法(适合凸多边形)

同上面三角形的判断方法一样，对凸多边形逆时针取向量，那么P点必然在这些向量的左侧。依照这个特性进行叉积判断叉积后的方向是否指向同一个位置可判断是否在多边形内。

3.重心坐标法

同上面三角形的判断方法一样，将多边形划分成若干三角形，然后用重心坐标性质判断。

4.内角和法

将P点与多边形各个顶点连线，环绕多边形一周，内角和为360°说明在多边形内。

5.光线投射算法

又称交叉数算法或奇偶规则算法

以被P为端点，向任意方向作射线（一般水平向右作射线），统计该射线与多边形的交点数。如果为奇数，P在多边形内；如果为偶数，P在多边形外。

6.二分法

这个是最巧妙的方法。将多边形划分为若干区域，二分地去查询落在哪个子区域，判断是落在哪个子区域内后判断是否落在该区域的三角形内，若是则在多边形内，若不是则在多边形外。

原网站

版权声明
本文为[qq_42987967]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_42987967/article/details/126197796