判断点是否在多边形内部两个算法

浅浅的花香味﹌ 2024-02-19 13:57 9阅读 0赞

判断点P是否在多边形中时计算几何中一个非常重要基本的算法。

方法一是：

用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点运算所以会带来一定的误差，

首先取目标点和多边形任意一条边构成三角形，三角形的符号这样确定，假设以多边形每个顶点逆时针顺序为正方向，按照这个方向每条边都是一个向量，当目标点在多边形某条边向量左边时，目标点和这条边构成的三角形的面积为正，当目标点在多边形某条边向量的右边时，目标点和这条边构成的三角形的面积为负

取目标点和多边形所有边构成的带符号三角形的面积之和假设为S，然后在取多边形任意一个顶点，做这个顶点和多边形所有边带符号三角形之和假设为P，P就为多边形的面积，比较S与P，假如他们相等，点就在多边形内部，假如他们不相等，点不在多边形内部

方法二是：

以点P为端点，向左方做射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形。。。所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外

单有些特殊情况需要考虑，当L和多边形顶点相交的时候，两个顶点只能算为一个交点，当L和多边形的一条边平行的时候，这条边应该忽略不计，

为了统一起见，我们在计算射线L和多边形的交点的时候：1）对于多边形的水平边不作考虑2）对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略3）对于P在多边形边上的情形，直接课判断P属于多边形。由此得出算法的伪代码如下

Count<-0;

以P为端点，作从右向左的射线L；

For 多边形的每条边s

Do if P 在边s上

Then returntrue;

If s 不是水平的

Then if s 的一个端点在L上

If 该端点是s 两端点中纵坐标较大的端点

Then count <-count + 1

Else if s 和L 相交

Then count <-count +1

If count mod 2 =1

Then returntrue;

Else returnfalse;

其中，做射线L的方法是：设P\`的纵坐标和P相同，横坐标为正无穷大（很大的一个数），则P和P\`就确定了射线L

判断点是否在多边形中的这个算法的时间复杂度为O（n）

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关如何判断两个多边形是否相交？——多边形相交判定算法详解

如何判断两个多边形是否相交？——多边形相交判定算法详解在计算机图形学中，判断两个多边形是否相交是一项很重要的任务。这涉及到各种应用场景，如碰撞检测、模拟物理效果等。在本篇文

心已赠人/ 2024年03月26日 20:41/ 0 赞/ 42 阅读

相关判断点是否在多边形内部两个算法

判断点P是否在多边形中时计算几何中一个非常重要基本的算法。方法一是：用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点运算所以会带来一定的误差，首先

浅浅的花香味﹌/ 2024年02月19日 13:57/ 0 赞/ 10 阅读

相关 C++判断点是否在三角形内部

[https://www.imooc.com/article/details/id/21972][https_www.imooc.com_article_details_id_

矫情吗；*/ 2023年01月12日 04:26/ 0 赞/ 107 阅读

相关判断一个点是否在多边形内部

一、比如说，我就随便涂了一个多边形和一个点，现在我要给出一种通用的方法来判断这个点是不是在多边形内部（别告诉我用肉眼观察……）。 ![enter image descript

比眉伴天荒/ 2022年08月07日 12:50/ 0 赞/ 258 阅读

相关点在多边形内算法，C#判断一个点是否在一个复杂多边形的内部

判断一点是否在不规则图像的内部算法，如下图是由一个个点组成的不规则图像，判断某一点是否在不规则矩形内部，先上效果图 ![20170622181708931][] 算法

骑猪看日落/ 2022年06月13日 01:18/ 0 赞/ 211 阅读

相关点在多边形内算法，JS判断一个点是否在一个复杂多边形的内部

点在多边形内算法，JS判断一个点是否在一个复杂多边形的内部： function isInPolygon(checkPoint, polygonPoints) {

阳光穿透心脏的1/2处/ 2022年06月05日 08:42/ 0 赞/ 204 阅读

相关判断一个点是否在三角形内部

![Center][] //判断一个点是否在三角形内部 public class IsIntriangle{ //(1)面积法求解

- 日理万妓/ 2022年05月28日 07:06/ 0 赞/ 163 阅读

相关判断一个点是否在矩形内部

![20180330221327550][] //判断一个点是否在矩形内部 public class InMatrix{ //(

以你之姓@/ 2022年05月28日 06:23/ 0 赞/ 200 阅读

相关判断点是否在多边形内

再经典不过的算法了： // 功能：判断点是否在多边形内 // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! //参数： //

ゝ一纸荒年。/ 2022年03月25日 08:40/ 0 赞/ 240 阅读

相关 C++ 点在多边形内算法——判断一个点是否在一个复杂多边形的内部

转自：http://blog.csdn.net/hjh2005/article/details/9246967 新页面（[new page][]）介绍了将样条曲线添加到此技术

亦凉/ 2022年03月19日 02:54/ 0 赞/ 271 阅读