治疗技术焦虑的方法就是学习!

[转]JS实现判断点是否在多边形内部(1)–射线法理论

前端 李新广 730℃ 0评论

原文地址:http://www.html-js.com/article/1517 ( 前端乱炖)
随便涂一个多边形和一个点,现在我要给出一种通用的方法来判断这个点是不是在多边形内部(别告诉我用肉眼观察……)。
这里写图片描述
首先想到的一个解法是从这个点做一条射线,计算它跟多边形边界的交点个数,如果交点个数为奇数,那么点在多边形内部,否则点在多边形外。
这里写图片描述
这个结论很简单,那它是怎么来的?下面就简单讲解一下。
首先,对于平面内任意闭合曲线,我们都可以直观地认为,曲线把平面分割成了内、外两部分,其中“内”就是我们所谓的多边形区域。
这里写图片描述
基于这一认识,对于平面内任意一条直线,我们可以得出下面这些结论:

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

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

  • 如果点在多边形内部,射线第一次穿越边界一定是穿出多边形。
  • 如果点在多边形外部,射线第一次穿越边界一定是进入多边形。 这里写图片描述

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

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

第一篇:射线法理论
第二篇:射线法实现
第三篇:回转数法实现

转载请注明:大道至简 » [转]JS实现判断点是否在多边形内部(1)–射线法理论

喜欢 (1)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址