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

[转]JS实现判断点是否在多边形内部(3)–回转数法实现

前端 李新广 1212℃ 0评论

原文地址:http://www.html-js.com/article/1538 (前端乱炖)
射线法是一种很简单直观的判断平面内点是否在多边形内的方法。除了射线法还有很多其他的方法,今天就再介绍一种通过回转数来判断的方法。
平面中的闭合曲线关于一个点的回转数(又叫卷绕数),代表了曲线绕过该点的总次数。下面这张图动态演示了回转数的概念:图中红色曲线关于点(人所在位置)的回转数为 2。
这里写图片描述
回转数是拓扑学中的一个基本概念,具有很重要的性质和用途。本文并不打算在这一点上展开论述,这需要具备相当的数学知识,否则会非常乏味和难以理解。我们暂时只需要记住回转数的一个特性就行了:当回转数为 0 时,点在闭合曲线外部。
对于给定的点和多边形,回转数应该怎么计算呢?

  1. 用线段分别连接点和多边形的全部顶点。 这里写图片描述
  2. 计算所有点与相邻顶点连线的夹角。 这里写图片描述
  3. 计算所有夹角和。注意每个夹角都是有方向的,所以有可能是负值。 这里写图片描述
  4. 最后根据角度累加值计算回转数。看过本文开头的介绍,很容易理解 360°(2π)相当于一次回转。

思路介绍完了,下面两点是实现中需要留意的问题。

  1. JavaScript 的数只有 64 位双精度浮点这一种。对于三角函数产生的无理数,浮点数计算不可避免会造成一些误差,因此在最后计算回转数需要做取整操作。
  2. 通常情况下,平面直角坐标系内一个角的取值范围是 -π 到 π 这个区间,这也是 JavaScript 三角函数 Math.atan2() 返回值的范围。但 JavaScript 并不能直接计算任意两条线的夹角,我们只能先计算两条线与 X 正轴夹角,再取两者差值。这个差值的结果就有可能超出 -π 到 π 这个区间,因此我们还需要处理差值超出取值区间的情况。

代码实现:

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

转载请注明:大道至简 » [转]JS实现判断点是否在多边形内部(3)–回转数法实现

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

表情

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

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