线段相交检测算法
介绍
线段相交检测算法是计算几何学中的基础问题，用于判断二维平面上两条线段是否相交。在图形学、地理信息系统、碰撞检测、路径规划等领域有广泛应用。该算法的核心思想是利用向量的叉积来判断两条线段的相对位置关系，确定它们是否相交。
算法步骤
定义两条线段：线段1由点P1和P2组成，线段2由点P3和P4组成
计算向量叉积：判断P3和P4分别位于线段P1P2的哪一侧
计算向量叉积：判断P1和P2分别位于线段P3P4的哪一侧
如果P3和P4分别位于线段P1P2的两侧，且P1和P2分别位于线段P3P4的两侧，则两线段相交
特殊情况处理：处理共线、端点重合等边界情况
核心特性
基于向量叉积：利用向量叉积的符号判断点在线段的哪一侧
边界情况处理：能处理端点重合、共线等特殊情况
时间复杂度：O(1)，只需进行固定次数的向量运算
空间复杂度：O(1)，只需存储几个点的坐标
基础实现
代码实现
Java
...