矢量叉积法.docxVIP

矢量叉积法 如果一个点在这个凸四边形内，那么按照逆时针方向走的话，该点一定会在每一条的左边。 所以方法就是：按照逆时针方向遍历这个凸四边形的每一条边的两个顶点和，然后判断给定点是否在矢量左边就可以了。 而判断一个点是否在一个矢量的左边，可以利用矢量叉积。 设,,给定点是，构造两条矢量边： 则和的叉积为(的行列式)： 值为： 然后利用右手法则进行判断： 如果,则点在矢量的左边 如果,则点在矢量的右边 这样就可以判断点与的相对位置了。然后按照逆时针方向，对凸四边形的每一条边都如此判断，如果每次都判断出在左边，那么就说明这个点在凸多边形内部了。 个人思路：在编程中，判断方向比较麻烦，因此将顺时针和逆时针的两种情况同时考虑进来，如果按照某一个方向，对凸四边形的每一条边都计算，如果每次的符号相同，那么就说明这个点在凸多边形内部了。 ? //?计算矢量叉积的符号，正返回1，负返回-1 int?CArithmetic::SignOfVectorProduct(double?_x1,?double?_y1,?double?_x2,?double?_y2) { ????double?res=_x1*_y2-_y1*_x2; ????if(res0) ???????return?1; ????else?if(res0) ???????return?-1; ????else ???????return?0; } //计算矢量叉积的符号，正返回1，负返回-1 int?CArithmetic::SignOfVectorProduct(CPoint _pointA, CPoint _pointB, CPoint _pointC) { ????double?x1=_pointB.x-_pointA.x; ????double?y1=_pointB.y-_pointA.y; ????double?x2=_pointC.x-_pointA.x; ????double?y2=_pointC.y-_pointA.y; ????return?SignOfVectorProduct(x1,y1,x2,y2); } //?判断点是否在四边形内，矢量方法 BOOL CArithmetic::IsPointInByVector(CPoint _point, CPoint* _vertexs) { ????int?sign1=SignOfVectorProduct(_vertexs[0],_vertexs[1],_point); ????int?sign2=SignOfVectorProduct(_vertexs[1],_vertexs[2],_point); ????int?sign3=SignOfVectorProduct(_vertexs[2],_vertexs[3],_point); ????int?sign4=SignOfVectorProduct(_vertexs[3],_vertexs[0],_point); ??? if(sign1==0||sign2==0||sign3==0||sign4==0) ?????? return TRUE; ????if(sign1==sign2sign2==sign3sign3==sign4) ???????return?TRUE; ????return?FALSE; }