计算几何常用算法 直线拐点判断 线段相交判断

"计算几何常用算法" 计算几何是计算机科学的一个分支，主要研究解决几何问题的算法。作为计算机科学的一个分支，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等多个领域有着十分重要的应用。 在计算几何中，有多种基本概念和常用算法，包括矢量的概念、矢量加减法、矢量叉积、折线段的拐向判断、判断点是否在线段上、判断两线段是否相交、判断线段和直线是否相交、判断矩形是否包含点等。 矢量的概念：如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段（directed segment）。如果有向线段 p1p2 的起点 p1 在坐标原点，我们可以把它称为矢量（vector）p2。 矢量加减法：设二维矢量 P = ( x1,y1 ) ，Q = ( x2 , y2 ) ，则矢量加法定义为： P + Q = ( x1 + x2 , y1 +y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。 矢量叉积：计算矢量叉积是与直线和线段相关算法的核心部分。设矢量 P = (x1,y1) ，Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2 和 p1+p2 所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。 折线段的拐向判断：折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段 p0p1 和 p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向。 判断点是否在线段上：设点为 Q，线段为 P1P2 ，判断点 Q 在该线段上的依据是：( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2 为对角顶点的矩形内。 判断两线段是否相交：我们分两步确定两条线段是否相交：(1)快速排斥试验设以线段 P1P2 为对角线的矩形为 R， 设以线段 Q1Q2 为对角线的矩形为 T，如果 R 和 T 不相交，显然两线段不会相交。(2)跨立试验 如果两线段相交，则两线段必然相互跨立对方。 计算几何常用算法还包括判断线段和直线是否相交、判断矩形是否包含点、判断圆是否在矩形中、判断点是否在多边形中、判断线段是否在多边形内等。 计算几何常用算法是解决几何问题的关键，通过学习和掌握这些算法，可以更好地应用计算几何解决问题。