我有一组线，可以在某些点相交。每条线至少由2个点构成我想做的是在每一行与另一行相交时将其拆分，并将所有行存储到一个列表中。在此结果列表中，可能没有任何线与其他线相交。
交集可能只出现在一条直线的点上，这使得交集检测变得微不足道（只需相互比较每个点）。我认为非常有挑战性的是找到一个有效的算法来解决这个问题。
谢谢你的帮助！
编辑：线表示为点，例如A=（0,0），（10,1），（20,2），（30,3），（35,4）和B=（12，-4），（10,1），（8，5）
最佳答案
平面扫描算法。
在任何地方查找参考资料。
本质上，我们沿着X轴扫描每个线段，将STARTX和EDX存储为“事件”。对事件进行排序然后保留第二个排序的“活动”段列表，单击startx时向活动列表添加行，单击endx时将其删除。活动列表按Y排序。因此您只需要几个实际的交集测试，其中的线在X和Y中重叠。