关于次数点在多边形内图的横坐标取点问题?

叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
若 P × Q = 0 , 则P与Q共线但可能同向也可能反向。
叉积的方向与进行叉积的两个向量都垂直所以叉积向量即为这两个向量构成平面的法向量。

我们来考虑题目假设凸点在多边形内各个定点坐标按照逆时针方向存储于一个数组中,那么可以通过计算0-i与0-P两个向量之间的左右关系确定点P于某两个相邻的顶点构成的向量之间如O-x与o-(x-1),然后看是否(x-1)-p向量位于(x-1)-x向量的逆时针方姠如果是顺时针方向则不在凸点在多边形内内。

参考资料

 

随机推荐