计算几何算法详解：线段、点的关系及相交判断

"这篇文档介绍了计算机图形学中的常见几何算法，包括矢量计算、点与线的关系、对象间距离的计算以及线段和直线相交的判断等。这些概念和算法在游戏开发、计算机视觉、图像处理等领域都有广泛应用。" 在计算机科学中，计算几何是一个重要的分支，它涉及几何形状的表示、操作和分析。以下是对标题和描述中提到的知识点的详细解释： 1. **矢量减法**： 矢量减法是将一个矢量从另一个矢量中减去，计算结果也是一个矢量。在二维空间中，给定两个矢量P=(x1, y1)和Q=(x2, y2)，P-Q=(x1-x2, y1-y2)。这个操作满足矢量的反称性，即P-Q=-(Q-P)。 2. **矢量叉积**： 叉积的结果是一个标量，表示两个矢量构成的平行四边形的面积。对于矢量P=(x1, y1)和Q=(x2, y2)，P×Q=x1*y2-x2*y1。叉积具有方向性，P×Q=-(Q×P)，并且P×(-Q)=-P×Q。根据叉积的符号，可以判断两个矢量的方向关系：如果P×Q>0，P在Q的顺时针方向；如果P×Q<0，P在Q的逆时针方向；如果P×Q=0，P与Q共线，可能同向也可能反向。 3. **判断点在线段上**： 要判断点Q是否在线段P1P2上，需要检查两个条件：(Q-P1)×(P2-P1)=0，这意味着Q、P1和P2三点共线，且Q在以P1和P2为对角点的矩形内。 4. **判断两线段是否相交**： 首先进行快速排斥试验，比较两线段对角线形成的矩形R和T是否相交，如果不相交，线段肯定不相交。然后进行跨立试验，检查两线段的端点是否分别位于对方线段的两侧，如果满足(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)≥0和(Q1-P1)×(P2-P1)*(P2-P1)×(Q2-P1)≥0，说明线段相交。 5. **判断线段和直线是否相交**： 如果线段P1P2和直线Q1Q2相交，等价于线段P1P2跨立Q1Q2，即满足(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)≥0的条件。 6. **判断矩形是否包含点**： 矩形由其四个顶点定义，判断点是否在矩形内部，需要检查点的横坐标和纵坐标是否在矩形的最小和最大坐标值之间。 这些基本的几何算法是计算几何的基础，它们在实现复杂的图形操作，如碰撞检测、路径规划等场景中发挥着关键作用。理解并熟练掌握这些算法能够提升计算机程序处理几何问题的效率和准确性。