我有一组线 L 和一组点 P。我想找出 L 的多少条线与穿过点 p 的水平线相交。我该如何计算?
最佳答案
假设您的线段集存储为 (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|))
决定。
关于algorithm - 扫描算法以找到线之间的交点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66035807/