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

射线法是一种很简单直观的判断平面内点是否在多边形内的方法。除了射线法还有很多其他的方法,今天就再介绍一种通过回转数来判断的方法。

平面中的闭合曲线关于一个点的回转数(又叫卷绕数),代表了曲线绕过该点的总次数。下面这张图动态演示了回转数的概念:图中红色曲线关于点(人所在位置)的回转数为 2。

enter image description here

回转数是拓扑学中的一个基本概念,具有很重要的性质和用途。本文并不打算在这一点上展开论述,这需要具备相当的数学知识,否则会非常乏味和难以理解。我们暂时只需要记住回转数的一个特性就行了:

当回转数为 0 时,点在闭合曲线外部。

对于给定的点和多边形,回转数应该怎么计算呢?

  1. 用线段分别连接点和多边形的全部顶点。

    enter image description here

  2. 计算所有点与相邻顶点连线的夹角。

    enter image description here

  3. 计算所有夹角和。注意每个夹角都是有方向的,所以有可能是负值。

    enter image description here

  4. 最后根据角度累加值计算回转数。看过本文开头的介绍,很容易理解 360°(2π)相当于一次回转。

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

  1. JavaScript 的数只有 64 位双精度浮点这一种。对于三角函数产生的无理数,浮点数计算不可避免会造成一些误差,因此在最后计算回转数需要做取整操作。

  2. 通常情况下,平面直角坐标系内一个角的取值范围是 -π 到 π 这个区间,这也是 JavaScript 三角函数 Math.atan2() 返回值的范围。但 JavaScript 并不能直接计算任意两条线的夹角,我们只能先计算两条线与 X 正轴夹角,再取两者差值。这个差值的结果就有可能超出 -π 到 π 这个区间,因此我们还需要处理差值超出取值区间的情况。

老规矩,上代码。

  /**
   * @description 回转数法判断点是否在多边形内部
   * @param {Object} p 待判断的点,格式:{ x: X坐标, y: Y坐标 }
   * @param {Array} poly 多边形顶点,数组成员的格式同 p
   * @return {String} 点 p 和多边形 poly 的几何关系
   */
  function windingNumber(p, poly) {
    var px = p.x,
        py = p.y,
        sum = 0

    for(var i = 0, l = poly.length, j = l - 1; i < l; j = i, i++) {
      var sx = poly[i].x,
          sy = poly[i].y,
          tx = poly[j].x,
          ty = poly[j].y

      // 点与多边形顶点重合或在多边形的边上
      if((sx - px) * (px - tx) >= 0 && (sy - py) * (py - ty) >= 0 && (px - sx) * (ty - sy) === (py - sy) * (tx - sx)) {
        return 'on'
      }

      // 点与相邻顶点连线的夹角
      var angle = Math.atan2(sy - py, sx - px) - Math.atan2(ty - py, tx - px)

      // 确保夹角不超出取值范围(-π 到 π)
      if(angle >= Math.PI) {
        angle = angle - Math.PI * 2
      } else if(angle <= -Math.PI) {
        angle = angle + Math.PI * 2
      }

      sum += angle
    }

    // 计算回转数并判断点和多边形的几何关系
    return Math.round(sum / Math.PI) === 0 ? 'out' : 'in'
  }

– P.S. –

本系列共三篇:

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

– 完 –

评论
发表评论
4个月前
赞了此文章!
2年前

真的很牛啊!

2年前

写的不错,严重支持

4年前

@Bolt_白衣苍狗 收藏的目的是啥捏,我想想这个功能的需求点在哪里

4年前

看到好文,有没有收藏功能

4年前

爱死博主了!!!谢谢!!!请问,博主的图片是自己画的么?用神马话的额?

WRITTEN BY
PUBLISHED IN
随便写写

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

我的收藏