《算法的乐趣》第四十节

本节介绍矢量点积及其在计算几何中的应用。点积定义为对应坐标乘积之和，其结果的正负可判断两矢量夹角为钝角、锐角还是直角。

本节介绍矢量点积及其在计算几何中的应用。点积定义为对应坐标乘积之和，其结果的正负可判断两矢量夹角为钝角、锐角还是直角。

随后讲解三类几何位置判断：判断点是否在线段上，需先用叉积判断共线，再做排斥试验检查点是否落在以线段为对角线的矩形内，两者同时满足才行。判断两线段是否相交，采用快速排斥试验（两线段的包围矩形是否相交）与跨立试验（利用叉积判断两端点是否分居对方所在直线两侧）相结合，两者同时满足即为相交。

最后讨论点与多边形的关系，采用射线法：从点发出射线，统计与多边形边的交点数，奇数为内部。为使算法可行，将无穷远射线简化为边界到点的线段，并处理射线穿过顶点、与边平行等特殊情况。工程上还会先用多边形外包矩形快速排除。