判断一个点是否在多边形内部 [1] 射线法思路
发布在随便写写2014年11月13日view:11903
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

前言:本文源于前几天看到的一条微博 http://weibo.com/1057676857/Adpfwwfsv

enter image description here

对于 po 主的言论我并不赞同。我是学化学的,没有学过计算机专业的课程,但凭直觉我认为这应该也是计算机图形学里面比较常见的一类问题。并且我认为这并不需要多么高端的计算机专业知识,只要中学数学没有全还给老师,就应该能给出至少一种解法。下面就试着解一下这个题吧。

比如说,我就随便涂了一个多边形和一个点,现在我要给出一种通用的方法来判断这个点是不是在多边形内部(别告诉我用肉眼观察……)。

enter image description here

首先想到的一个解法是从这个点做一条射线,计算它跟多边形边界的交点个数,如果交点个数为奇数,那么点在多边形内部,否则点在多边形外。

enter image description here

这个结论很简单,那它是怎么来的?下面就简单讲解一下。

首先,对于平面内任意闭合曲线,我们都可以直观地认为,曲线把平面分割成了内、外两部分,其中“内”就是我们所谓的多边形区域。

enter image description here

基于这一认识,对于平面内任意一条直线,我们可以得出下面这些结论:

  • 直线穿越多边形边界时,有且只有两种情况:进入多边形或穿出多边形。
  • 在不考虑非欧空间的情况下,直线不可能从内部再次进入多边形,或从外部再次穿出多边形,即连续两次穿越边界的情况必然成对。
  • 直线可以无限延伸,而闭合曲线包围的区域是有限的,因此最后一次穿越多边形边界,一定是穿出多边形,到达外部。

enter image description here

现在回到我们最初的题目。假如我们从一个给定的点做射线,还可以得出下面两条结论:

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

enter image description here

把上面这些结论综合起来,我们可以归纳出:

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

到这里,我们已经了解了这个解法的思路,大家可以试着自己写一个实现出来。关于算法实现中某些具体问题和边界条件的处理,下次接着写,这次画图已经画够了……

后记:给出这个解法后,我简单搜了一下,原来这种算法就叫做射线法(ray casting)或者奇偶规则法(even odd rule),是一种早已被广泛应用的算法。后面还打算介绍另一种通过回转数(winding number,拓扑学的一个概念)解这个问题的思路。

– P.S. –

本系列共三篇:

  1. 射线法思路
  2. 射线法实现
  3. 回转数法

– 完 –

评论
发表评论
1个月前
赞了此文章!
3年前

@qwer 谢谢博主,已经在你的第二篇文章找到答案了

3年前

@Kervin 没明白你的意思?

3年前

@米粽粽 是不是这样:将交点坐标和给定坐标点进行比较,如果交点包含在给定坐标点中,则穿越次数+1或者-1

4年前

@epooren 顶点是有顺序的。组成另一个多边形以后,虽然还是那些点,但数组就不一样了。这个算法要解决的是“给定多边形和点判断位置关系”,给定顶点能画出多少个多边形不是要解决的问题。

4年前

@米粽粽 @芋头 同一组顶点坐标,某些情况可以组成多个不同的多边形。好像漏掉这点了。

4年前

@徐伟思春 这个我下一次会写,在这之前你可以自己思考一下看看有没有办法解决 :)

4年前

我想问,如果穿越了多边形的角的顶点,如何能确保是在多边形内?

4年前

给力的不是一两点呀!!

4年前

灰常灰常灰常灰常优秀,灰常灰常灰常灰常感谢,灰常灰常灰常灰常希望博主快快更新。爱死博主了,么么哒!!!ps.博主个人博客上的东西也非常给力!!!

4年前

大大给力

WRITTEN BY
PUBLISHED IN
随便写写

高兴了就随便写写,不高兴就不写。不保证对你手头的工作有帮助。

我的收藏