algorithm - 将一组线拆分为相交线段

Question

我有一组可能在某些点相交的线。每条线至少由 2 个点构成。我想要做的是在每条线与另一条线相交时拆分每条线并将所有线存储到一个列表中。在此结果列表中，可能没有任何线与另一条线相交。

交点可能只出现在一条线上的点上，这使得交点检测变得微不足道(只需将每个点相互比较)。我认为非常具有挑战性的是找到一个高性能的算法来解决这个问题。

感谢您的帮助!

编辑:线表示为点，例如A = (0,0),(10,1),(20,2),(30,3),(35,4) 和 B = (12,-4), (10,1), (8, 5)

Answer 1

平面扫描算法。

在任何地方查找引用。

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