叉积判断点在多边形内外 poj2318

本文主要是介绍叉积判断点在多边形内外 poj2318，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算几何中长遇到的问题：判断特定点是否在平面多边形内部。向量叉积是一种方法，用于凸多边形。【优角：角度值大于180度小于360度。凸多边形：沿着多边形的一边做一条直线，如果剩下所有的部分都在直线的同侧，那么称这是一个凸多边形，凸多边形是没有优角的】

判断：连接第i条边的第一个端点和测试点成向量u，再连接第一个端点与第二个端点成向量v，记录叉积结果，除第一条边外，叉积结果和上一条边对应的叉积的乘积是正数的话继续判断，负数则不在多边形内。

结果为正也就意味着点和边的时针方向是一致的，边按照一定的时针方向构成多边形。所有点都是如此的话点自然在多边形的内部。

struct Edge{point p1,p2;
};
bool inside(point p,edge[],int n){ //n是多边形的边数int now,pre;for(int i=0;i<n;i++){now=multi(p,edge[i].p1,edge[i].p2);if(i>0&&now*pre<0) return 0;pre=now;}return 1;
} 

问题：http://poj.org/problem?id=2318

这篇关于叉积判断点在多边形内外 poj2318的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---