线段求交算法

线段求交算法（segment intersection），理学-计算机科学技术-计算机科学理论-算法-计算几何算法，线段求交算法是解决线段求交问题的算法。在线段求交问题中，给定一组线段（用顶点坐标表示），要求：①判断是否有两条线段相交；②输出所有相交的线段对。概述在计算几何中（见计算几何算法），线段求交是指，给定n个不同的线段s1,s2,...,sn(以端点的坐标表示线段)，想要解决以下两个问题:①判断是否存在线段对(si,sj),i≠j使得si,sj相交。②输出所有相交的线段对。最简单的算法是检查每一对线段，时间复杂度是O(n2)。但是线段交的个数p在通常的情况下要比线段个数的平方n2要少，所以，希望得到一个时间复杂度与输出的线段对个数p相关的算法。