判断点P是和多边形(凸or凹)的位置关系

方法1:

    从点P向左做射线,计算与多边形的交点数。如果交点个数为奇数,点P在多边形内部;如果交点个数为偶数,点P在多边形外部。可以按任意顺序考虑多边形的每一条边,来求取交点的总个数。

    计算时需要注意:(以边P1P2为例)

  1. 如果一个多边形顶点以该射线为切线,则直接忽略该顶点(因为射线会与两条线段的端点相交,而这两条线段有一个共同的端点);

  2. 如果边P1P2水平,射线与其无交点或有无数个交点,该边也可以直接忽略;

  3. 如果边P1P2竖直,很容易判断是否相交(只能有一个交点);

  4. 判断相交之前,先判断P是否在边P1P2上,如果在,则P在多边形内部(可根据内部的不同定义更改)。

注意:可以使用bounding box进行加速。


方法2:

    首先保证多边形的所有点都有序。然后,做P点到多边形所有点的连线,计算P点与多边形所有边的端点所成的角度(在P点处所成的角)的和(根据边的顶点位置,求出来的角度有正有负)。如果所有角度的和等于 2PI ,则点P在多边形内;否则,点P在多边形外。

    同样,可以使用bounding box进行加速。


判断一个点P是否在三角形ABC内:

当点p在三角形abc内时,4个三角形的面积满足:abc = abp + apc + pbc

计算面积使用向量外积:abc = |ab x ac| / 2

而且因为:

pb x pc = (ab-ap) x (ac-ap) = ab x ac - ab x ap - ap x ac

所以公式转换为:

ab x ac 是否等于 ab x ap + ap x ac + (ab x ac - ab x ap - ap x ac)

转自博客:http://www.html-js.com/article/1528

今天就来讲讲射线法在实际应用中的一些问题和解决方案。

  1. 点在多边形的边上

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

    判断点P是和多边形(凸or凹)的位置关系 第1张

    看了上面的图就会发现,不管算不算穿越,都会陷入两难的境地——同样落在多边形边上的点,可能会得到相反的结果。这显然是不正确的,因此对这种特殊情况需要特殊处理。

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

    判断点P是和多边形(凸or凹)的位置关系 第2张

    这其实是第一种情况的一个特例。

  3. 射线经过多边形顶点

    射线刚好经过多边形顶点的时候,应该算一次还是两次穿越?这种情况比前两种复杂,也是实现中的难点,后面会讲解它的解决方案。

    判断点P是和多边形(凸or凹)的位置关系 第3张

  4. 射线刚好经过多边形的一条边

    这是上一种情况的特例,也就是说,射线连续经过了多边形的两个相邻顶点。

    判断点P是和多边形(凸or凹)的位置关系 第4张

解决方案:

  1. 判断点是否在线上的方法有很多,比较简单直接的就是计算点与两个多边形顶点的连线斜率是否相等,中学数学都学过。

  2. 点和多边形顶点重合的情况更简单,直接比较点的坐标就行了。

  3. 顶点穿越看似棘手,其实我们换一个角度,思路会大不相同。先来回答一个问题,射线穿越一条线段需要什么前提条件?没错,就是线段两个端点分别在射线两侧。只要想通这一点,顶点穿越就迎刃而解了。这样一来,我们只需要规定被射线穿越的点都算作其中一侧。

    判断点P是和多边形(凸or凹)的位置关系 第5张

    如上图,假如我们规定射线经过的点都属于射线以上的一侧,显然点D和发生顶点穿越的点C都位于射线Y的同一侧,所以射线Y其实并没有穿越CD这条边。而点C和点B则分别位于射线Y的两侧,所以射线Y和BC发生了穿越,由此我们可以断定点Y在多边形内。同理,射线X分别与AD和CD都发生了穿越,因此点X在多边形外,而射线Z没有和多边形发生穿越,点Z位于多边形外。

  4. 解决了第三点,这一点就毫无难度了。根据上面的假设,射线连续经过的两个顶点显然都位于射线以上的一侧,因此这种情况看作没有发生穿越就可以了。由于第三点的解决方案实际上已经覆盖到这种特例,因此不需要再做特别的处理。

问题都解决了,其实并不复杂,不是吗?啥也不说了,上代码。

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

    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 && sy === py) || (tx === px && ty === py)) {
        return 'on'
      }

      // 判断线段两端点是否在射线两侧      if((sy < py && ty >= py) || (sy >= py && ty < py)) {
        // 线段上与射线 Y 坐标相同的点的 X 坐标        var x = sx + (py - sy) * (tx - sx) / (ty - sy)

        // 点在多边形的边上        if(x === px) {
          return 'on'
        }

        // 射线穿过多边形的边界        if(x > px) {
          flag = !flag        }
      }
    }

    // 射线穿过多边形边界的次数为奇数时点在多边形内    return flag ? 'in' : 'out'
  }


http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf 相关数学资料

https://sourceforge.net/p/jsclipper/wiki/documentation/#clipperlibclipperpointinpolygon


ClipperLib.Clipper.PointInPolygon = function (pt, path)
{
  //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
//See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos
  //http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
  var result = 0,
    cnt = path.length;
  if (cnt < 3)
    return 0;
  var ip = path[0];
  for (var i = 1; i <= cnt; ++i)
  {
    var ipNext = (i == cnt ? path[0] : path[i]);
    if (ipNext.Y == pt.Y)
    {
      if ((ipNext.X == pt.X) || (ip.Y == pt.Y && ((ipNext.X > pt.X) == (ip.X < pt.X))))
        return -1;
    }
    if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
    {
      if (ip.X >= pt.X)
      {
        if (ipNext.X > pt.X)
          result = 1 - result;
        else
        {
          var d = (ip.X - pt.X) * (ipNext.Y - pt.Y) - (ipNext.X - pt.X) * (ip.Y - pt.Y);
          if (d == 0)
            return -1;
          else if ((d > 0) == (ipNext.Y > ip.Y))
            result = 1 - result;
        }
      }
      else
      {
        if (ipNext.X > pt.X)
        {
          var d = (ip.X - pt.X) * (ipNext.Y - pt.Y) - (ipNext.X - pt.X) * (ip.Y - pt.Y);
          if (d == 0)
            return -1;
          else if ((d > 0) == (ipNext.Y > ip.Y))
            result = 1 - result;
        }
      }
    }
    ip = ipNext;
  }
  return result;
};
var poly = [{X:10,Y:10},{X:110,Y:10},{X:110,Y:110},{X:10,Y:110}];
var pt = new ClipperLib.IntPoint(50,50);
var inpoly = ClipperLib.Clipper.PointInPolygon(pt, poly);
// inpoly is 1, which means that pt is in polygon


本文标题:判断点P是和多边形(凸or凹)的位置关系
本文链接:https://56way.com/p/126.html
作者授权:除特别说明外,本文由 无路 原创编译并授权 小无路 刊载发布。
版权声明:本文不使用任何协议授权,您可以任何形式自由转载或使用。

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。