将一组线条拆分为相交线段

Question

我有一组线条可能会在某些点相交。每条线至少有2个点。我想要做的是当每条线与其他线相交并将所有线存储到列表中时分割每条线。在这个结果列表中可能没有任何行与其他行相交。

一个路口可能只在一条线上的点是什么使路口检测微不足道（只是相互比较各点）进行。我认为非常具有挑战性的是找到解决此问题的高性能算法。

感谢您的帮助！

编辑：线被表示为点，例如， A =（0,0），（10,1），（20,2），（30,3），（35,4），B =（12,4），（10,1） 5）

Answer 1

平面扫描算法。

在任何地方查找参考。

本质上，我们沿着x轴扫描每个线段，将startx和endx存储为“事件”。排序事件。然后，您保留第二个“活动”段的排序列表，当您点击startx时将行添加到活动列表中，并在您碰到endx时删除它。活动列表按y排序。所以你只需要一些实际的相交测试，其中x和y都重叠。