【转】已知四边形的四个点,求一个点是否在四边形之内

已知四边形(凸四边形)的四个点A、B、C、D(按逆时针顺序)的坐标,求点P是否在ABCD所围成的四边形内,可以通过向量叉乘的方法实现。

先提供一种简单情景(假定四边形是一个凸四边形)的解决方法:

原理:凸多边形内部的点都在凸多边形的边所在的向量的同一侧(前提是计算边所在的向量时采用的是同一个方向,同为顺时针或者同为逆时针),利用叉积求解。
假设四边形四个顶点依次为A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4),待判断的点为P(x,y),如果点P在四边形内部,则向量AB * AP(注意:1.这是求叉积;2.AB、AP均为向量,也就等于(x2-x1) * (y-y1)-(y2-y1) * (x-x1))的值与BC*BP、CD * CP、DA * DP的值同号(若有等于零的情况,则表示P在边上,可以根据自己的喜好把它当做是内部或者外部),即四个值同为正或者同为负,则点P在ABCD内部,否则在外部。
如果是凹四边形还要做一些其他处理,就是找到导致四边形为凹的那个顶点,也是借助于叉积,然后把四边形分成两个三角形(三角形肯定是凸的了),再按照上面的方法计算叉积,即可解决。
总结:叉积是判断多边形凹凸性以及点是否在凸多边形内部的利器。

向量AB(B.x - A.x , B.y - A.y);

向量AP(P.x - A.x , P.y - A.y);

向量叉乘ABxAP = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);

        /// <summary>
        /// 判断点是否在矩形内
        /// </summary>
        /// <param name="x">坐标点X</param>
        /// <param name="y">坐标点Y</param>
        /// <param name="ps">矩形4个顶点</param>
        /// <returns></returns>
        private bool IsPointInRect(int x, int y, Point[] ps)
        {
            Point A = ps[0];
            Point B = ps[1];
            Point C = ps[2];
            Point D = ps[3];
            int a = (B.X - A.X) * (y - A.Y) - (B.Y - A.Y) * (x - A.X);
            int b = (C.X - B.X) * (y - B.Y) - (C.Y - B.Y) * (x - B.X);
            int c = (D.X - C.X) * (y - C.Y) - (D.Y - C.Y) * (x - C.X);
            int d = (A.X - D.X) * (y - D.Y) - (A.Y - D.Y) * (x - D.X);
            if ((a >= 0 && b >= 0 && c >= 0 && d >= 0) || (a <= 0 && b <= 0 && c <= 0 && d <= 0))
            {
                return true;
            }
            //      AB X AP = (b.x - a.x, b.y - a.y) x (p.x - a.x, p.y - a.y) = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);  
            //      BC X BP = (c.x - b.x, c.y - b.y) x (p.x - b.x, p.y - b.y) = (c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x);  
            return false;
        }

原文地址:http://blog.csdn.net/laukaka/article/details/45168439

原文地址:https://www.cnblogs.com/mqxs/p/8385895.html