点 多边形内外判断

问题情境:

  1.判断点是否在人体某个部位(不规则多边形)上

思路辨析:

  判断方法有好多种,需要考虑到实用性(局限性)和代码化简易程度。

  1.面积和判断,内角和判断(转角法)等,或局限于多边形形状(凹、凸),或代码计算有复杂地方(弧长,角度计算),或局限于多边形顶点的顺序问题等。

  2.观察及检验之下,射线法(判断奇偶)和改进的弧长法,可用。

原理阐释:

  1.射线法:以被测点为一端点,做一射线(任何斜率都可,一般做水平线或竖直线),如果穿越多边形边的次数为偶(点在外),为奇(点在内)。自己动手画图加以理解。局限性,射线过多边形的顶点,或射线过某条多边形的边。所以代码中要特殊考虑。

  2.改进的弧长法:叫法不同而已。原理可以从转角法(或弧长法)出发理解。以被测点为原点建坐标系,判断两个顶点所属象限的关系(两个顶点没有次序关系):同一个象限认为是 0,间隔一个象限是 1,间隔二个象限 是± 2(分方向),间隔三个象限是-1。得出值求和,不为0即在多边形内部。限制,点在坐标轴上的判断,要特殊考虑。

  3.弧长法:以被测点为圆心,作单位圆,把边投影到单位圆上,对应一段段 弧长,规定逆时针为正,顺时针为负,计算弧长代数和:代数和为0,点在多边形外部;代数和为2π,点在多边形内部;代数和为π,点在多边形边上。

代码:

  1.射线法的代码暂不附上。

  2.改进的弧长法(c#):

//    /// <summary>
        /// 判断某点是否在多边形里面
        /// </summary>
        /// <param name="point">点</param>
        /// <param name="points">多边形各个顶点</param>
        /// <returns></returns>
        public bool IsInMultiLine(Point point, Point[] points)
        {
            Point[] point_norm = new Point[points.Length];
            int i = 0;
            for (i = 0; i < points.Length; i++)
            {
                point_norm[i] = new Point(points[i].X - point.X, points[i].Y - point.Y); // 坐标平移 
            }
            int zone1 = point_norm[0].X >= 0 ? (point_norm[0].Y >= 0 ? 0 : 3) : (point_norm[0].Y >= 0 ? 1 : 2);// 计算象限
            int sum = 0;

            for (i = 1; i < point_norm.Length; i++)
            {
                if (point_norm[i].X == 0 && point_norm[i].Y == 0)
                {
                    break;// 被测点为多边形顶点
                }
                int crossValue = point_norm[i].Y * point_norm[i - 1].X - point_norm[i].X * point_norm[i - 1].Y;         // 计算叉积

                if (crossValue == 0 && point_norm[i - 1].X * point_norm[i].X <= 0 && point_norm[i - 1].Y * point_norm[i - 1].Y <= 0)
                {
                    break;  // 点在边上
                }
                int zone2 = point_norm[i].X >= 0 ? (point_norm[i].Y >= 0 ? 0 : 3) : (point_norm[i].Y >= 0 ? 1 : 2);// 计算象限

                if (zone2 == (zone1 + 1) % 4)
                {
                    sum += 1;
                }
                else if (zone2 == (zone1 + 3) % 4)
                {
                    sum -= 1;
                }
                else if (zone2 == (zone1 + 2) % 4)
                {
                    if (crossValue > 0)
                    {
                        sum += 2;
                    }
                    else
                    {
                        sum -= 2;
                    }
                }
                zone1 = zone2;
            }

            if (i < point_norm.Length || sum != 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

  

原文地址:https://www.cnblogs.com/gaara-zhang/p/12461746.html