计算几何–线段求交

线段求交 问题描述:已知两条线段P1P2P_1P_2P1​P2​和Q1Q2Q_1Q_2Q1​Q2​,判断P1P2P_1P_2P1​P2​和Q1Q2Q_1Q_2Q1​Q2​是否相交,若相交,求出交点。 两条线段的位置关系可以分为三类:有重合部分、无重合部分但有交点、无交点。 方法一 step1:快速排斥实验 设以线段P1P2P_1P_2P1​P2​为对角线的矩形为R,设以线段Q1Q2Q_1Q_2Q1​Q2​为对角线的矩形为T,如果R和T不相交,则两线段不相交。 step2:跨立实验 如果两线段相交,则两线段必然相互跨立对方。 若PP1P2P_1P_2P1​P2​跨立Q1Q2Q_1Q_2Q1​Q2