algorithm - 连接线段组的计数

Question

我正在尝试解决以下问题:假设我们得到了一堆具有一些起点和终点坐标的线段。所有这些都是水平或垂直的。我正在尝试提出一种算法来计算给定组中的组件数量。组件是一组线段，其中每个线段与至少一个其他线段相交(或者换句话说，可以从任何线段的任何点到任何其他线段上的任何点)。有没有可能比明显的 O(N^2) 解决方案做得更好？

Answer 1

可以使用扫线算法(1) (2)寻找路口。
使用这些交叉点来制作具有 union-find algorithm 的线段簇.

请注意，当交叉点数很高(大约 O(N^2))时，此方法可能是二次方的。