前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >一种快速判断点在多边形内的算法

一种快速判断点在多边形内的算法

作者头像
sunsky
发布于 2022-09-08 07:08:45
发布于 2022-09-08 07:08:45
1.3K01
代码可运行
举报
文章被收录于专栏:sunskysunsky
运行总次数:1
代码可运行

由于业务需要, 我总结了一种快速判断点在多边形内的算法。

先说思路:

如图:

  • 如果点在多边形内部,射线第一次穿越边界一定是穿出多边形。
  • 如果点在多边形外部,射线第一次穿越边界一定是进入多边形。

我们可以归纳出:

    • 当射线穿越多边形边界的次数为偶数时,所有第偶数次(包括最后一次)穿越都是穿出,因此所有第奇数次(包括第一次)穿越为穿入,由此可推断点在多边形外部。
    • 当射线穿越多边形边界的次数为奇数时,所有第奇数次(包括第一次和最后一次)穿越都是穿出,由此可推断点在多边形内部。

实现关键点

1. 点在多边形的边上

前面我们讲到,射线法的主要思路就是计算射线穿越多边形边界的次数。那么对于点在多边形的边上这种特殊情况,射线出发的这一次,是否应该算作穿越呢?

思路: 先求边和点的交点, 即边的起点y乘以边斜率,得到交点的x, 若x == X, X是参考点的横坐标,则点在线上。

2. 点和多边形的顶点重合

思路:参考点与边顶点重合,则直接是 x == X && y == Y ,其中x,y是边顶点, X,Y是参考点, 则直接返回。

3. 射线经过多边形顶点

思路:这时相交点次数无论内外都是偶数次,无法判断。不过,这里看射线两侧的边如果都在两侧时算作一次“穿过”,即 y == Y时, x1 > X 并且 x2 <= X (或  x1 < X 且 x2 > X),穿过数次加1 , 其中X,Y是参考点, x1,y1 ,  x2, y2是线段顶点。

4. 射线刚好经过一条边

思路: 这个最简单, 直接判断 y == Y,可以理解成穿过了这条边的2个顶点, Y是参考点的纵坐标, y是边的纵坐标。

问题都解决了,其实并不复杂。

实现代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
type Point struct {
	X float64
	Y float64
}

func IfPointsInPolygon(point Point, area []Point) bool {
	// 目标点的x, y坐标
	x := point.X
	y := point.Y

	// 多边形的点数
	count := len(area)

	// 点是否在多边形中
	var inInside bool

	// 浮点类型计算与0的容差
	precision := 2e-10

	// 依次计算每条边,根据每边两端点和目标点的状态栏判断
	for i, j := 0, count-1; i < count; j, i = i, i+1 {
		// 记录每条边上的两个点坐标
		x1 := area[i].X
		y1 := area[i].Y
		x2 := area[j].X
		y2 := area[j].Y

		// 判断点与多边形顶点是否重合
		if (x1 == x && y1 == y) || (x2 == x && y2 == y) {
			return true
		}

		// 判断点是否在水平直线上
		if (y == y1) && (y == y2) {
			return true
		}

		// 判断线段两端点是否在射线两侧
		if (y >= y1 && y < y2) || (y < y1 && y >= y2) {
			// 斜率
			k := (x2 - x1) / (y2 - y1)

			// 相交点的 x 坐标
			_x := x1 + k*(y-y1)

			// 点在多边形的边上
			if _x == x {
				return true
			}

			// 浮点类型计算容差
			if math.Abs(_x-x) < precision {
				return true
			}

			// 射线平行于x轴,穿过多边形的边
			if _x > x {
				inInside = !inInside
			}
		}
	}

	return inInside
}
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#压测
/private/var/folders/9l/9h6c50j93qs8c43wpwnvhnbc0000gn/T/GoLand/___gobench_common_algorithm_polygon.test -test.v -test.paniconexit0 -test.bench . -test.run ^$
goos: darwin
goarch: amd64
pkg: common/algorithm/polygon
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkPIP
BenchmarkPIP-12    	29140065	        40.57 ns/op
PASS
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-07-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
判断点是否在多边形内的Python实现及小应用(射线法)
判断一个点是否在多边形内是处理空间数据时经常面对的需求,例如GIS软件中的点选功能、根据多边形边界筛选出位于多边形内的点、求交集、筛选不在多边形内的点等等。判断一个点是否在多边形内有几种不同的思路,相应的方法有:
蛰虫始航
2019/09/29
10K2
判断点是否在多边形内的Python实现及小应用(射线法)
判断点在多边形内算法的C++实现
判断平面内点是否在多边形内有多种算法,其中射线法是其中比较好理解的一种,而且能够支持凹多边形的情况。该算法的思路很简单,就是从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。如下图所示:
charlee44
2019/08/13
6.1K0
平面几何:判断点是否在多边形内(射线法)
之前我们讲解了如何利用叉乘 判断点是否在凸多边形内。但该算法限制较大,多边形必须为凸多变形。
前端西瓜哥
2024/05/22
6600
平面几何:判断点是否在多边形内(射线法)
计算几何算法概览
  计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为计算机科学的一个分支,计算几何主要研究解决几何问题的算法。在现代工程和数学领域,计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中,我们将对计算几何常用的基本算法做一个全面的介绍,希望对您了解并应用计算几何的知识解决问题起到帮助。
owent
2023/03/05
1.8K0
丘比特的箭(点是否在面内)- HDU 1756
对于点A是否在多边形P内的判定, 一般有两种方法:射线法和转角法。 这里介绍一下射线法。
ACM算法日常
2018/08/07
1K0
丘比特的箭(点是否在面内)- HDU 1756
多边形的点序
凸多边形:Convex polygon,non-self-intersecting polygon, simple polygon说的都是它(定义详见 wiki)。常见的凸多边形有:矩形、三角形等。
用户4363240
2020/01/01
1.7K0
多边形的点序
算法 - PNPoly解决点和多边形问题
计算点到多边形最短距离的基本原理是:依次计算点到多边形每条边的距离,然后筛选出最短距离。
用户2987604
2020/06/15
2.6K0
算法 - PNPoly解决点和多边形问题
平面几何:判断点是否在凸多边形内
在之前的 求两向量的夹角的文章 中我提到过,对于两个向量,我们可以利用叉积的符合右手定则,判断两个向量的位置关系。
前端西瓜哥
2024/05/15
2680
平面几何:判断点是否在凸多边形内
Mapinfo高阶-判断点是否位于多边形内
笔者在工作过程中遇到一个场景,需要批量判断点是否位于某个多边形,搜索了几个算法,发现过于复杂,本身理解就有困难,编成代码就更难了。
披头
2019/12/26
1.9K0
利用向量积(叉积)计算三角形的面积和多边形的面积
利用向量积(叉积)计算三角形的面积和多边形的面积: 向量的数量积和向量积: (1)  向量的数量积 (1)  向量的向量积 两个向量a和b的叉积(向量积)可以被定义为: 在这里θ表示两向量之间的角夹角
Angel_Kitty
2018/04/08
6.5K0
利用向量积(叉积)计算三角形的面积和多边形的面积
LeetCode 469. 凸多边形(向量叉积)
文章目录 1. 题目 2. 解题 1. 题目 给定一个按顺序连接的多边形的顶点,判断该多边形是否为凸多边形。 注: 顶点个数至少为 3 个且不超过 10,000。 坐标范围为 -10,000 到 1
Michael阿明
2021/02/19
9850
带你实现一个简单的多边形编辑器
多边形编辑器少数见于一些图片标注需求,常见于地图应用,用来绘制区域,比如高德地图:
街角小林
2022/06/15
1.2K0
带你实现一个简单的多边形编辑器
【Web技术】1139- 手把手教你实现手绘风格图形
https://juejin.cn/post/6942262577460314143
pingan8787
2021/11/17
8850
百度地图电子围栏功能
今年疫情以来,工作都比较紧凑,没能抽出时间来记录工作日常了。最近接触一个项目需要使用到百度地图的围栏功能,作为前期调研,先探探路。 经过一番搜搜,找到一篇不错的文章。专门介绍,百度地图围栏的。地址如下:https://www.cnblogs.com/CherishTheYouth/p/CherishTheYouth_20190416.html
用户5640963
2020/10/26
4.2K0
百度地图电子围栏功能
HDOJ 2036 改革春风吹满地(多边形的面积)
Problem Description “ 改革春风吹满地, 不会AC没关系; 实在不行回老家, 还有一亩三分地。 谢谢!(乐队奏乐)”
谙忆
2021/01/20
3000
求解任意多边形的面积(平面内)
  平面内多边形的计算,也就是平面坐标系内多边形的计算,已知各定点坐标,有顺序的,逆时针或者顺时针。根据给出坐标求面积。
用户2038589
2018/09/06
8380
凸包多边形最小外切矩形算法
其实我对算法不是很在行, 但是项目中有用到某种算法 来实现某种功能, 也得硬着头皮来实现. 这是很早之前的一个项目了, 要计算一个凸包多边形最小外切矩形 . 遇到这种情况肯定是束手无策.. 在翻了一些资料之后. 终于完成了.
chuchur
2022/10/25
8970
凸包多边形最小外切矩形算法
ACM计算几何篇_acm数学
https://linxi99.gitee.io/20190211/ACM计算几何篇/
全栈程序员站长
2022/11/19
1.5K0
ACM计算几何篇_acm数学
​LeetCode刷题实战469:凸多边形
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/12/17
4680
​LeetCode刷题实战469:凸多边形
point inside 点在框内
如果是矩形比较简单,直接判断四个点的范围,不能推广到多边,考虑到图形的凹凸就更复杂,考虑到程序需要直接拿来用罢了,
vanguard
2020/03/13
1.3K0
相关推荐
判断点是否在多边形内的Python实现及小应用(射线法)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验