algorithm - 扫描算法以找到线之间的交点

Question

我有一组线 L 和一组点 P。我想找出 L 的多少条线与穿过点 p 的水平线相交。我该如何计算？

Answer 1

假设您的线段集存储为 (start, stop) 对并且多个交叉点计数多次，则此答案适用。
第一步是丢弃所有 x 坐标 - 只有 y 坐标重要。然后从 L 和 P 构建一个对数组。对于 L 中的每个线段，将 (y_start, START) 和 (y_stop, STOP) 添加到数组中。对于 P 中的每个点，将 (y, POINT) 添加到数组中( START, STOP, POINT 只是任意值，例如 C 枚举)。按第一个值对对数组进行排序。
然后，初始化 n = 0, l = 0 并循环遍历数组并查看每对的第二个值:

如果是 START ，则增加 l 。

如果是 STOP ，则递减 l 。

如果是 POINT ，则将 l 添加到 n 。

n 是你的最终结果。总复杂度由排序 O((|L| + |P|) log(|L| + |P|)) 决定。